多边形Ploygon并集轮廓线 算法实现
本帖最后由 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 for i in PList)
Xlist = []
for poi in PList:
if poi == Xmax:
Xlist.append(poi)
Ymax = max(i for i in Xlist)
for i in PList:
if i == Xmax and i == Ymax:
return i
def RegulaPloy(ploy):
# x极值点 正则判断的需要
Xmax = max( for i in ploy])
for id, item in enumerate(ploy):
if item == Xmax:
Num = id
break
# 两侧延长数据
tempPloy = ploy.copy()
tempPloy.append(ploy)
tempPloy.insert(0, ploy)
# 顶点正则判断
= tempPloy
= tempPloy
= tempPloy
Wise = (x3 - x2) * (y1 - y2) - (x1 - x2) * (y3 - y2)
if Wise < 0:
ploy.reverse()
return ploy
def IsCross(line1, line2):
[, ] = line1
[, ] = 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):
[, ] = line1
[, ] = 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
def Dis(p1, p2):
return (p2 - p1)**2 + (p2 - p1)**2
def RouteSec(XYRpoi, StartPoi):
T = 0
# print(XYRpoi)
ployName = XYRpoi
for poi in Data:
if T == 1:
if poi == StartPoi and poi == StartPoi:
print("轮廓线 绘制完毕！")
return "OK"
if len(poi) == 2:
ContourLine.append(, poi])
if len(poi) > 2:
T = 0
if poi == ployName:
nextName = poi
elif poi == ployName:
nextName = poi
else:
print("Error: 交叉点路由信息错误。")
return , poi, nextName]
if poi == XYRpoi and poi == XYRpoi:# 注意 浮点精度问题
ContourLine.append(, poi])
T = 1
def plot2D():
for ploy in Data.values():
x = for i in ploy]
y = for i in ploy]
x.append(x)
y.append(y)
plt.scatter(x, y)
plt.plot(x, y)
x = for i in ContourLine]
y = for i in ContourLine]
x.append(x)
y.append(y)
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 =
for i in range(len(KList)):
for j in range(i + 1, len(KList)):
PloyPair.append(, KList])
AllCrossP = []
for pair in PloyPair:
for id, Aline in enumerate(SidePloy(Data])):
for jd, Bline in enumerate(SidePloy(Data])):
if IsCross(Aline, Bline):
xy = CrossPoi(Aline, Bline)
info = , id, pair, 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 = Data * 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()
AI的提出的方法
实现这个问题，可以使用扫描线算法。扫描线算法是一种计算几何算法，它通过维护扫描线上交点的次序，来计算几何图形的并集。
首先，将所有多边形的所有边按照x坐标从左到右排序，每次处理的时候选择x坐标最小的边，如果该边的两个端点在扫描线的同一侧，则不处理，如果在不同侧，则加入交点，并在扫描线上删除该边。接下来，扫描线向右移动，并继续执行上述操作，直到所有边都被处理完。
最终得到的并集轮廓线就是所有交点按照x坐标从左到右排列的线段集合。可以使用深度优先搜索算法消除并集内的孤岛区域。
实现起来可能比较复杂，但是如果你有足够的编程经验和数学知识，应该能够实现。 jun353835273 发表于 2023-2-12 15:32
AI的提出的方法
实现这个问题，可以使用扫描线算法。扫描线算法是一种计算几何算法，它通过维护扫描线上交 ...
感谢您的提示和建议。
准备用正则矢量法试试。目前预估算法上可行，近期找时间代码实现看看。届时核各位朋友交流. dcl1214 发表于 2023-8-14 21:31
CGAL有源码公布，建议您看看
嗯。谢谢。
此算法有别于Cgal的凸包，并没有参考cgal的 Convex Hulls算法。区别是，Cgal的 Extreme Points以及Convex Hulls采用了其他的航向模式，可生成3D凸包，舍弃了部分2D的效率
可以用regon后union，得到的图形炸开后，然后用pe合并得到pline，扫描线法可以得到最近点外轮廓的方法，没有学会，请知道的大神指教，感谢。 本帖最后由 landsat99 于 2023-2-15 20:38 编辑
// 2023.02.15-- 问题首层 已更新
基本实现。不定期完善中。
简单，全部求交点，打断，中点射线法判断 可以参考点集（所有交点、顶点的数组）的最小凸包算法。 这是什么语言的代码？ chixun99 发表于 2023-4-21 13:49
这是什么语言的代码？
用的是Python 有一个不是算法快捷方法。外面画个大矩形，直接用bo快捷键，就生成轮廓线。但是bo需要内部图元少
页:
[1]
2