创建穿过所有给定点的非相交多边形 [英] Create non-intersecting polygon passing through all given points

问题描述

假设我有一个随机顺序的点数组，我需要找到一个多边形(通过对它们进行排序，使得每个相邻对代表一个边)，它通过 所有 点，当然，它的边是不相交的.

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 triangulation.连续删除边界线段，直到剩下的边界可以插值所有点或不能删除更多线段.如果使用该段的三角形的所有点都在边界上，则不要删除边界段.以此边界为路径.

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.

我在 Mathematica 中使用 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屋！