按顺时针sorting点？

给定一个x，y点的数组，我该如何按顺时针顺序排列这个数组的点（围绕它们的整个平均中心点）？ 我的目标是将点传递给线条创build函数，以最终看起来相当“坚固”的东西，尽可能凸出，没有线相交。

对于它的价值，我使用Lua，但任何伪代码将不胜感激。 非常感谢您的帮助！

更新：作为参考，这是基于Ciamej的优秀答案（忽略我的“应用程序”前缀）的Lua代码：

function appSortPointsClockwise(points) local centerPoint = appGetCenterPointOfPoints(points) app.pointsCenterPoint = centerPoint table.sort(points, appGetIsLess) return points end function appGetIsLess(a, b) local center = app.pointsCenterPoint if ax >= 0 and bx < 0 then return true elseif ax == 0 and bx == 0 then return ay > by end local det = (ax - center.x) * (by - center.y) - (bx - center.x) * (ay - center.y) if det < 0 then return true elseif det > 0 then return false end local d1 = (ax - center.x) * (ax - center.x) + (ay - center.y) * (ay - center.y) local d2 = (bx - center.x) * (bx - center.x) + (by - center.y) * (by - center.y) return d1 > d2 end function appGetCenterPointOfPoints(points) local pointsSum = {x = 0, y = 0} for i = 1, #points do pointsSum.x = pointsSum.x + points[i].x; pointsSum.y = pointsSum.y + points[i].y end return {x = pointsSum.x / #points, y = pointsSum.y / #points} end 

Answer 1

首先，计算中心点。 然后使用任何你喜欢的sortingalgorithm对点进行sorting，但是使用特殊的比较例程来确定一个点是否比另一个更小。

你可以通过这个简单的计算来检查一个点（a）是否在另一个（b）的左边或右边与中心有关：

 det = (ax - center.x) * (by - center.y) - (bx - center.x) * (ay - center.y) 

如果结果为零，那么它们与中心在同一条线上，如果它是正的或负的，那么它在一边或另一边，所以一点在另一边。 使用它可以构造一个小于关系来比较点，并确定它们应该出现在sorting数组中的顺序。 但是你必须定义这个顺序的起点在哪里，我的意思是什么angular度是起始的angular度（例如X轴的正半轴）。

