将任意数量的多边形组合在一起

Question

将任意数量的多边形组合在一起

algorithmhexpolygonhexagonal-tiles

4

我有许多任意的多边形（在这种情况下是六边形），它们随机排列，但它们都与另一个六边形相接触。

每个单独的六边形都有6个x，y顶点。所有六边形的顶点都已知。

有没有人可以指导我一个算法，将所有六边形合并成单个多边形？本质上，我只是在寻找一个函数，该函数输出一个顶点位置数组，以一种使得从一个顶点到下一个顶点绘制线条时，形成多边形的方式进行排序。

到目前为止，我的方法如下：

1.创建所有六边形的所有顶点的数组。

2.确定顶点在数组中出现的次数。

3.如果顶点在数组中出现3次或更多次，则从数组中删除该顶点。

4.如果顶点在数组中出现2次，则删除其中之一。

然而，下一步十分棘手。我使用画布来绘制这些多边形，这本质上涉及从一个顶点到下一个顶点绘制线条。因此，最终数组中的顶点顺序很重要。它不能任意排序。

此外，我不需要“凸包”算法，因为那样无法正确绘制多边形。

是否有任何函数可以做到这一点？我是否在正确的轨道上，还是有更好、更有效的方法？

- Jake Wilson

1

关于一个有洞的大多边形，你想怎么处理？两个（或更多）顶点列表是否足够？ - Beta

假设所有六边形都相互接触，没有空洞。 - Jake Wilson

3个回答

0

如果不跟踪构成线条的坐标对，将无法确定形状的外边界

如果您知道构成线条的坐标对，则

创建两个列表，一个是顶点（列表1），一个是线条（列表2）
从顶点列表中删除所有重复的顶点
创建一个新列表（列表3），其中包含所有连接有3条线的顶点
使用列表3，删除其两个坐标对为列表3中顶点的所有线条
现在是遍历形状的时候了，剩下的线条列表应该形成您想要的形状只需从任意坐标开始，然后对于每个坐标对于所有线条如果（x1，y1）=当前坐标，则将（x2，y2）添加到堆栈中并从列表中删除该线条打破否则，如果（x2，y2）=当前坐标，则将（x1，y1）添加到堆栈中并从列表中删除该线条打破

- Andy Strackbein

0

对于每个六边形，您都有一个由6个顶点组成的列表。如果需要，请对列表进行排序，以便按逆时针顺序（这是数学约定）排序顶点。

现在您有一组多边形（最初为六边形）。想法是将多边形组合在一起，直到只剩下一个（或尽可能少的）。

选择多边形的一条边，并在其他多边形中寻找相同的边（即相同的顶点对）。如果有两个实例，请在该边缘处组合两个多边形，例如(a, b, c, d, e, f) + (g, h, d, c, i, j) => (a, b, c, i, j, g, h, d, e, f)。（如果两个顶点在两个多边形中以相同的顺序出现，或者如果边缘有三个或更多实例，则报告错误并中止。）遍历所有边缘。如果六边形确实形成了连续的组，那么只会剩下一个多边形。

多边形可能有重复的边。如果一条边出现了多次，可以通过将列表分成两部分来消除它，例如 (a, b, c, d, b, a, e, f, g) => (b, c, d) + (a, e, f, g)。或者如果这些边是相邻的，则删除它们：(a, b, c, b, d, e) => (a, b, d, e)。或者如果该列表只有一个边缘，则删除该列表：(a,b) => 无。

一旦消除了重复的边，就会有一个列表用于多边形逆时针外边缘，以及一个或多个列表用于顺时针内部孔的边缘。

- Beta

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Niet the Dark Absol · Accepted Answer

我会这样做:

列出所有的边。一条边由两对坐标定义。
如果任何一条边出现多次，则删除该边的所有实例。
选择一条任意的边，并从该边选择一个点。
将该点放入数组中。
跟随当前边并将另一个点放入数组中。
删除你刚刚跟随的那条边。
然后找到另一条具有与数组中最后一个点相同的点的边。只会有一条这样的边。如果没有，那么就完成了。
回到步骤5。

现在，您应该拥有按顺序构成所需形状的点数组。

请注意，这不能处理孔洞。该形状必须由单个路径定义。