有效性算法用于创建一个非自相交多边形 [英] Validity of algorithm for creation of a non self-intersecting polygon

问题描述

作为一个扩展和部分答案我的线程我写了一个简单的给定一个点的集合（与XY坐标）算法可以形成一个非自相交多边形

As an extension and partial answer to my thread I wrote a simple algorithm that given a set of points(with xy coordinates) can form a non self-intersecting polygon.

要求：给定任意一组以不同的点的坐标总是可能构造一个规则或不规则的，非自相交多边形

Claim: Given an arbitrary set of points with different coordinates it is always possible to construct a regular or irregular, non self-intersecting polygon.

的算法：

假定有一个包含所有顶点的集合V

Assume there is a set V containing all the vertices

1）排序的所有V中的顶点由X坐标

1) Sort all vertices in V by x-coordinate

2）想象直线（我们将称之为除法）平行于x轴而从第一节点开始扩展到无限大并除以/分割的顶点成两组

2) Imagine a straight line (we'll call that "the divider") parallel to the x-axis which starting from the first node expands to infinity and divides/splits the vertices into two sets.

3）现在考虑两组：

A =以上或在分隔线的集合中的所有顶点

A = The set of all vertices above or on the divider line

B =集合所有剩余顶点

B = The set of all remaining vertices

4）处开始的最左边的顶点连接A中的所有顶点，直到你到最右边的

4) Starting at the leftmost vertex of A connect all vertices in A until you get to the rightmost

5）如果有序集合V​​（与最大的x坐标的顶点最右边顶点）不在一个连接的最后一个顶点（A的最右边）与它。

5) If the rightmost vertex of the sorted set V (the vertex with the biggest x coordinate) is not in A connect that last vertex (rightmost of A) with it.

6）和向后从有序集合V​​（与最大X顶点的最右边顶点开始坐标）连接所有的都在B中的顶点工作

6) Work backwards and starting from the rightmost vertex of the sorted set V (the vertex with the biggest x coordinate) connect all the vertices that are in B

7）将第一个（最左边的顶点的B）的B与A的最左边的顶点顶点

7)Connect the first (leftmost vertex of B) vertex of B with the leftmost vertex of A

我觉得算法是正确的，并不能找到一个测试，它会失败，但也许我失去了一些东西。

I think that the algorithm is correct and can't find a test that it would fail but maybe I'm missing something.

我会AP preciate它，如果你可以看看，并给我那就没办法了一个例子，如果有任何的（我敢肯定，一定有）。

I would appreciate it if you could have a look and give me an example that wouldn't work if there is any(which I'm sure there must be).

推荐答案

我不知道我理解正确你想要做的事。在其他线程，并在<一href="http://math.stackexchange.com/questions/26373/center-of-gravity-of-a-self-intersecting-irregular-polygon/26374">the在math.SE （这把我带到这里）对应的线，你说你有一个多边形，并试图寻找它的重心。在这里，你说你有一组点，你想从它构造一个不相交的多边形。这是两个完全不同的事情。正如我在math.SE提到的，如果多边形不知道是凹凸有致，一组点的不唯一确定一个多边形的 - 所以你在这里提出的算法可以构建一些任意的非自相交多边形（我的天堂'吨检查是否成功地做了），但是这可能会或可能不会承担任何有关的多边形你最初在，或者有兴趣的我误解你的问题在​​math.SE，你实际上只具有一定的点，要建构随便一个非自相交从他们多边形并不在意，可能有几种不等价的解决方案呢？

I'm not sure I understand correctly what you're trying to do. In the other thread, and in the corresponding thread at math.SE (which brought me here), you said you had a polygon and were trying to find its center of gravity. Here you say you have a set of points and you want to construct a non-intersecting polygon from it. Those are two quite different things. As I mentioned at math.SE, if the polygons are not known to be convex, a set of points doesn't uniquely define a polygon -- so the algorithm you propose here may construct some arbitrary non-self-intersecting polygon (I haven't checked whether it successfully does that) but that may or may not bear any relation to the polygon you were originally interested in. Or did I misunderstand your question at math.SE and you actually only have some points and want to construct just any non-self-intersecting polygon from them and don't care that there may be several inequivalent solutions for this?

这篇关于有效性算法用于创建一个非自相交多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！