比较函数的代码如下所示：

 bool less(point a, point b) { if (ax - center.x >= 0 && bx - center.x < 0) return true; if (ax - center.x < 0 && bx - center.x >= 0) return false; if (ax - center.x == 0 && bx - center.x == 0) { if (ay - center.y >= 0 || by - center.y >= 0) return ay > by; return by > ay; } // compute the cross product of vectors (center -> a) x (center -> b) int det = (ax - center.x) * (by - center.y) - (bx - center.x) * (ay - center.y); if (det < 0) return true; if (det > 0) return false; // points a and b are on the same line from the center // check which point is closer to the center int d1 = (ax - center.x) * (ax - center.x) + (ay - center.y) * (ay - center.y); int d2 = (bx - center.x) * (bx - center.x) + (by - center.y) * (by - center.y); return d1 > d2; } 

这将从12点开始顺时针顺序点。 在同一个“小时”上的点将从离中心较远的点开始sorting。

如果使用整数types（在Lua中并不存在），则必须确保det，d1和d2variables是能够保存执行计算结果的types。

如果你想获得一些看起来坚实的东西，尽可能的凸出来，那么我猜你正在寻找一个凸包 。 您可以使用Graham Scan进行计算。 在这个algorithm中，您还必须从一个特殊的轴心点开始顺时针（或逆时针）对点进行sorting。 然后，每次检查是否向左或向右添加新凸点时，都重复简单的循环步骤，此检查基于与上述比较函数类似的交叉产品。

编辑：

if (ay - center.y >= 0 || by - center.y >=0)添加了一个if语句，以确保x = 0和y的点是从远离中央。 如果你不关心在同一个“小时”的点的顺序，你可以省略这个if语句，总是返回ay > by 。

通过添加-center.x和-center.y更正了第一个if语句。

添加了第二个if语句(ax - center.x < 0 && bx - center.x >= 0) 。 这是一个明显的疏忽，它失踪了。 if语句现在可以重新组织，因为一些检查是多余的。 例如，如果第一个if语句中的第一个条件是false，那么第二个if的第一个条件必须是true。 但是，我决定为了简单起见而保留代码。 编译器很可能会优化代码，并产生相同的结果。

Answer 2

你所要求的是一个被称为极坐标的系统。 从笛卡儿到极坐标的转换很容易以任何语言完成。 公式可以在这部分find。

我不知道Lua，但这个页面似乎提供了这个转换的代码片段。

转换为极坐标后，按angular度θ进行sorting。

Answer 3

你的问题一个有趣的替代方法是find旅行商问题（TSP）的近似最小值，即。 连接所有点的最短路线。 如果你的点形成一个凸形，那么它应该是正确的解决scheme，否则，它应该看起来很好（一个“实心”的形状可以被定义为一个具有低周长/面积比，这是我们在这里优化的） 。

你可以使用任何优化器的TSP实现，我相信你可以find你所select的语言吨。

Answer 4

另一个版本（如果在逆时针方向之前出现b，则返回true）：

  bool lessCcw(const Vector2D &center, const Vector2D &a, const Vector2D &b) const { // Computes the quadrant for a and b (0-3): // ^ // 1 | 0 // ---+--> // 2 | 3 const int dax = ((ax() - center.x()) > 0) ? 1 : 0; const int day = ((ay() - center.y()) > 0) ? 1 : 0; const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) << 1); /* The previous computes the following: const int qa = ( (ax() > center.x()) ? ((ay() > center.y()) ? 0 : 3) : ((ay() > center.y()) ? 1 : 2)); */ const int dbx = ((bx() - center.x()) > 0) ? 1 : 0; const int dby = ((by() - center.y()) > 0) ? 1 : 0; const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) << 1); if (qa == qb) { switch (qa) { case 0: case 3: return (bx() - center.x()) * (ay() - center.y()) < (by() - center.y()) * (ax() - center.x()); default: return (center.x() - bx()) * (ay() - center.y()) > (by() - center.y()) * (center.x() - ax()); } } else { return qa < qb; } } 

这是更快的，因为编译器（在Visual C ++ 2015上testing）不会生成跳转来计算dax，day，dbx，dby。 这里来自编译器的输出程序集：

 ; 345 : const int dax = ((ax() - center.x()) > 0) ? 1 : 0; mov eax, DWORD PTR _center$[esp-4] xor edx, edx push ebx push ebp push esi mov esi, DWORD PTR _a$[esp+8] ; 346 : const int day = ((ay() - center.y()) > 0) ? 1 : 0; ; 347 : const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) << 1); mov ebp, 2 vmovsd xmm3, QWORD PTR [eax] vmovsd xmm1, QWORD PTR [eax+8] vxorpd xmm2, xmm2, xmm2 vmovsd xmm0, QWORD PTR [esi] vsubsd xmm6, xmm0, xmm3 vmovsd xmm0, QWORD PTR [esi+8] vcomisd xmm6, xmm2 vsubsd xmm4, xmm0, xmm1 seta dl xor ecx, ecx vcomisd xmm4, xmm2 push edi seta cl mov edi, ebp ; 348 : /*const int qa = ; 349 : ( (ax() > center.x()) ; 350 : ? ((ay() > center.y()) ; 351 : ? 0 : 3) ; 352 : : ((ay() > center.y()) ; 353 : ? 1 : 2));*/ ; 354 : const int dbx = ((bx() - center.x()) > 0) ? 1 : 0; xor ebx, ebx lea eax, DWORD PTR [ecx+ecx] sub edi, eax lea eax, DWORD PTR [edx+edx] and edi, eax sub edi, ecx sub edi, edx mov edx, DWORD PTR _b$[esp+12] add edi, ebp vmovsd xmm0, QWORD PTR [edx] vsubsd xmm7, xmm0, xmm3 ; 355 : const int dby = ((by() - center.y()) > 0) ? 1 : 0; vmovsd xmm0, QWORD PTR [edx+8] vcomisd xmm7, xmm2 vsubsd xmm5, xmm0, xmm1 seta bl xor ecx, ecx vcomisd xmm5, xmm2 seta cl ; 356 : const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) << 1); lea eax, DWORD PTR [ecx+ecx] sub ebp, eax lea eax, DWORD PTR [ebx+ebx] and ebp, eax sub ebp, ecx sub ebp, ebx add ebp, 2 ; 357 : /*const int qb = ; 358 : ((bx() > center.x()) ; 359 : ? ((by() > center.y()) ; 360 : ? 0 : 3) ; 361 : : ((by() > center.y()) ; 362 : ? 1 : 2));*/ ; 363 : if (qa == qb) cmp edi, ebp jne SHORT $LN57@lessCw ; 364 : { ; 365 : switch (qa) test edi, edi je SHORT $LN6@lessCw cmp edi, 3 je SHORT $LN6@lessCw ; 370 : default: ; 371 : return (center.x() - bx()) * (ay() - center.y()) > (by() - center.y()) * (center.x() - ax()); vsubsd xmm0, xmm3, QWORD PTR [edx] vmulsd xmm1, xmm0, xmm4 vsubsd xmm0, xmm3, QWORD PTR [esi] pop edi vmulsd xmm0, xmm0, xmm5 xor eax, eax pop esi vcomisd xmm1, xmm0 pop ebp seta al pop ebx ; 372 : } ; 373 : } ; 374 : else ; 375 : { ; 376 : return qa < qb; ; 377 : } ; 378 : } ret 12 ; 0000000cH $LN6@lessCw: pop edi ; 366 : { ; 367 : case 0: ; 368 : case 3: ; 369 : return (bx() - center.x()) * (ay() - center.y()) < (by() - center.y()) * (ax() - center.x()); vmulsd xmm1, xmm7, xmm4 vmulsd xmm0, xmm5, xmm6 xor eax, eax pop esi vcomisd xmm0, xmm1 pop ebp seta al pop ebx ; 372 : } ; 373 : } ; 374 : else ; 375 : { ; 376 : return qa < qb; ; 377 : } ; 378 : } ret 12 ; 0000000cH $LN57@lessCw: pop edi pop esi pop ebp setl al pop ebx ret 12 ; 0000000cH 

请享用。