在所有给定的点创建不相交的多边形传递 [英] Create non-intersecting polygon passing through all given points

问题描述

假如我有以随机顺序点的数组，我需要找到一个多边形（通过对它们进行排序，使得每个相​​邻的一对重presents侧）穿过所有之分，并且其两侧都是非相交当然

Suppose I have an array of points in random order, and I need to find a polygon (by sorting them, such that every adjacent pair represents a side) which passes through all of the points, and its sides are non-intersecting of course.

我试图通过选择一个点，并加入所有点到最后阵列低于它这样做，排序从左到右。然后，加入它们之上的所有点，排序从右到左。

I tried to do it by selecting a point, and adding all points to the final array which are below it, sorted left to right. Then, adding all points which are above it, sorted right to left.

我被告知，我可以添加额外的点和排序自然，避免自交..我无法弄清楚，虽然。什么是一个简单的方法来做到这一点？

I've been told that I can add an additional point and sort naturally to avoid self-intersections.. I am unable to figure out that though. What's a simple way to do this?

推荐答案

正如有人所说，最小长度的解决方案是完全旅行商问题。这里有一个非最佳，但可行的方法：

As someone said, the minimal length solution is exactly the traveling salesman problem. Here's a non-optimal but feasible approach:

计算一个贵点Delauney三角。先后删除边界节段，直到你只剩下了所有插值点或没有更多的部分可以被删除的边界。请不要删除边界段，如果是在边界上的三角形使用该段的所有点。就拿这个边界，你的路径。

Compute a Delauney triangulation of your points. Successively remove boundary segments until you are left with a boundary that interpolates all points or no more segments can be removed. Don't remove boundary segments if all points of the triangle using that segment are on the boundary. Take this boundary as your path.

我用40个随机点实现了这个在数学。下面是一个典型的结果：

I implemented this in Mathematica using 40 random points. Here is a typical result:

最明显的反对意见是，你可能会得到一个点，不是所有的点是边界点，但不使边界自相交无法删除的边界段。这是一个有效的异议。我花了几十奔跑，看看这发生的情况，但最后得到这个案例：

The obvious objection is that you might get to a point where not all your points are boundary points, but you can't remove a boundary segment without making the boundary self intersecting. This is a valid objection. It took me dozens of runs to see a case where this happened, but finally got this case:

您很可能会看到使用本地拓扑固定这样一些明显的方式，但我会离开的细节给你！这可能有助于一件事是边缘翻转，你需要共享一个侧面，说三角形（P，Q，R）和（Q，P，S）两个三角形，并与（R，P，S）和替换（ R，S，Q）（逆时针所有坐标周围的三角形）。这可以，只要在这一转变所得的三角形也逆时针下令进行。

You can probably see some obvious ways of fixing this using the local topology, but I'll leave the details to you! One thing that might help is "edge flipping" where you take two triangles that share a side, say triangle (p,q,r) and (q,p,s) and replace them with (r,p,s) and (r,s,q) (all coordinates counterclockwise around the triangle). This can be done as long as the resulting triangles in this transformation are also counterclockwise ordered.

要减少所需的修复起坐，你将要做出的段不错的选择，以消除在每一步。我用的边界段的长度的比率到候选三角形（由潜在入射点与段形成的三角形）的另一侧的长度之和

To reduce the need for fix-ups, you will want to make good choices of the segments to remove at each step. I used the ratio of the length of the boundary segment to the sum of the lengths of the other side of the candidate triangle (the triangle formed by the potentially incoming point with the segment).

这篇关于在所有给定的点创建不相交的多边形传递的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！