按顺时针顺序排序点？
给定一个 x,y 点数组，我如何按顺时针顺序（围绕它们的整体平均中心点）对该数组的点进行排序？我的目标是将点传递给线创建函数，最终得到看起来相当“实心”的东西，尽可能凸出，没有线相交。
对于它的价值，我正在使用 Lua，但任何伪代码都会受到赞赏。
更新：作为参考，这是基于 Ciamej 出色答案的 Lua 代码（忽略我的“app”前缀）：
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 a.x >= 0 and b.x < 0 then return true
elseif a.x == 0 and b.x == 0 then return a.y > b.y
end
local det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
if det < 0 then return true
elseif det > 0 then return false
end
local d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y)
local d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - 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
ipairs(tbl)，它会遍历从 1 到 #tbl 的 tbl 的索引和值。因此，对于总和计算，您可以这样做，大多数人认为这看起来更干净：for _, p in ipairs(points) do pointsSum.x = pointsSum.x + p.x; pointsSum.y = pointsSum.y + p.y end
ipairs 比数字 for 循环慢得多。
首先，计算中心点。然后使用您喜欢的任何排序算法对点进行排序，但使用特殊的比较例程来确定一个点是否小于另一个点。
通过这个简单的计算，您可以检查一个点 (a) 相对于中心是在另一点 (b) 的左侧还是右侧：
det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
如果结果为零，则它们与中心在同一条线上，如果为正或负，则在一侧或另一侧，因此一个点将先于另一个。使用它，您可以构建一个小于关系来比较点并确定它们应该出现在排序数组中的顺序。但是您必须定义该订单的开始位置，我的意思是起始角度是什么角度（例如x轴的正半部分）。
比较函数的代码如下所示：
bool less(point a, point b)
{
if (a.x - center.x >= 0 && b.x - center.x < 0)
return true;
if (a.x - center.x < 0 && b.x - center.x >= 0)
return false;
if (a.x - center.x == 0 && b.x - center.x == 0) {
if (a.y - center.y >= 0 || b.y - center.y >= 0)
return a.y > b.y;
return b.y > a.y;
}
// compute the cross product of vectors (center -> a) x (center -> b)
int det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - 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 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
int d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
return d1 > d2;
}
这将从 12 点开始顺时针排列点。同一“小时”上的点将从远离中心的点开始排序。
如果使用整数类型（在 Lua 中并不真正存在），您必须确保 det、d1 和 d2 变量属于能够保存执行计算结果的类型。
如果您想获得看起来坚固、尽可能凸的东西，那么我猜您正在寻找 Convex Hull。您可以使用 Graham Scan 计算它。在此算法中，您还必须从特殊的枢轴点开始顺时针（或逆时针）对点进行排序。然后每次检查是否向左或向右向凸包添加新点时重复简单的循环步骤，此检查基于叉积，就像上面的比较函数一样。
编辑：
添加了一个 if 语句 if (a.y - center.y >= 0 || b.y - center.y >=0) 以确保 x=0 和负 y 的点从离中心较远的点开始排序。如果您不关心同一“小时”的点数顺序，则可以省略此 if 语句并始终返回 a.y > b.y。
通过添加 -center.x 和 -center.y 更正了第一个 if 语句。
添加了第二个 if 语句 (a.x - center.x < 0 && b.x - center.x >= 0)。这是一个明显的疏忽，它丢失了。 if 语句现在可以重新组织，因为一些检查是多余的。例如，如果第一个 if 语句中的第一个条件为假，那么第二个 if 的第一个条件必须为真。但是，为了简单起见，我决定保留代码不变。编译器很可能会优化代码并产生相同的结果。
您需要的是一个称为 polar coordinates 的系统。从笛卡尔坐标到极坐标的转换可以用任何语言轻松完成。公式可在 this section 中找到。
转换为极坐标后，只需按角度 theta 排序。
解决您的问题的一种有趣的替代方法是找到旅行商问题 (TSP) 的近似最小值，即。连接所有点的最短路线。如果您的点形成一个凸形，它应该是正确的解决方案，否则，它应该仍然看起来不错（“实心”形状可以定义为具有低周长/面积比的形状，这是我们在这里优化的） .
您可以为 TSP 使用任何优化器的实现，我很确定您可以在您选择的语言中找到大量的优化器。
另一个版本（如果 a 逆时针方向出现在 b 之前，则返回 true）：
bool lessCcw(const Vector2D ¢er, const Vector2D &a, const Vector2D &b) const
{
// Computes the quadrant for a and b (0-3):
// ^
// 1 | 0
// ---+-->
// 2 | 3
const int dax = ((a.x() - center.x()) > 0) ? 1 : 0;
const int day = ((a.y() - center.y()) > 0) ? 1 : 0;
const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) << 1);
/* The previous computes the following:
const int qa =
( (a.x() > center.x())
? ((a.y() > center.y())
? 0 : 3)
: ((a.y() > center.y())
? 1 : 2)); */
const int dbx = ((b.x() - center.x()) > 0) ? 1 : 0;
const int dby = ((b.y() - center.y()) > 0) ? 1 : 0;
const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) << 1);
if (qa == qb) {
return (b.x() - center.x()) * (a.y() - center.y()) < (b.y() - center.y()) * (a.x() - center.x());
} else {
return qa < qb;
}
}
这更快，因为编译器（在 Visual C++ 2015 上测试）不会生成跳转来计算 dax、day、dbx、dby。这里是编译器的输出程序集：
; 28 : const int dax = ((a.x() - center.x()) > 0) ? 1 : 0;
vmovss xmm2, DWORD PTR [ecx]
vmovss xmm0, DWORD PTR [edx]
; 29 : const int day = ((a.y() - center.y()) > 0) ? 1 : 0;
vmovss xmm1, DWORD PTR [ecx+4]
vsubss xmm4, xmm0, xmm2
vmovss xmm0, DWORD PTR [edx+4]
push ebx
xor ebx, ebx
vxorps xmm3, xmm3, xmm3
vcomiss xmm4, xmm3
vsubss xmm5, xmm0, xmm1
seta bl
xor ecx, ecx
vcomiss xmm5, xmm3
push esi
seta cl
; 30 : const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) << 1);
mov esi, 2
push edi
mov edi, esi
; 31 :
; 32 : /* The previous computes the following:
; 33 :
; 34 : const int qa =
; 35 : ( (a.x() > center.x())
; 36 : ? ((a.y() > center.y()) ? 0 : 3)
; 37 : : ((a.y() > center.y()) ? 1 : 2));
; 38 : */
; 39 :
; 40 : const int dbx = ((b.x() - center.x()) > 0) ? 1 : 0;
xor edx, edx
lea eax, DWORD PTR [ecx+ecx]
sub edi, eax
lea eax, DWORD PTR [ebx+ebx]
and edi, eax
mov eax, DWORD PTR _b$[esp+8]
sub edi, ecx
sub edi, ebx
add edi, esi
vmovss xmm0, DWORD PTR [eax]
vsubss xmm2, xmm0, xmm2
; 41 : const int dby = ((b.y() - center.y()) > 0) ? 1 : 0;
vmovss xmm0, DWORD PTR [eax+4]
vcomiss xmm2, xmm3
vsubss xmm0, xmm0, xmm1
seta dl
xor ecx, ecx
vcomiss xmm0, xmm3
seta cl
; 42 : const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) << 1);
lea eax, DWORD PTR [ecx+ecx]
sub esi, eax
lea eax, DWORD PTR [edx+edx]
and esi, eax
sub esi, ecx
sub esi, edx
add esi, 2
; 43 :
; 44 : if (qa == qb) {
cmp edi, esi
jne SHORT $LN37@lessCcw
; 45 : return (b.x() - center.x()) * (a.y() - center.y()) < (b.y() - center.y()) * (a.x() - center.x());
vmulss xmm1, xmm2, xmm5
vmulss xmm0, xmm0, xmm4
xor eax, eax
pop edi
vcomiss xmm0, xmm1
pop esi
seta al
pop ebx
; 46 : } else {
; 47 : return qa < qb;
; 48 : }
; 49 : }
ret 0
$LN37@lessCcw:
pop edi
pop esi
setl al
pop ebx
ret 0
?lessCcw@@YA_NABVVector2D@@00@Z ENDP ; lessCcw
享受。
vector3 a = new vector3(1 , 0 , 0).......wrt X_axis
vector3 b = any_point - 中心；
- y = |a * b| , x = a . b
- Atan2(y , x)...............................gives angle between -PI to + PI in radians
- (Input % 360 + 360) % 360................to convert it from 0 to 2PI in radians
- sort by adding_points to list_of_polygon_verts by angle we got 0 to 360
最后你得到 Anticlockwize 排序的顶点
list.Reverse().......顺时针顺序
这是一种按顺时针顺序对矩形顶点进行排序的方法。我修改了 pyimagesearch 提供的原始解决方案并摆脱了 scipy 依赖。
import numpy as np
def pointwise_distance(pts1, pts2):
"""Calculates the distance between pairs of points
Args:
pts1 (np.ndarray): array of form [[x1, y1], [x2, y2], ...]
pts2 (np.ndarray): array of form [[x1, y1], [x2, y2], ...]
Returns:
np.array: distances between corresponding points
"""
dist = np.sqrt(np.sum((pts1 - pts2)**2, axis=1))
return dist
def order_points(pts):
"""Orders points in form [top left, top right, bottom right, bottom left].
Source: https://www.pyimagesearch.com/2016/03/21/ordering-coordinates-clockwise-with-python-and-opencv/
Args:
pts (np.ndarray): list of points of form [[x1, y1], [x2, y2], [x3, y3], [x4, y4]]
Returns:
[type]: [description]
"""
# sort the points based on their x-coordinates
x_sorted = pts[np.argsort(pts[:, 0]), :]
# grab the left-most and right-most points from the sorted
# x-roodinate points
left_most = x_sorted[:2, :]
right_most = x_sorted[2:, :]
# now, sort the left-most coordinates according to their
# y-coordinates so we can grab the top-left and bottom-left
# points, respectively
left_most = left_most[np.argsort(left_most[:, 1]), :]
tl, bl = left_most
# now that we have the top-left coordinate, use it as an
# anchor to calculate the Euclidean distance between the
# top-left and right-most points; by the Pythagorean
# theorem, the point with the largest distance will be
# our bottom-right point. Note: this is a valid assumption because
# we are dealing with rectangles only.
# We need to use this instead of just using min/max to handle the case where
# there are points that have the same x or y value.
D = pointwise_distance(np.vstack([tl, tl]), right_most)
br, tr = right_most[np.argsort(D)[::-1], :]
# return the coordinates in top-left, top-right,
# bottom-right, and bottom-left order
return np.array([tl, tr, br, bl], dtype="float32")
关注公众号
不定期副业成功案例分享
atan()，没有平方根，甚至没有除法。这是计算机图形思维的一个很好的例子。尽快剔除所有简单的情况，即使在困难的情况下，也尽可能少地计算以知道所需的答案。