多边形Ploygon并集轮廓线算法实现

landsat99 · 发表于 2023-2-12 14:36:40

本帖最后由 landsat99 于 2023-2-15 20:57 编辑

n个多边形随机放置，每个多边形边数(m>=3)。

条件：已知每个多边形顶点有序坐标集。
算法实现：n个多边形的并集轮廓线，并消除集内孤岛区域。

// ------------------------------------------------------------------
// 2023.02.15 修改
// ------------------------------------------------------------------

基本实现。尚在不定期更新中: PloyContour (landsat99.github.io)
原创代码，未参考其它几何算法集。
欢迎大家提供测试数据。

import operator
from copy import deepcopy
import matplotlib.pyplot as plt
from PloyData_1 import *
def XYMaxPoint(PList):
Xmax = max(i[0] for i in PList)
Xlist = []
for poi in PList:
if poi[0] == Xmax:
Xlist.append(poi)
Ymax = max(i[1] for i in Xlist)
for i in PList:
if i[0] == Xmax and i[1] == Ymax:
return i
def RegulaPloy(ploy):
# x极值点正则判断的需要
Xmax = max([i[0] for i in ploy])
for id, item in enumerate(ploy):
if item[0] == Xmax:
Num = id
break
# 两侧延长数据
tempPloy = ploy.copy()
tempPloy.append(ploy[0])
tempPloy.insert(0, ploy[len(ploy) - 1])
# 顶点正则判断
[x1, y1] = tempPloy[Num]
[x2, y2] = tempPloy[Num + 1]
[x3, y3] = tempPloy[Num + 2]
Wise = (x3 - x2) * (y1 - y2) - (x1 - x2) * (y3 - y2)
if Wise < 0:
ploy.reverse()
return ploy
def IsCross(line1, line2):
[[Ax1, Ay1], [Ax2, Ay2]] = line1
[[Bx1, By1], [Bx2, By2]] = line2
m1 = (Bx1 - Ax1) * (Ay2 - Ay1) - (Ax2 - Ax1) * (By1 - Ay1) # line1 2-sides
m2 = (Bx2 - Ax1) * (Ay2 - Ay1) - (Ax2 - Ax1) * (By2 - Ay1)
k1 = (Ax1 - Bx1) * (By2 - By1) - (Bx2 - Bx1) * (Ay1 - By1) # line2 2-sides
k2 = (Ax2 - Bx1) * (By2 - By1) - (Bx2 - Bx1) * (Ay2 - By1)
return m1 * m2 <= 0 and k1 * k2 <= 0
def CrossPoi(line1, line2):
[[Ax1, Ay1], [Ax2, Ay2]] = line1
[[Bx1, By1], [Bx2, By2]] = line2
Left = (Bx2 - Bx1) * (Ay1 - Ay2) - (Ax2 - Ax1) * (By1 - By2)
Right = (Ay1 - By1) * (Ax2 - Ax1) * (Bx2 - Bx1) + Bx1 * \
(By2 - By1) * (Ax2 - Ax1) - Ax1 * (Ay2 - Ay1) * (Bx2 - Bx1)
x = Right / Left
Left = (Ax1 - Ax2) * (By2 - By1) - (Ay2 - Ay1) * (Bx1 - Bx2)
Right = Ay2 * (Ax1 - Ax2) * (By2 - By1) + (Bx2 - Ax2) * \
(By2 - By1) * (Ay1 - Ay2) - By2 * (Bx1 - Bx2) * (Ay2 - Ay1)
y = Right / Left
return [x, y]
def Dis(p1, p2):
return (p2[0] - p1[0])**2 + (p2[1] - p1[1])**2
def RouteSec(XYRpoi, StartPoi):
T = 0
# print(XYRpoi)
ployName = XYRpoi[2]
for poi in Data[ployName]:
if T == 1:
if poi[0] == StartPoi[0] and poi[1] == StartPoi[1]:
print("轮廓线绘制完毕！")
return "OK"
if len(poi) == 2:
ContourLine.append([poi[0], poi[1]])
if len(poi) > 2:
T = 0
if poi[2] == ployName:
nextName = poi[4]
elif poi[4] == ployName:
nextName = poi[2]
else:
print("Error: 交叉点路由信息错误。[From：轮廓线生成函数 RouteSec]")
return [poi[0], poi[1], nextName]
if poi[0] == XYRpoi[0] and poi[1] == XYRpoi[1]: # 注意浮点精度问题
ContourLine.append([poi[0], poi[1]])
T = 1
def plot2D():
for ploy in Data.values():
x = [i[0] for i in ploy]
y = [i[1] for i in ploy]
x.append(x[0])
y.append(y[0])
plt.scatter(x, y)
plt.plot(x, y)
x = [i[0] for i in ContourLine]
y = [i[1] for i in ContourLine]
x.append(x[0])
y.append(y[0])
plt.scatter(x, y)
plt.plot(x, y, lw=6, color='navy')
plt.show()
if __name__ == "__main__":
for val in Data.values():
val = RegulaPloy(val)
PlotData = deepcopy(Data)
PloyPair = []
KList = [i for i in Data.keys()]
for i in range(len(KList)):
for j in range(i + 1, len(KList)):
PloyPair.append([KList, KList[j]])
AllCrossP = []
for pair in PloyPair:
for id, Aline in enumerate(SidePloy(Data[pair[0]])):
for jd, Bline in enumerate(SidePloy(Data[pair[1]])):
if IsCross(Aline, Bline):
xy = CrossPoi(Aline, Bline)
info = [pair[0], id, pair[1], jd]
xy.extend(info)
AllCrossP.append(xy)
for name, ploy in Data.items():
for i in range(len(ploy) - 1, -1, -1):
insPoiList = IndexCrossPoi(name, ploy, i, AllCrossP)
if insPoiList != []:
insPoiList.reverse()
for j in insPoiList:
ploy.insert(i + 1, j)
for key, val in Data.items():
Data[key] = Data[key] * 2
AllployPoi = []
for name, val in PlotData.items():
for i in val:
i.append(name)
AllployPoi.append(i)
StartPoi = XYMaxPoint(AllployPoi)
Poi_A = StartPoi
Poi_B = []
# 生成轮廓线
ContourLine = []
while Poi_B != "OK":
Poi_B = RouteSec(Poi_A, StartPoi)
Poi_A = Poi_B
# 绘图
plot2D()

