在逆时针订购CONCAVE多边形顶点？ [英] Ordering CONCAVE polygon vertices in (counter)clockwise?

问题描述

我有一组可能形成凹多边形的无序顶点。现在，我想按顺时针或逆时针顺序对其进行排序。

。也就是说，有许多启发式算法通常可以找到即使他们不能总是保证找到的解决方案是真正的最小值，也可以很快找到一个近乎最优的解决方案。

I have a set of disordered vertices that may form a concave polygon. Now I wish to order them in either clockwise or counterclockwise.

An answer here suggests the following steps:

• Find the polygon center
• Compute angles
• Order points by angle

This is obviously only for convex polygon and will fail when the points form a concave one.

How may I do this to a concave one?

I am using Python, but welcome all generic answers.

解决方案

In general, your problem seems ill-defined. For example, given the following set of vertices:

 

which of these non-convex polygons would you consider to be the "correct" way to connect them?

     

Now, obviously, there are various possible criteria that you could use to choose between different possible orders. For example, you might want to choose the ordering that minimizes the total length of the edges, which should yield fairly "reasonable" results if the points do, in fact, lie fairly close to each other on the boundary of a simple polygon:

 

Unfortunately, for a general set of points, finding the ordering that minimizes the total edge length turns out to be a well known NP-complete problem. That said, there are many heuristic algorithms that can usually find a nearly optimal solution quickly, even if they can't always guarantee that the solution they find is the true minimum.

这篇关于在逆时针订购CONCAVE多边形顶点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！