本文涉及知识点数学 几何1 线段求交两个网络的叠合而言对应的几何条件是这样的给定由线段组成的两个集合计算出来自于其中一个集合的所有线段与另外一个集合的所有线段之间的交点。线段是闭的一个集合的线段端点在另外一个集合的线段上也认为是交点。某算法其运行实际不仅取决于输入中的线段数目还去取决于实际的)交点数目。这样的算法称为输出敏感的算法。下面的平面扫描算法plane sweep algorithm就是输出敏感算法也称交点敏感算法。线段求交假定没有线段部分或完全重合预处理的时候合并掉。暂时规定没有水平直线。暂时规定没有三条直线交于一点。令maxy 等于所有线段端点y的最大值miny等于所有线段端点的最小值。C ( y 0 ) 记录所有直线 y y 0 相交的线段这些线段以和 y y 0 交点的横坐标升序排序 C(y_0)记录所有直线yy_0相交的线段这些线段以和yy_0交点的横坐标升序排序C(y0​)记录所有直线yy0​相交的线段这些线段以和yy0​交点的横坐标升序排序。令存在交点 ( x 1 , y 1 ) y 1 小于 y 0 且最大。 令存在交点(x1,y1)y1小于y0且最大。令存在交点(x1,y1)y1小于y0且最大。如果没有线段交点的纵坐标y在[ y 1 , y 0 ] , 则 ( x 1 , y 1 ) 所在的直线一定在 C ( y 0 ) 中相邻 [y_1,y_0],则(x_1,y_1)所在的直线一定在C(y_0)中相邻[y1​,y0​],则(x1​,y1​)所在的直线一定在C(y0​)中相邻。令任意一条青色线与y y 0 和 y y 1 分别交于 p 0 , p 1 。显然 p 0 属于红白组成的三角线 p 1 属于黄白梯形或紫白梯形 yy_0和yy_1分别交于p_0,p_1。显然p_0属于红白组成的三角线p1属于黄白梯形或紫白梯形yy0​和yy1​分别交于p0​,p1​。显然p0​属于红白组成的三角线p1属于黄白梯形或紫白梯形。故青线必定和公共界限(白线相交)且y y 0 , y y 1 yy_0,y y_1yy0​,yy1​。中间的青线交点相同如果没有边上的两根青色线青线和白色线相邻。暂时规则两条直线交于( x 0 , y 0 ) (x_0,y_0)(x0​,y0​)马上交换位置。当y变化成y 2 y_2y2​时C不一定会变化以下三种情况会变化除这三种情况下不会变化。一存在一个纵坐标为y 2 y_2y2​的上端点。二存在一个纵坐标为y 2 y_2y2​的下端点。二存在一个纵坐标为y 2 y_2y2​的交点。线段端点中y大的上端点y相同则x小的是上端点。C称为状态status上端点、下端点、交点称为事件点。实现细节有序集合映射)不支持交换所以只能删除再增加。有序集合映射不能记录各线段与扫描线的交点的横坐标否则扫描线发生变化时所有的横坐标都可能发生变化。有序集合记录所有线段的下标然后自定义比较函数比较函数和扫描线的纵坐标有关。有序集合很多操作都依赖于有序自定义比较函数后不再保证有序。故更改扫描线时必须保证更改扫描线后有序集合仍然有序。更改扫描线时只有交点在扫描线的线段顺序会发生变化。一故更改扫描线前先删除交点所在线段。更改扫描线后全部加回来。二增加上端点。三如果有水平线判断水平线的交点交点直接进结果不进入事件队列。四删除端点。五status删除点时判断左右邻居是否有交点。status增加点时判断此线段是否有交点。交点的y小于扫描线的纵坐标则入队列。对于平面上任意n条线段组成的集合S求交点的算法是O(nlognIlogn)。I是交点的数量。平面扫描线算法也支持y单调的曲线。事件堆大根堆的元素是扫描线事件大小和y的大小相同。扫描线事件由4部分组成一y。二上端点的x集合。三下端点的x集合。四交点的x及对应的线段。2 双向链接边表(doubly-connected edge list)又称半边结构图的平面嵌入而导出的平面子区域划分。原图中每个节点(node)的嵌入称为一个顶点(vertex)。原图中每条弧(arc)的嵌入称为一条边(edge)。本文只考虑所有弧是直的。我们把边看成开的也就是不包括线段的两个端点(也就是子区域划分的顶点)。给定一个子区域划分其中所谓的“面(face)指的是在平面上除去所有的顶点和所有的边之后余下的每一个极大的连同子集。按此定义每个面都是一个开集。若某个顶点是某条边的端点就说这个顶点与这条边是关联的。一张面与其边界上的每条边也是关联的一张面与其边界上的每个顶点也是关联的。设计的数据结构双向链接边表必须一围绕指定的某张面沿其边界遍历一周。二指定一条公共边后通过与其相邻于一侧的面找到另一侧的那张面。三给定一个顶点之后依次枚举出与之关联的所有边。对于任一子区域划分与之对应的双向链接边表为其中的每张面、每条边和每个顶点都设置了一个记录。总而言之在每个记录中不仅存在有几何的、拓扑的信息而且还有一些附加信息。如对应子区域的植被类型。附加信息也被称为属性信息。为了能够沿逆时针方向围绕某张面遍历一周可在每条边对应的记录)中存储一个指针指向下一条边。为了反方向访问存储前一条边的指针。通常每条边都隶属于两张面的边界因此还需要为各边配备一对指针分别指向与之关联的两张面。将每条边的两端分别视为一条半边(halof-edge)这样任何一条半边都有唯一的一条后继半边唯一的一条前驱半边。每条半边就只隶属唯一一张面的边界。每条边都被分成两条半边它们互为孪生兄弟(twin)。为每条半边指定后继半边的原则后继半边的方向应该能够逆时针遍历其对应的面。若一条半边e ⃗ 起于 v 终止于 w 则 T w i n ( e ⃗ ) 起始于 w 终止于 v 。 \vec e起于v终止于w则Twin(\vec e)起始于w终止于v。e起于v终止于w则Twin(e)起始于w终止于v。若是空洞则按顺时针访问其边界。双向链接边表由三组记录构成一组对应顶点一组对应于面还有一组对应于半边。这些记录中分别存有下列几何的及拓扑的信息。顶点v的记录。存放顶点坐标。指向以v为起点的某一条半边。面f的记录。指向改面外边界的任意一条半边。若是无界面则为空。多个指针每个指针指向空洞边界的边。半边e ⃗ \vec ee的记录。改半边的起点孪生半边所在的面。前驱半边后驱半边。下图有两个区域一无穷区域扣除洞ADCB。二矩形ABCD。3 计算子区域划分的叠合给定两个子区域划分S 1 和 S 2 且叠合 O ( S 1 , S 2 ) 也是一个子区域划分。 S_1和S_2且叠合O(S_1,S_2)也是一个子区域划分。S1​和S2​且叠合O(S1​,S2​)也是一个子区域划分。O ( S 1 , S 2 ) 有一张面 f 当且仅当在 S 1 , S 2 中分别存在面 f 1 和 f 2 使得 f 是 f 1 ∩ f 2 中的一个极大连通字集 O(S_1,S_2)有一张面f当且仅当在S_1,S_2中分别存在面f_1和f_2使得f是f_1 \cap f_2中的一个极大连通字集O(S1​,S2​)有一张面f当且仅当在S1​,S2​中分别存在面f1​和f2​使得f是f1​∩f2​中的一个极大连通字集。利用前面章节的平面扫描线求交点当交点的边不属于同一个子区域划分时则对双向链接边表D做调整。我们只讲解一种情况。S 1 的一条边穿过 S 2 的一个顶点 v S_1的一条边穿过S_2的一个顶点vS1​的一条边穿过S2​的一个顶点v。e对应的两条半边变成4条。要生成两个以v为起点的半边记录。如何寻找后继半边以逆时针为例逆时针半平面旋转弧度最大的就是后继边不包括180∘ ^\circ∘及更大即内角和最小的。![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/7f22cafd59d249a98e3fd1b971202298.png3 拼接内外环及交集并集补集拼接内外换红色是是内环顺时针黄色外环逆时针。AB是顺时针 故环是ABCDJGFIA部分边是红色部分边是黄色故不是交集。BA是逆时针故环是BAIFGJDCBA。部分边是红色部分边是黄色故不是交集。外环一EI是顺时针故环是EIJHE。部分边是红色部分边是黄色故不是交集。IE是逆时针故环是IEHJI。部分边是红色部分边是黄色故不是交集。外环二IF是顺时针故环是IFGJI。全部是红色故是交集。FI是逆时针故环是FIJGF。全部是黄色故是交集。环一是逆时针来自于S 1 的边之前是逆时针来自 s 2 的边之前是顺时针 S_1的边之前是逆时针来自s_2的边之前是顺时针S1​的边之前是逆时针来自s2​的边之前是顺时针故外环一是S 1 S_1S1​独有。环二是逆时针来自于S 1 的边之前是顺时针来自 s 2 的边之前是顺时针 S_1的边之前是顺时针来自s_2的边之前是顺时针S1​的边之前是顺时针来自s2​的边之前是顺时针故外环二是S 2 S_2S2​独有。交集公共部分。并集属于 S 1 或 S 2 。 S 1 − S 2 只属于 S 1 的部分 交集公共部分。并集属于S_1或S_2。S_1-S_2 只属于S_1的部分交集公共部分。并集属于S1​或S2​。S1​−S2​只属于S1​的部分扩展阅读算法为骨CAD为魂亲士工具箱支持中望CAD2024、AutoCad2013及以上多年承接CAD项目的精华工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。视频课程先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。https://edu.csdn.net/course/detail/38771如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程https://edu.csdn.net/lecturer/6176测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。