import operator 
from copy import deepcopy 
import matplotlib.pyplot as plt 
from PloyData_1 import * 
 
 
def XYMaxPoint(PList): 
    Xmax = max(i[0] for i in PList) 
    Xlist = [] 
    for poi in PList: 
        if poi[0] == Xmax: 
            Xlist.append(poi) 
    Ymax = max(i[1] for i in Xlist) 
    for i in PList: 
        if i[0] == Xmax and i[1] == Ymax: 
            return i 
 
 
def RegulaPloy(ploy): 
    # x极值点 正则判断的需要 
    Xmax = max([i[0] for i in ploy]) 
    for id, item in enumerate(ploy): 
        if item[0] == Xmax: 
            Num = id 
            break 
    # 两侧延长数据 
    tempPloy = ploy.copy() 
    tempPloy.append(ploy[0]) 
    tempPloy.insert(0, ploy[len(ploy) - 1]) 
    # 顶点正则判断 
    [x1, y1] = tempPloy[Num] 
    [x2, y2] = tempPloy[Num + 1] 
    [x3, y3] = tempPloy[Num + 2] 
    Wise = (x3 - x2) * (y1 - y2) - (x1 - x2) * (y3 - y2) 
    if Wise < 0: 
        ploy.reverse() 
    return ploy 
 
 
 
