顺时针排列凹多边形顶点

Question

我有一组点，这些点位于一个凹多边形的边界上。我想找到一个没有交叉的多边形，它的顶点为这些点。换句话说，我想以逆时针（或顺时针）的方式排列凹多边形的顶点。

我看了看评估多边形是以逆时针还是顺时针的方法（计算和求和叉乘），但这不完全是我的问题：我有随机顺序的顶点，我想对它们进行排序，使它们顺时针或逆时针排列在多边形的外壳上。

我考虑取初始顶点序列，并连续识别交叉点。如果初始点序列是[x1，y1；x2，y2；x3，y3；...]，第二个和第三个点相交，我们将继续使用序列[x1，y1；x2，y3；x3，y2；...]。

你能想到什么算法？背后的概念是什么？你有参考资料的提示吗？

此致敬礼

- kiriloff

---

你所说的“crossing points”并不清楚，是指交叉线吗？在你的例子中，似乎是在改变点——从（x2，y2）和（x3，y3）到（x2，y3）和（x3，y2）？ - krjampani

Answer 1

如果我正确理解问题，您想要对输入点集进行排序，使其按某个可能凹多边形的顺时针顺序排列。可以按以下方式解决此问题。

让p1和p2分别为最左侧和最右侧的点。找到所有点的下半部凸包S。S包含p1、p2和所有在线段p1p2下方的凸包点。现在按照它们的x坐标对剩余点（不在S中的点）进行排序。这个排序顺序和S的顺序（由下半部凸包算法生成）将给你所需的所有顶点的顺时针顺序。

- krjampani

---

不是很准确：我想对一个凹多边形的顶点进行排序。但是我不能使用凸包方法，或者我漏掉了什么？感谢您的回答。 - kiriloff

你只计算了凸包的下半部分。点的最终顺序仍然可以是凹多边形的顺序。我已经添加了一张图片以使这更清楚。 - krjampani

我有一个新月形状。下半部分点的顺序并不能帮助我找到所有在最左和最右点之上的点的顺序！？我认为我不理解你最后一句话的意思：你能澄清或重新措辞吗：“这个排序顺序以及由下凸壳算法生成的S的顺序将给您所有顶点的所需顺时针顺序。” - kiriloff

我们将顶点分为两组。一组（S）包含下凸壳的点。这些点由图中的黑色边连接。其余顶点仅按从左到右排序。这些点由蓝色边连接。很容易看出，由于点已排序，因此没有两个蓝色边会相交。此外，很容易看出蓝色边不会穿过黑色边。因此，黑色和蓝色边共同表示凹多边形所有点的循环顺序。 - krjampani

谢谢！现在让我们来看看我的点集（图中的红色点）。我想连接这些红点以获得形状轮廓（不用关心红线）。采用我们的方法：我找到凸包的下部。在上面，我有很多点，无法按x坐标排序以获得令人满意的结果。或者我误解了吗？您能解释一下您的方法如何解决这种情况吗？再次感谢！ - kiriloff

Answer 2

在构建多边形时，除非该多边形比可能是凹多边形的一组点更好地定义，否则必须使用该时间的信息。

例如，如果顶点来自形状或图像，则形状中的填充像素可能会有所帮助。对于一个项目，我需要对斑点周长上的点进行排序，因此我获取斑点的边界像素（可以用多种方式完成），然后通过这些像素进行DFS样式遍历以将它们按顺序放置。然后，我编写了算法来合并边缘并在交叉口做出决策。

- Nichole