如何在简单的非凸多边形中对顶点进行排序 [英] how to order vertices in a simple, non-convex polygon

问题描述

我有一个问题，我有一个简单的非凸多边形的一系列点（我希望我的术语是正确的）。但是这些要点并不一定按顺序（即顺时针或逆时针）。对于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的工作。希望这些信息有帮助。我认为最好的办法是生成一个多边形顶点的有序列表，但可能需要另一种方法。

解决方案

也许你的意思是多边形是凸的（即它是非凹的）。否则，我不认为你在做什么实际上是可能的（可以有多种方法来加入点并形成一个多边形）。

一种技巧I可以想到在这种情况下：
首先，列表中的前两项必须按照您提供的规则形成边缘。
然后尝试添加顶点，因为它们以列表顺序出现;在每种情况下，如果结果只能为凹形，请从结果列表中删除前一个元素，然后暂时忽略它。一旦你浏览了源列表，如果你仍然跳过顶点，继续跳过这些跳过的顶点。

编辑：只是从维基百科看你的例子，而你 do 是指非凸的。我不认为这是可能的。

I have a problem where I have a series of points for a simple, non-convex polygon (I hope I have the terminology correct). But the points are not necessarily in order (ie, clockwise or counterclockwise). For Flash's drawing API to correctly draw a fill area, I need to have these points progress in order around the edge (to finally connect with the starting point).

Is there some way I can sort my list of Cartesian coordinates in either clockwise or counterclockwise direction so I can draw my shape from point to point without "lifting the pen"?

I saw one post for sorting 4-points of a polygon, but I think it was a special case only for 4 points. My shapes have at minimum 6 points. In the list, each entry is guaranteed to be adjacent (in either clockwise or counterclockwise order) to at least one of its neighbors (either the previous point or the following). For example: A, B, D, C... or B, A, D, C... but not A, C, B, D... (I need to sort so I get either A, B, C, D or D, C, B, A). I found this post, but it appears to be unanswered: Sort point list into polygon

CPU performance is an issue. But even a "slow" solution, if it is easy to implement and understand (for the next programmer) might be ok if I can come up with an effective cache mechanism.

I would like to attach a picture to show an example of what I need to do but do not yet have 10 reputation points. Anyway, if I had a means for sorting the vertices of the 3rd example in this list of polygons, that would be perfect: http://upload.wikimedia.org/wikipedia/commons/1/1f/Assorted_polygons.svg

I really appreciate any and all help, thank you!

EDIT: I can indeed guarantee a center point for the coordinate system--it will be the center of the screen. All points will be between 0 and Screen Width/Height (origin is obviously Width/Height / 2). I cannot guarantee that the polygon will contain the origin point in its interior. It is a rare case exception, but I need to account for it.

By the way, the reason my segments are not necessarily in order is because they are generated using Conrec: http://paulbourke.net/papers/conrec/ (they are contour lines). I order the contour line segments generated by Conrec using the following: How to assemble an array(s) of continuous points for a contour line using Conrec The problem case now is for the outer contour lines on a map. Those will intersect with the edge of the map (ie, not form a closed polygon). In this case, I have draw around the edge of the map bounds until either I re-connect with where the line started (on the edge of the map) or a sibling line enters the map (repeating until I eventually get back to my starting point). Then I can draw an area and get the fill API to work. Hope this information helps. I assumed the best thing to do would be to generate an ordered list of polygon vertices, but perhaps another approach is called for.

解决方案

Perhaps you mean that the polygon is convex (i.e. it's non-concave). Otherwise I don't think what you're doing is actually possible (there could be multiple ways to "join the dots" and form a polygon).

One technique I can think of in that case: First, the first two items in the list must form an edge, by the rules you give. Then try adding vertices as they appear in list order; in each case, if the result could only be concave, remove the previous element from the result list and ignore it for now. Once you have gone through the source list, if you still vertices that you skipped over, continue for those skipped vertices.

Edit: Ok, just looked at your example from wikipedia, and you do mean non-convex. I don't think it's possible unfortunately.

这篇关于如何在简单的非凸多边形中对顶点进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！