def IsCross(line1, line2): 
    [[Ax1, Ay1], [Ax2, Ay2]] = line1 
    [[Bx1, By1], [Bx2, By2]] = line2 
    m1 = (Bx1 - Ax1) * (Ay2 - Ay1) - (Ax2 - Ax1) * (By1 - Ay1)  # line1 2-sides 
    m2 = (Bx2 - Ax1) * (Ay2 - Ay1) - (Ax2 - Ax1) * (By2 - Ay1) 
    k1 = (Ax1 - Bx1) * (By2 - By1) - (Bx2 - Bx1) * (Ay1 - By1)  # line2 2-sides 
    k2 = (Ax2 - Bx1) * (By2 - By1) - (Bx2 - Bx1) * (Ay2 - By1) 
    return m1 * m2 <= 0 and k1 * k2 <= 0 
 
 
def CrossPoi(line1, line2): 
    [[Ax1, Ay1], [Ax2, Ay2]] = line1 
    [[Bx1, By1], [Bx2, By2]] = line2 
    Left = (Bx2 - Bx1) * (Ay1 - Ay2) - (Ax2 - Ax1) * (By1 - By2) 
    Right = (Ay1 - By1) * (Ax2 - Ax1) * (Bx2 - Bx1) + Bx1 * \ 
        (By2 - By1) * (Ax2 - Ax1) - Ax1 * (Ay2 - Ay1) * (Bx2 - Bx1) 
    x = Right / Left 
 
    Left = (Ax1 - Ax2) * (By2 - By1) - (Ay2 - Ay1) * (Bx1 - Bx2) 
    Right = Ay2 * (Ax1 - Ax2) * (By2 - By1) + (Bx2 - Ax2) * \ 
        (By2 - By1) * (Ay1 - Ay2) - By2 * (Bx1 - Bx2) * (Ay2 - Ay1) 
    y = Right / Left 
    return [x, y] 
 
 
def Dis(p1, p2): 
    return (p2[0] - p1[0])**2 + (p2[1] - p1[1])**2 
 
 
def RouteSec(XYRpoi, StartPoi): 
    T = 0 
    # print(XYRpoi) 
    ployName = XYRpoi[2] 
    for poi in Data[ployName]: 
        if T == 1: 
            if poi[0] == StartPoi[0] and poi[1] == StartPoi[1]: 
                print("轮廓线 绘制完毕！") 
                return "OK" 
            if len(poi) == 2: 
                ContourLine.append([poi[0], poi[1]]) 
            if len(poi) > 2: 
                T = 0 
                if poi[2] == ployName: 
                    nextName = poi[4] 
                elif poi[4] == ployName: 
                    nextName = poi[2] 
                else: 
                    print("Error: 交叉点路由信息错误。[From：轮廓线生成函数 RouteSec]") 
                return [poi[0], poi[1], nextName] 
        if poi[0] == XYRpoi[0] and poi[1] == XYRpoi[1]:  # 注意 浮点精度问题 
            ContourLine.append([poi[0], poi[1]]) 
            T = 1 
 
 
def plot2D(): 
    for ploy in Data.values(): 
        x = [i[0] for i in ploy] 
        y = [i[1] for i in ploy] 
        x.append(x[0]) 
        y.append(y[0]) 
        plt.scatter(x, y) 
        plt.plot(x, y) 
    x = [i[0] for i in ContourLine] 
    y = [i[1] for i in ContourLine] 
    x.append(x[0]) 
    y.append(y[0]) 
    plt.scatter(x, y) 
    plt.plot(x, y, lw=6, color='navy') 
    plt.show() 
 
 
