我有一个问题,我有一系列简单的非凸多边形的点(我希望我的术语是正确的)。但这些点不一定是按顺序排列的(即顺时针或逆时针)。为了让 Flash 的绘图 API 正确绘制填充区域,我需要让这些点在边缘周围按顺序排列(最终与起点连接)。
有什么方法可以按顺时针或逆时针方向对笛卡尔坐标列表进行排序,这样我就可以在不“举笔”的情况下从一个点到另一个点绘制我的形状?
我看到一篇文章对多边形的 4 点进行排序,但我认为这只是 4 点的特例。我的形状至少有 6 分。在列表中,每个条目都保证与其相邻的至少一个相邻(顺时针或逆时针顺序)相邻(前一点或后一点)。例如:A、B、D、C... 或 B、A、D、C... 但不是A、C、B、D...(我需要排序,所以我得到 A、B、C , D 或 D, C, B, A)。我找到了这篇文章,但似乎没有答案:将点列表排序为多边形
CPU性能是个问题。但是,即使是一个“缓慢”的解决方案,如果它易于实现和理解(对于下一个程序员),如果我能想出一个有效的缓存机制,也可能没问题。
我想附上一张图片来展示我需要做什么但还没有 10 个声望点的例子。无论如何,如果我有办法在这个多边形列表中对第三个示例的顶点进行排序,那将是完美的:http: //upload.wikimedia.org/wikipedia/commons/1/1f/Assorted_polygons.svg
我真的很感激任何和所有的帮助,谢谢!
编辑:我确实可以保证坐标系的中心点——它将是屏幕的中心。所有点都将介于 0 和屏幕宽度/高度之间(原点显然是宽度/高度 / 2)。我不能保证多边形将在其内部包含原点。这是一个罕见的例外情况,但我需要考虑它。
顺便说一句,我的片段不一定按顺序排列的原因是因为它们是使用 Conrec 生成的:http://paulbourke.net/papers/conrec/ (它们是等高线)。我使用以下命令对 Conrec 生成的轮廓线段进行排序:如何使用 Conrec 为轮廓线组装连续点的数组 现在的问题案例是地图上的外轮廓线。这些将与地图的边缘相交(即,不形成封闭的多边形)。在这种情况下,我在地图边界的边缘绘制,直到我重新连接线开始的位置(在地图的边缘)或兄弟线进入地图(重复直到我最终回到我的起点观点)。然后我可以绘制一个区域并让填充 API 工作。希望这些信息有所帮助。我认为最好的办法是生成多边形顶点的有序列表,但也许需要另一种方法。