正交点集-外轮廓线算法实现

landsat99 发表于 2023-2-6 23:55

本帖最后由 landsat99 于 2023-2-7 09:15 编辑

// 分布于正交栅格网的散点集合（允许有内部空洞），生成正交点集合的外轮廓线。

说明：
1.此算法分区施加右手法则，贴合正交外轮廓。
2.对任意散点的集合，外轮廓线不唯一。需附加约束条件，比如面积最大、轮廓线周长最大、最小等。
3.Python演示算法及图形说明。
4.此正交算法为纯原创代码，未参考其它几何算法集。不严谨之处多多交流指正。

# RecVec_grid.py
import matplotlib.pyplot as plt
import GenList as Gen
import MaxP as MP

def Direc(UpDown, A, B):
alpha = 360 + 10
if UpDown == 1:# 象限号
   if B == A and B > A:
         alpha = 0#
   elif B == A and B < A:
         alpha = 180
   elif B == A and B > A:
         alpha = 90
   elif B == A and B < A:
         alpha = 270
   else:
         pass
if UpDown == 2:# 象限号
   if B == A and B > A:
         alpha = 0
   elif B == A and B < A:
         alpha = 180
   elif B == A and B > A:
         alpha = 270
   elif B == A and B < A:
         alpha = 90
   else:
         pass
if UpDown == 3:# 象限号
   if B == A and B < A:
         alpha = 0
   elif B == A and B > A:
         alpha = 180
   elif B == A and B < A:
         alpha = 90
   elif B == A and B > A:
         alpha = 270
   else:
         pass
if UpDown == 4:# 象限号
   if B == A and B < A:
         alpha = 0
   elif B == A and B > A:
         alpha = 180
   elif B == A and B < A:
         alpha = 270
   elif B == A and B > A:
         alpha = 90
   else:
         pass
return alpha

def Dist(A, B):
return (B - A)**2 + (B - A)**2

def NextPoi(UpDown, Poi, PList):
Dire = 360 + 10
Unit = 1
for id, p in enumerate(PList):
   if Direc(UpDown, Poi, p) <= Dire and Dist(Poi, p) == Unit:
         Dire = Direc(UpDown, Poi, p)
         dis = Dist(Poi, p)
         Num = id
return PList

def plot2D(x, y, x_out, y_out):
plt.scatter(x, y)# 画散点图
plt.plot(x_out, y_out)# 画连线图
plt.show()

if __name__ == '__main__':
Points = Gen.GenList()
XMaxPoi, Num = MP.XMaxPoint(Points)
YMaxPoi, Num = MP.YMaxPoint(Points)
XMinPoi, Num = MP.XMinPoint(Points)
YMinPoi, Num = MP.YMinPoint(Points)
PPs = Points.copy()
PPs.remove(XMaxPoi)
Poi_A = XMaxPoi
RList =
Poi_B = []
while Poi_B != YMaxPoi:
   Poi_B = NextPoi(1, Poi_A, PPs)
   RList.append(Poi_B)
   PPs.remove(Poi_B)
   Poi_A = Poi_B
Poi_A = YMaxPoi
Poi_B = []
while Poi_B != XMinPoi:
   Poi_B = NextPoi(2, Poi_A, PPs)
   RList.append(Poi_B)
   PPs.remove(Poi_B)
   Poi_A = Poi_B
Poi_A = XMinPoi
Poi_B = []
while Poi_B != YMinPoi:
   Poi_B = NextPoi(3, Poi_A, PPs)
   RList.append(Poi_B)
   PPs.remove(Poi_B)
   Poi_A = Poi_B
Poi_A = YMinPoi
Poi_B = []
PPs = + PPs# 加回第一点
while Poi_B != XMaxPoi:
   Poi_B = NextPoi(4, Poi_A, PPs)
   RList.append(Poi_B)
   PPs.remove(Poi_B)
   Poi_A = Poi_B
print(RList)

XList = for i in Points]
YList = for i in Points]
X_OutList = for i in RList]
Y_OutList = for i in RList]
plot2D(XList, YList, X_OutList, Y_OutList)

# MaxP.py
def XMaxPoint(PList):
Xmax = PList
Ymax = PList
for id, poi in enumerate(PList):
   if poi > Xmax:
         Xmax = poi
         Ymax = poi
         Num = id
   if poi >= Xmax and poi > Ymax:
         Xmax = poi
         Num = id
return PList, Num

def YMaxPoint(PList):
Xmax = PList
Ymax = PList
for id, poi in enumerate(PList):
   if poi > Ymax:
         Ymax = poi
         Xmax = poi
         Num = id
   if poi >= Ymax and poi < Xmax:
         Ymax = poi
         Num = id
return PList, Num

def XMinPoint(PList):
Xmin = PList
Ymin = PList
for id, poi in enumerate(PList):
   if poi < Xmin:
         Xmin = poi
         Ymin = poi
         Num = id
   if poi <= Xmin and poi < Ymin:
         Xmin = poi
         Num = id
return PList, Num

def YMinPoint(PList):
Xmin = PList
Ymin = PList
for id, poi in enumerate(PList):
   if poi < Ymin:
         Ymin = poi
         Xmin = poi
         Num = id
   if poi <= Ymin and poi > Xmin:
         Ymin = poi
         Num = id