if __name__ == "__main__": 
    for val in Data.values(): 
        val = RegulaPloy(val) 
    PlotData = deepcopy(Data) 
 
    PloyPair = [] 
    KList = [i for i in Data.keys()] 
    for i in range(len(KList)): 
        for j in range(i + 1, len(KList)): 
            PloyPair.append([KList, KList[j]]) 
 
    AllCrossP = [] 
    for pair in PloyPair: 
        for id, Aline in enumerate(SidePloy(Data[pair[0]])): 
            for jd, Bline in enumerate(SidePloy(Data[pair[1]])): 
                if IsCross(Aline, Bline): 
                    xy = CrossPoi(Aline, Bline) 
                    info = [pair[0], id, pair[1], jd] 
                    xy.extend(info) 
                    AllCrossP.append(xy) 
 
    for name, ploy in Data.items(): 
        for i in range(len(ploy) - 1, -1, -1): 
            insPoiList = IndexCrossPoi(name, ploy, i, AllCrossP) 
            if insPoiList != []: 
                insPoiList.reverse() 
                for j in insPoiList: 
                    ploy.insert(i + 1, j) 
 
    for key, val in Data.items(): 
        Data[key] = Data[key] * 2 
 
    AllployPoi = [] 
    for name, val in PlotData.items(): 
        for i in val: 
            i.append(name) 
            AllployPoi.append(i) 
    StartPoi = XYMaxPoint(AllployPoi) 
    Poi_A = StartPoi 
    Poi_B = [] 
 
    # 生成轮廓线 
    ContourLine = [] 
    while Poi_B != "OK": 
        Poi_B = RouteSec(Poi_A, StartPoi) 
        Poi_A = Poi_B 
 
    # 绘图 
    plot2D()

jun353835273 · 发表于 2023-2-12 15:32:30

AI的提出的方法
实现这个问题，可以使用扫描线算法。扫描线算法是一种计算几何算法，它通过维护扫描线上交点的次序，来计算几何图形的并集。
首先，将所有多边形的所有边按照x坐标从左到右排序，每次处理的时候选择x坐标最小的边，如果该边的两个端点在扫描线的同一侧，则不处理，如果在不同侧，则加入交点，并在扫描线上删除该边。接下来，扫描线向右移动，并继续执行上述操作，直到所有边都被处理完。

最终得到的并集轮廓线就是所有交点按照x坐标从左到右排列的线段集合。可以使用深度优先搜索算法消除并集内的孤岛区域。

实现起来可能比较复杂，但是如果你有足够的编程经验和数学知识，应该能够实现。

landsat99 · 发表于 2023-2-14 10:21:19

jun353835273 发表于 2023-2-12 15:32
AI的提出的方法
实现这个问题，可以使用扫描线算法。扫描线算法是一种计算几何算法，它通过维护扫描线上交 ...

感谢您的提示和建议。

准备用正则矢量法试试。目前预估算法上可行，近期找时间代码实现看看。届时核各位朋友交流.

landsat99 · 发表于 2024-4-25 21:24:32

dcl1214 发表于 2023-8-14 21:31
CGAL有源码公布，建议您看看

嗯。谢谢。

此算法有别于Cgal的凸包，并没有参考cgal的 Convex Hulls算法。区别是，Cgal的 Extreme Points以及Convex Hulls采用了其他的航向模式，可生成3D凸包，舍弃了部分2D的效率

hhh454 · 发表于 2023-2-14 21:24:07

可以用regon后union，得到的图形炸开后，然后用pe合并得到pline，扫描线法可以得到最近点外轮廓的方法，没有学会，请知道的大神指教，感谢。

landsat99 · 发表于 2023-2-15 20:26:08

本帖最后由 landsat99 于 2023-2-15 20:38 编辑

// 2023.02.15 -- 问题首层已更新

基本实现。不定期完善中。

雨的节奏 · 发表于 2023-2-16 22:51:27

简单，全部求交点，打断，中点射线法判断

chixun99 · 发表于 2023-4-21 13:48:23

可以参考点集（所有交点、顶点的数组）的最小凸包算法。

chixun99 · 发表于 2023-4-21 13:49:34

这是什么语言的代码？

1ce94 · 发表于 2023-4-21 17:05:54

chixun99 发表于 2023-4-21 13:49
这是什么语言的代码？

用的是Python

liuhe · 发表于 2023-4-29 07:04:38

有一个不是算法快捷方法。外面画个大矩形，直接用bo快捷键，就生成轮廓线。但是bo需要内部图元少

账号		自动登录	找回密码
密码			注册

[其它] 多边形Ploygon并集轮廓线算法实现

本帖子中包含更多资源

评分

本帖子中包含更多资源

[其它] 多边形Ploygon并集轮廓线 算法实现

本帖子中包含更多资源

评分

本帖子中包含更多资源

[其它] 多边形Ploygon并集轮廓线算法实现