c++ - 逆时针定向多边形线所需的编码算法

Question

我遇到了另一个问题。我有一个算法可以实现缠绕数算法来检测一个点是否位于多边形内。该算法要求多边形的边沿逆时针方向排列。我目前通过检查多边形的中心是否在边缘的左侧来做到这一点。如果不是，则按顺时针方向制作线条，并更改绕数算法结果的符号。

对于大多数情况，此方法非常有效。但是，我遇到了中心在多边形之外的情况。在这一点上，我的算法中断了，因为一些边被记录为逆时针，而实际上它们是顺时针的。

我一直在寻找一些资源来获得一些灵感:

How to determine if a list of polygon points are in clockwise order?

Ordering CONCAVE polygon vertices in (counter)clockwise?

https://math.stackexchange.com/questions/340830/clockwise-or-anticlockwise-edges-in-a-polygon

http://jeffe.cs.illinois.edu/teaching/373/notes/x05-convexhull.pdf

但是，这些资源主要处理凸多边形。我需要开发一种可以同时处理凸多边形和凹多边形的通用算法。虽然，如果这不存在(或无法完成)，那么我将解决创建两个单独的算法并检测多边形是否凹/凸的问题。

理想的算法会简单地检测所选多边形的特定边是顺时针还是逆时针。但我愿意接受将多边形的逆时针流中的边和顶点求助的算法。

我一直在考虑一种不需要使用多边形中心点的算法，因为结果将取决于中心是在多边形内部还是外部。

如果您有任何问题，请随时在评论中提出，我会尽快回复。谢谢!

编辑:

我应该注意到线条的方向是随机的。有些会逆时针。其他的会顺时针

Answer 1

假设您有一个无序列表，每行都有一个起始顶点和一个结束顶点:

• 为您订购的行创建一个空列表。
• 从无序列表中随机选择一行，将其从无序列表移至有序列表，并使其成为当前行。
• 虽然无序列表中还有剩余行:
  • 在无序列表中找到起始或结束顶点等于当前行的结束顶点的行，并将其从列表中删除。将其称为下一行。
  • 如果下一行的起始顶点等于当前行的结束顶点，则将其原样添加到有序列表的末尾
  • 否则如果下一行的结束顶点等于当前行的结束顶点，则交换下一行的开始和结束顶点并将其添加到有序列表的末尾
  • 使下一行成为新的当前行
• 完成后，使用鞋带公式检查整个列表的顺序，如 Yves Daoust 的回答中所述，如果为负，则交换所有行的开始和结束顶点

您可以使用哈希表(使用顶点值作为键)来更快地找到匹配线。如果这些线已经按顺序排列(但有些是错误的方式)那么这只是一个问题以前的。

如果有多条线共享一个顶点，则此算法将不起作用。