关于如何识别平面内封闭区间的问题（ue4，c++）

淡淡的烟草味﹌ 2023-10-17 12:00 3阅读 0赞

**关于如何识别平面内封闭区间的问题（ue4，c++）**

问题描述：通过鼠标在平面上不断点击会得到一个线段集合S，编写一个算法，识别出其中的每一个不可分割的小的封闭区域S（i），输出每一个小区域的点集合（顺或者逆时针）。

刚开始遇到这个问题的时候查询了很多资料，都没有找到很好的办法。便先按照当有一个点等于第一个点的时候作为判断封闭区域的条件。这样一想便知只能个一个区域一个区域的实现，不能达到想要的效果。不过好在最后还是解决了问题。

**程序思路：**

**①：**得到线段我们的线段集合S（本次项目鼠标点击得到线段（p1，p2两点）已经在ue4蓝图里面实现，这一步就不过多阐述）

**②：**移除孤立的线段（两端的点都是孤立的）；

**③：**拆分所有的线段（就是将所有的相交线线段拆分开，得到新的线段集合S）

**④**：移除一个端点孤立的线段（一个端点孤立的线段是不构成多边形的）

**⑤：**找出所有的大区域线段集合M，M是线段集合的集合，二维数组；（这里的大区域指的是：以任意一条线为起点找到和它相交的其他线段，再找到和这些线段相交的其他线段，直到找不到相交线段，那么这些线段的集合就是一个大区域Mi。然后找完所有的大区域）

**⑥：**分别对每一个大区域进行封闭区域的提取。

**怎么从大区域中提取封闭区域，这个问题比较棘手，我们可做如下思考**

**第一：循环查找封闭区域**

如何找到下一条线段和封闭区域比较关键：首先以大区域任意一条线段L作为初始线段，以L线段的p2为起始点。然后找到连接该条线段p2点的所有其它线段集合f。（注意这里需要确保f中所有线段的p1点等于L的p2点，方便提取封闭区域点就是所有的p2点，所以找到其它线段时如果是p2点等于L的p2，应将找到的线段p1和p2对调一下）；

找到L（p2p1向量）按照顺时针旋转最小（最大）角度到f中的线段L‘（p1p2向量），记录这条线段添加到Q中，然后以L’作为新的起始线段重复这一步骤；直到找回到L；集合Q可能为我们要找的封闭区域）

**第二：找出的区域有哪几种情况？**

上述区域Q中其实有几种情况，如果以外边界线用作起始线段L，那么可能会找到一个大的外框，或者我们需要的小框（这和我们取旋转角度有关，最小和最大角度，一定有一个会对应一个外边框。比如‘田’字这样的区域）；如果以内线段用作起始线段L，那么最大和最小角度都会是一个我们需要的小封闭区域；

**第三：顺时针最小（最大）角度计算**

我用的是向量法，假设其实线段向量（p2p1向量）为a；下一条线段（集合f里的一条线p1p2向量）为b。先计算ab夹角α。那么a到b的顺时针角度可以这么计算a叉乘b如果小于零顺时针角度就是α，大于零角度就为2pi-α；等于零时判断两向量的方向：反向时角度为pi，同向时角度为0；

**第四：判断封闭区域是否为最小封闭区域**

是不是最小封闭区域可以根据该打区域内其它的线段的中点进行遍历，看剩余的线段的中点是否在该封闭区域内部，本次采用射线法判断。（点是否在多边形内部，可以用射线法，面积法，内角和法等等，可在网上查寻）。

**第五：思考一条线段最多能参与几次封闭区域提取？**

这个问题比较好判断，以‘田’字模型为例，针对内部线段，线段最多可能参与2个封闭区域提取，针对最外层边框最多参与1个封闭区域提取。

**第六：减法思想，找出外边框定义线段的属性num初始计数**

1：定义所有线段初始num计数为2，外边框初始计数为1。

2：外边框查找：需要找到外边界线为其实线段，外边界线可由外边界点得到，外边界点（也叫凸点）就是最值点，它是x或y最大或者最小点都可以。然后找到连接该点的所有线段，取一条作为初始线默认以最小顺时针角度，得到多边形，若不是外边框，就以最大角度找若还不是，那么换下一条线段做起起始线段，总会找一个外边框。如果找完找不到外边框那么这个肯定是一个“口”字形类似的内部无其它线段的区域那么这个多边形就是外框；

3:找到一个外框后将这个外框所有的线段的num计数改为1；

4：思考我们的大区域中是否会包含多个外边界框呢？答案是肯定的。所以我们经过3之后并没有全部找完所有的外边界框（比如‘口^口’这样的大区域）。那么我们可以继续寻找外边界框：从该大区域中移除找到的外边界框线段，由于移除后大区域可能又会产生新的孤立线段，所以进行步骤②④，再找下一个外边界框，直到大区域内无线段，这样大区域所有外边框都被我们找到了并全部定义好了num初始计数。

通过以上分析上诉中第⑥步可分为以下几步来实现：

**⑥\[1\]：**定义每一条线段的初始计数num为2，找到大区域里面的所有外边框线段集合，将它们的计数num改为1；

**⑥\[2\]：**对定义num后的大区域进行提取小封闭区域，取任意线段为起始线段默认最小顺时针角度找到封闭区域并记录。将该封闭区域里面的所有线段的num-1，判断将num==0的线段移除，进行步骤②④；然后重复提取小区域，直到大区域里面没有线段

**⑥\[3\]：**对每一个大区域提取小区域完后将各个小区域的所有线段的p2点作为输出，即为我们想要的数据；

如图是[简单的html测试][html]：[平面封闭区域提取][html]

![56671b55be9942f69e7b9e0e826c5ef8.jpeg][]

![6e999084d0094cf48e8ee60c4c64b5a0.jpeg][]

关于识别平面（xy平面）封闭区间就是这样简单，有点绕，但是仔细理解后就会觉得比较简单。本文没有做图，希望读者能根据描述，亲自动手画一画、想一想。[参考代码][Link 1]是初学c++时所作，代码风格极为不规范，逻辑也比较混乱，不建议直接copy！

[html]: http://1.14.71.218/%E5%B9%B3%E9%9D%A2%E5%B0%81%E9%97%AD%E5%8C%BA%E5%9F%9F%E6%8F%90%E5%8F%96.html
[56671b55be9942f69e7b9e0e826c5ef8.jpeg]: https://img-blog.csdnimg.cn/56671b55be9942f69e7b9e0e826c5ef8.jpeg
[6e999084d0094cf48e8ee60c4c64b5a0.jpeg]: https://img-blog.csdnimg.cn/6e999084d0094cf48e8ee60c4c64b5a0.jpeg
[Link 1]: https://download.csdn.net/download/qq_22824481/9794987?spm=1001.2014.3001.5503