c# - 在C#中合并非重叠多边形的简单算法

Question

我正在尝试实现一个简单的算法来合并一些多边形。多边形不重叠，我需要的算法根本不需要高效。我正在寻找最简单的算法。

我的问题是多边形 10,9 和 6。如您所见，多边形 10 和 9 在合并之前与 6 不相邻。因此，如果 9 和 5 在 9 和 10 之前合并，则 6 将没有任何机会与 10 和 9 合并。但是如果我先合并 10,9，我将能够将最终的多边形与 10 合并。怎么可能我解决这个？

Answer 1

如何合并边缘重叠的形状？

• 提取所有形状的所有边

• 对边进行排序

  • 先按梯度，

  • 然后根据 y 值，如果延伸那么远，该边缘将穿过 x 轴
    (如果它平行于 y 轴，则按 x 值)，

  • 然后是边缘的最小 y 端点(或者最小的 x 点，如果它平行于 x 轴)。

• 遍历边缘

  • 前两个排序条件只是为了剔除不重叠的边(我们本质上可以认为那些不符合前两个排序条件的边存储在不同的数据结构中)。

  • 对于第三个条件，执行以下操作:

    如果这条边在前一条边的终点之前开始(前两个条件相同)，则合并形状(如果它们尚未合并)。

示例:

我们分割水平和垂直边缘。

然后我们对水平边进行排序，使得 3-10 上的所有边(3-1、1-2、2-11 等)彼此跟随，然后是 7-9 上的边，然后是 2 上的边-6(请记住，我们首先按它们的 y 值排序，因为如果将它们扩展到 x 轴，它们在那里将具有相同的 y 值，然后我们按最小的 x 端点排序)。

然后我们对垂直边进行排序，使 2-3(2-7 和 7-3)上的边相互跟随，然后是 14-1，然后是 5-2 边，等等(请记住它们平行于 y 轴，所以我们先取它们的 x 值，然后按最小的 y 端点排序)。

请记住，像 14-1 这样的边会出现两次，因为它同时是 10 和 9 的边，我们将有边 7-8、7-14 和 14-8。

现在我们遍历边缘:

我们以 3-1 开局。它没有先前的优势，所以我们什么都不做。 1-2 在其前一个边缘 (3-1) 之后开始，所以我们什么都不做。对于 2-11、11-41、41-19 和 19-10 也是如此。

然后是 7-8。没有以前的优势，所以什么都不做。然后我们做7-14。自 7 < 8 ，我们合并相应的形状 10 和 6。

等等。