return PList, Num

# GenList.py
def GenList():
Points = []
for i in range(6, 9):
   for j in range(14, 17):
         Points.append()
for i in range(4, 12):
   for j in range(12, 14):
         Points.append()
for i in range(5, 10):
   for j in range(10, 12):
         Points.append()
for i in range(2, 13):
   for j in range(6, 10):
         Points.append()
for i in range(4, 13):
   for j in range(4, 6):
         Points.append()
for i in range(3, 8):
   for j in range(0, 4):
         Points.append()
for i in range(9, 12):
   for j in range(2, 5):
         Points.append()
return Points

landsat99 发表于 2023-2-7 00:11

此算法的右手航向角取为正交判断（针对正交栅格散点集合）。

对任意散点集合，需设定另外的约束条件。

mahuan1279 发表于 2023-2-7 08:44

删掉的点都是以该点为中心八方向都有点的点。

landsat99 发表于 2023-2-7 09:24

mahuan1279 发表于 2023-2-7 08:44
删掉的点都是以该点为中心八方向都有点的点。

您这个思路很棒！确实可以解决很多阴角歧点、回头线等问题。
目前我用的四分区的办法（集合4个极值分区）分别制定航向规则，来解决阴角歧点、回头线问题。

您的方案，估计算法上会更佳。赞一个

qjchen 发表于 2023-2-7 09:54

感觉题目定义可能会导致一些无解的情况
比如矩形格点只有3个点的情况，或者有单独几点伸出的情况，也可能如楼主说的，需要限制条件
https://karobben.github.io/2022/03/07/Python/point_outline/
此处也有一个类似的问题，用了α来限制

landsat99 发表于 2023-2-7 11:27

本帖最后由 landsat99 于 2023-2-7 11:29 编辑

qjchen 发表于 2023-2-7 09:54
感觉题目定义可能会导致一些无解的情况
比如矩形格点只有3个点的情况，或者有单独几点伸出的情况，也可能 ...
同意您的观点。

对有单点的分支凸起，此算法会中断。单点凸起的轮廓线，是需要单独定义。

如果轮廓线定义为：散点集合的最大面积轮廓线，则算法将会大大简化。

mahuan1279 发表于 2023-2-7 15:34

landsat99 发表于 2023-2-7 11:27
同意您的观点。

对有单点的分支凸起，此算法会中断。单点凸起的轮廓线，是需要单独定义。

那不就是求凸包么？

landsat99 发表于 2023-2-8 17:32

本帖最后由 landsat99 于 2023-2-8 17:38 编辑

是的。凸包算法将大为简化算法。即便手写算法，也无需分区制定规则。尤其Convex的成熟包很多，稳定效率优秀。

Scipy的ConvexHull实例

import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import ConvexHull

x = np.random.normal(0, 1, 100)
y = np.random.normal(0, 1, 100)
xy = np.hstack((x[:, np.newaxis], y[:, np.newaxis]))
hull = ConvexHull(xy)
plt.scatter(x, y)
plt.plot(x, y)
plt.plot(np.append(x, x), np.append(y, y))
plt.show()

landsat99 发表于 2023-2-14 10:09

本帖最后由 landsat99 于 2023-2-14 10:13 编辑

// 2023.02.14

改为正则矢量法，可得到较优方案。普式性、简洁性均较大改善。
点集/线集序列应用，在较多情况下正则矢量法会优于航向角法。
改进过程不定期更新中.https://landsat99.github.io/GridContour.html

同时欢迎您提供数据测试

#
# 不支持 “单线分支”的图形集合
#
import matplotlib.pyplot as plt
import Data1 as Data

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)
return

def NextPoi(P, PList):
Unit = 1.0
Poi_B = []
TList = []
Grid_4 = [ + Unit, P], - Unit, P],
         , P + Unit], , P - Unit]]
for i in Grid_4:
   if i in PList:
         TList.append(i)
for A in TList:
   k = 1
   for B in TList:
         Wise = (A - P) * (B - P) - \
            (A - P) * (B - P)
         if Wise < 0:
            k = 0
   if k == 1:
         Poi_B = A
return Poi_B

def plot2D(x, y, x_out, y_out):
plt.scatter(x, y)
plt.plot(x_out, y_out)
plt.show()

if __name__ == '__main__':
PPs = Data.Points.copy()
PoiStart = XYMaxPoint(Data.Points)
Poi_A = PoiStart
RList = []
Poi_B = []
n = 0
while Poi_B != PoiStart:
   Poi_B = NextPoi(Poi_A, PPs)
   RList.append(Poi_A)
   PPs.remove(Poi_A)
   Poi_A = Poi_B
   n = n + 1
   if n == 2:
         PPs.append(PoiStart)
RList.append(PoiStart)
XList = for i in Data.Points]
YList = for i in Data.Points]
X_OutList = for i in RList]
Y_OutList = for i in RList]
plot2D(XList, YList, X_OutList, Y_OutList)

页: [1]

明经CAD社区's Archiver

正交点集-外轮廓线 算法实现

正交点集-外轮廓线算法实现