1

我有一个问题,我有一系列简单的非凸多边形的点(我希望我的术语是正确的)。但这些点不一定是按顺序排列的(即顺时针或逆时针)。为了让 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 工作。希望这些信息有所帮助。我认为最好的办法是生成多边形顶点的有序列表,但也许需要另一种方法。

4

4 回答 4

1

我正在考虑一种O(n^2)算法:
由于您有绘制点的顺序(希望如此),因此您知道每条边的端点。
选择一个点开始,然后继续直到与另一条边相交。
然后你标记那个点,继续在新的边缘,直到你到达另一个边缘或端点。每当您到达更改边缘的点时,将其列出。一旦你到达起点,你就完成了。

于 2011-04-04T01:59:58.200 回答
0

好吧,你不会喜欢它,但这是不可能的。如果您考虑删除演示多边形中的所有线,您可以以不同的方式连接它们并且仍然具有有效的非凸多边形,那么排序应该如何知道该走哪条路?这就是非凸多边形的糟糕之处。

于 2011-04-04T01:56:34.760 回答
0

也许你的意思是多边形凸的(即它是非凹的)。否则我不认为你正在做的事情实际上是可能的(可能有多种方法可以“连接点”并形成一个多边形)。

在这种情况下我能想到的一种技术:首先,列表中的前两项必须根据您给出的规则形成一条边。然后尝试添加以列表顺序出现的顶点;在每种情况下,如果结果只能是凹的,则从结果列表中删除前一个元素并暂时忽略它。浏览完源列表后,如果您仍然跳过了顶点,请继续处理那些跳过的顶点。

编辑:好的,刚刚从维基百科看你的例子,你意思是非凸的。不幸的是,我认为这是不可能的。

于 2011-04-04T01:59:03.730 回答
0

一个表明问题不是唯一可解的简单示例是点 a=(0,0), b=(2,0), c=(1,1), d=(1,2); 每个订单 (a,b,c,d,a), (a,b,d,c,a) (a,c,b,d,a) 都是简单的多边形。

于 2011-04-05T13:02:31.297 回答