geometry - Jarvis 行进算法可以返回未排序的结果吗？

Question

我正在尝试为一个非常复杂的点集计算一个复杂的外壳。见图片：

左边的绿色/蓝绿色线包含相邻的凸包点，即一个接一个。继续这个序列，下一个点应该是右下角的青色/绿色。

但是，如果我沿着阵列走，下一个似乎是右上角的那个，黄色。

是的，输出是 ascii，点云是正确的（与 GUI 输出相比）。

片段：

for(int i = 0; i< rd.length; i++) {
if( (*rd)[i].lon < lonMin) {
     lonMin = (*rd)[i].lon;
     leftMostPos = i;
}
}


 int [] hullIdx = new int[0];

 int p = leftMostPos, m = to!int((*rd).length), q;

 do {

    hullIdx ~= [p];

    q = (p + 1) % m;

    for ( int ij = 0; ij < m ; ij ++) {

         auto a = (*rd)[p];
         auto b = (*rd)[ij];
         auto c = (*rd)[q];

         double ornt = (b.lat - a.lat) * ( c.lon - b.lon) - (b.lon - a.lon) * (c.lat - b.lat) ;
         if (ornt < 0) q = ij;


      }
      p = q;

 } while ( p != leftMostPos);

语言是 D，我正在求解地理纬度和经度。Lons 是一个坐标，lats 是 x 坐标。矩阵逐行增加 y 坐标，朝下方向。这也被考虑在内。

我想知道 Jarvis 算法如何返回未排序的输出。我会感激你所有的帮助。

标签： geometrydconvex-hull