一种在C#中合并不重叠多边形的简单算法

Question

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

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

​

​

Answer 1

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

• 提取所有形状的所有边缘
• 将边缘排序

- First by gradient,
- Then by the y value where that edge would cross the x-axis if extended that far

(如果它与y轴平行，则按x值表示)，

-然后是边的最小y端点(如果它与x轴平行，则由最小的x点)。

​

• 遍历边缘

- The first two sorting criteria are just to eliminate non-overlapping edges (we can essentially consider those not matching the first two sorting criteria to be stored in a different data structure).
- For the third criteria, do the following:

如果此边缘在前一个边缘结束之前开始(具有相同的前两个条件)，则合并这些形状(如果它们尚未被合并)。

​

示例：

​

​

我们把水平和垂直的边缘分开。

然后对水平边进行排序，使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合并。

诸若此类。