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

Question

我有随机排列的任意数量的多边形（在这种情况下为十六进制），但它们都接触另一个十六进制。

每个单独的十六进制有 6 个 x,y 顶点。顶点以所有六边形而闻名。

谁能指出我将所有六边形组合成一个多边形的算法的方向？本质上，我只是在寻找一个函数，它可以吐出一组顶点位置，这些顶点位置的排序方式是，在从一个到下一个绘制线条时，它会形成多边形。

到目前为止，这是我的方法：

1. 为所有六边形创建所有顶点的数组。
2. 确定顶点在数组中出现的次数
3. 如果顶点在数组中出现 3 次以上，则从数组中删除顶点。
4. 如果顶点在数组中出现 2 次，则删除其中之一。

下一步很棘手。我正在使用画布绘制这些多边形，这实际上涉及从一个顶点到下一个顶点绘制一条线。所以最终数组中顶点的顺序很重要。不能随意排序。

另外，我不是在寻找“凸包”算法，因为它不会正确绘制多边形。

是否有任何功能可以做这样的事情？我是在正确的轨道上还是有更好更有效的方法？

Answer 1

我会做这样的事情：

1. 列出所有方面。边由两对坐标定义。
2. 如果任何一方出现不止一次，则删除该方的所有实例。
3. 选择任意一侧，并从该一侧选择其中一个点。
4. 将该点放在一个数组中。
5. 跟随当前一侧并将另一点放入数组中。
6. 删除你刚刚关注的那一边。
7. 然后找到与数组中最后一个点相同的点的另一边。这样的一方只会有一个。如果没有，你就完成了。
8. 返回第 5 步。

您现在应该有一组点，这些点按顺序组成您想要的形状。

请注意，这不会处理漏洞。形状必须可由单个路径定义。

Answer 2

对于每个十六进制，您都有一个包含 6 个顶点的列表。如有必要，对列表进行排序，以便顶点按逆时针顺序排序（这是数学约定）。

现在你有一组多边形（最初是六边形）。这个想法是组合多边形直到只有一个（或尽可能少）。

选择多边形的一条边，并在其他多边形中寻找同一条边（即同一对顶点）。如果有两个实例，则在该边合并两个多边形，例如 (a, b, c, d, e, f) + (g, h, d, c, i, j) => (a, b, c , 我, 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) => 没有。

一旦你消除了重复的边缘，就会有一个多边形逆时针外边缘的列表，可能还有一个或多个孔的顺时针内边缘列表。

Answer 3

如果不跟踪构成线条的坐标对，就不可能确定形状的外边界

如果你知道组成线条的坐标对，那么

1. 创建2个列表，顶点之一（列表1），行之一（列表2）
2. 从顶点列表中删除所有重复的顶点
3. 为所有附有 3 行的顶点创建一个新列表（列表 3）
4. 使用列表 3，从列表 3 中删除所有具有 2 个顶点的线作为它们的两个坐标对
5. 是时候遍历形状了，剩余的线条列表应该形成您想要的形状，只需从任意坐标开始，然后对于所有线条的每个坐标，如果 (x1,y1) = 当前坐标，然后将 (x2,y2) 添加到堆栈并从列表中断中删除该行 elseif (x2,y2) = 当前坐标，然后将 (x1,y1) 添加到堆栈并从列表中断中删除该行