c++ - 排序点 : concave polygon

Question

我有一组点，我试图从它们的角度按 ccw 顺序或 cw 顺序排序。我希望对这些点进行排序，使它们可以形成一个多边形，其区域或交叉点没有分割。这很难，因为在大多数情况下，它会是一个凹多边形。

point centroid;
int main( int argc, char** argv )
{
  // I read a set of points into a struct point array: points[n]

  // Find centroid
  double sx = 0; double sy = 0;
  for (int i = 0; i < n; i++)
  {
    sx += points[i].x;
    sy += points[i].y;
  }
  centroid.x = sx/n;
  centroid.y = sy/n;

  // sort points using in polar order using centroid as reference
  std::qsort(&points, n, sizeof(point), polarOrder);
}

// -1 ccw, 1 cw, 0 collinear
int orientation(point a, point b, point c)
{
   double area2 = (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
   if      (area2 < 0) return -1;
   else if (area2 > 0) return +1;
   else                return  0;
}

// compare other points relative to polar angle they make with this point
// (where the polar angle is between 0 and 2pi)
int polarOrder(const void *vp1, const void *vp2)
{
  point *p1 = (point *)vp1;
  point *p2 = (point *)vp2;

  // translation
  double dx1 = p1->x - centroid.x;
  double dy1 = p1->y - centroid.y;

  double dx2 = p2->x - centroid.x;
  double dy2 = p2->y - centroid.y;

  if      (dy1 >= 0 && dy2 < 0) { return -1; }  // p1 above and p2 below
  else if (dy2 >= 0 && dy1 < 0) { return  1; }  // p1 below and p2 above
  else if (dy1 == 0 && dy2 ==0) {               // 3-collinear and horizontal
      if      (dx1 >= 0 && dx2 < 0) { return -1; }
      else if (dx2 >= 0 && dx1 < 0) { return  1; }
      else                          { return  0; }
  }
  else return -orientation(centroid,*p1,*p2);   // both above or below
}

看起来这些点被准确地排序(粉红色)直到它们“塌陷”，在这种情况下算法跳过这些点然后继续..任何人都可以指出我正确的方向来对点进行排序以便它们形成我正在寻找的多边形？原始点图 - 蓝色、粉红色点 - 已排序

点列表:http://pastebin.com/N0Wdn2sm (您可以忽略第三个分量，因为所有这些点都位于同一平面上。)

Answer 1

下面的代码(抱歉，它是 C 而不是 C++)使用 atan2 正确排序。

您的代码的问题可能是它试图使用被比较的两个 vector 之间的夹角。这是注定要失败的。该阵列不是圆形的。它有第一个和最后一个元素。关于质心，对数组进行排序需要一个总的极坐标顺序:一个角度范围，使得每个点都对应一个唯一的角度，而不管其他点。角度是总极序，将它们作为标量进行比较提供了排序比较功能。

以这种方式，您提出的算法可以保证生成星形多段线。它可能会在不同的半径之间剧烈振荡(......你的数据会这样!这就是你所说的“陷入”的意思吗？如果是这样，它是你的算法和数据的一个特征，而不是实现错误)，并且点正好对应相同的角度可能会产生重合的边(直接位于彼此的顶部)，但边不会交叉。

我相信您选择的质心作为极坐标原点足以保证连接如上生成的折线的末端将产生完整的 star-shaped polygon。 ，但是，我没有证据。

用 Excel 绘制的结果

请注意，您可以从质心所在的近乎径向的边缘进行猜测!这就是我上面提到的“星形”。

为了说明这实际上是一个星形多边形，这里放大了令人困惑的左下角:

如果你想要一个在某种意义上“更好”的多边形，你将需要一个更高级(可能更高级)的算法，例如其他人提到的基于 Delaunay 三角剖分的方法。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct point {
  double x, y;
};

void print(FILE *f, struct point *p) {
  fprintf(f, "%f,%f\n", p->x, p->y);
}

// Return polar angle of p with respect to origin o
double to_angle(const struct point *p, const struct point *o) {
  return atan2(p->y - o->y, p->x - o->x);
}

void find_centroid(struct point *c, struct point *pts, int n_pts) {
  double x = 0, y = 0;
  for (int i = 0; i < n_pts; i++) {
    x += pts[i].x;
    y += pts[i].y;
  }
  c->x = x / n_pts;
  c->y = y / n_pts;
}

static struct point centroid[1];

int by_polar_angle(const void *va, const void *vb) {
  double theta_a = to_angle(va, centroid);
  double theta_b = to_angle(vb, centroid);
  return theta_a < theta_b ? -1 : theta_a > theta_b ? 1 : 0;
}

void sort_by_polar_angle(struct point *pts, int n_pts) {
  find_centroid(centroid, pts, n_pts);
  qsort(pts, n_pts, sizeof pts[0], by_polar_angle);
}

int main(void) {
  FILE *f = fopen("data.txt", "r");
  if (!f) return 1;
  struct point pts[10000];
  int n_pts, n_read;
  for (n_pts = 0; 
       (n_read = fscanf(f, "%lf%lf%*f", &pts[n_pts].x, &pts[n_pts].y)) != EOF;
       ++n_pts)
    if (n_read != 2) return 2;
  fclose(f);
  sort_by_polar_angle(pts, n_pts);
  for (int i = 0; i < n_pts; i++)
    print(stdout, pts + i);
  return 0;
}