PythonTIN⽹⽣成（Delaunay三⾓形）
新型玉米播种机
基于Python的TIN⽹⽣成（Delaunay三⾓形）
基本算法
⽣成TIN的算法很多，但作者所学有限，今天仅写依据Delaunay三⾓形的TIN扩张⽣成算法，具体流程如下：
1. 在离散点中随机选取⼀点作为基线边的起点，寻与起点最近的另⼀点作为基线边的终点，⽣成⼀条基线边，并存⼊BaseStack栈 中。创建LineList存放边，TriangleList存放⽣成的三⾓形。
2. 在BaseStack栈中取⼀条基线边出栈，在离散点中遍历查询⼀个基线边右侧的点使得其与基线边构成的⾓最⼤。
3. 若存在这样的点，则⽤该点与基线边创建⼀个Delaunay三⾓形。基线边为第⼀条边，基线边起点到该新查询点为第⼆条边，该新查询
点到基线边终点为第三条边，后两新边作为新的基线边压⼊BaseStack中，若重复则不再压⼊。再依次将新边、三⾓形存⼊LineList 和TriangleList，若重复则不在存储。若不存在这样的点，则跳过该基线边。
4. 重复2、3步骤，直到BaseStack为空，将得到的LineList和TriangleList保存。
为了结构化管理数据，我们为数据创建了三种数据结构，即点类（Point）、边类（Line）和三⾓形类（Triangle）。
点类
具有点名PointName、坐标值X,Y、⾼程值H等属性、并拥有⼀个计算当前点与其他点之间距离的⽅法Cal_Distans()，如下所⽰：
# 点类
class Point:
电极材料'''包含点名数学坐标X 数学坐标Y ⾼程（z）H'''
def__init__(self,pointname,x,y,h):
self.PointName=pointname
self.X=x
self.Y=y
self.H=h
def Cal_Distans(self,x0,y0):
d=math.sqrt(math.pow(x0-self.X,2)+math.pow(y0-self.Y,2))
return d
边类
具有起始点BeginPoint和终⽌点EndPoint两个来确定边的主要属性，另外拥有Belonging_Triangle列表属性来记录当前边的归属三⾓形和他所属的邻接三⾓形（该属性在后续等值线的⽣长中将发挥巨⼤作⽤），除此之外重载了⽅向不同但投影是相同边的判断运算符（==）⽤来判断边是否相同，如下所⽰：
#边类
class Line:
def__init__(self,point_b,point_e):
self.BeginPoint=point_b
self.EndPoint=point_e
self.Belonging_Triangle=[]
def__eq__(self, other):
if(self.BeginPoint.PointName==other.EndPoint.PointName and
self.EndPoint.PointName==other.BeginPoint.PointName):
return1
elif(self.BeginPoint.PointName==other.BeginPoint.PointName and
self.EndPoint.PointName==other.EndPoint.PointName):
return1
else:
return0
三⾓形类
根据Delaunay三⾓形的⽣成过程，我们定义的三⾓形类⼴泛意义上讲是⼀个有向三⾓形，它由基线边、基线边的起点到新查询点、新查询点到基线边终点三条有向边构成，除此之外也重载了⽅向不同但投影是相同三⾓形的判断运算符（==）⽤来判断三⾓形是否相等，如下所⽰：
# 三⾓形类
class Triangle:
def__init__(self,point_b,point_e,point_s):
self.BaseLine=Line(point_b,point_e)
def__eq__(self, other):#重载==
if(self.BaseLine==other.BaseLine wLine1==wLine1 wLine2==wLine2):
return1
elif(self.BaseLine==other.BaseLine wLine1==wLine2 wLine2==wLine1):
return1
elif(self.BaseLine==wLine1 wLine1==wLine2 wLine2==other.BaseLine):
return1
elif(self.BaseLine==wLine1 wLine1==other.BaseLine wLine2==wLine2):
return1
elif(self.BaseLine==wLine2 wLine1==wLine1 wLine2==other.BaseLine):
return1
elif(self.BaseLine==wLine2 wLine1==other.BaseLine wLine2==wLine1):
return1
else:
return0
功能代码实现过程
导⼊数据
打开指定路径⽂件，按⾏读取⽂件中的内容，直到⽂件结束。将每⾏⽂件内容按“，”分隔符分割，将得到的点名，坐标，⾼程等实例成⼀个点对象point。将各个点对象按尾插⼊法存⼊point_list列表,⽅便后续管理和使⽤数据，如下所⽰：
# 数据读取将数据组织到已经封装的点类再⽤列表将所有点线性连接在⼀起⽅便调⽤
def ReadDataTXT(Str_Path):
point_list=[]
with open(Str_Path)as f:
title = f.readline()
print(title.rstrip())
while(1):
line = f.readline()
变面积式电容传感器if(line==""):
break
str_list=[]
str_list=line.rstrip().split(',')
point=Point(str_list[1],float(str_list[2]),float(str_list[3]),float(str_list[4]))
point_list.append(point)
str_list=[]
return point_list
⽣成TIN三⾓⽹
查询数据边界
查询定位数据的最⼤最⼩横纵坐标，以此矩形框作为可视化显⽰的边界，也是当前坐标系与屏幕坐标系转换时的⽐例尺依据，将会在坐标系转换时频繁发⽣作⽤，如下所⽰：
# 查询数据边界
def XYMinMax(Point_List):
xmax=EPSILON
xmin=1/EPSILON
ymax=EPSILON
ymin=1/EPSILON
for point in Point_List:
if(point.X<xmin):
xmin=point.X
elif(point.X>xmax):
xmax=point.X
if(point.Y<ymin):
ymin=point.Y
elif(point.Y>ymax):
ymax=point.Y
return xmin,xmax,ymin,ymax
坐标系转换
蜂巢芯
将数学坐标系下数据的边界范围和屏幕坐标系的屏幕⼤⼩关系进⾏⽐较，得到横纵⽐例尺及其对应的函数关系，⼀次将每⼀个数学坐标点转换到屏幕坐标系下并显⽰（通过Tkinter canvas画布），如下所⽰：
# 数学坐标系转到屏幕坐标系
# 上下个延伸10% 使屏幕有效率达到86% 数据边界不会丢失
def GaussToScreenCor(XYMinMax_List,Gx,Gy):
网络视频传输
dxmax=(XYMinMax_List[1]-XYMinMax_List[0])*1.2
dymax=(XYMinMax_List[3]-XYMinMax_List[2])*1.2
xscale=dxmax/800
yscale=dymax/600
Sx=int((Gx-XYMinMax_List[0]+dxmax*0.083)/xscale)
Sy=int((XYMinMax_List[3]-Gy+dymax*0.083)/yscale)
return Sx,Sy
计算余弦值
算法通过最⼩⾓最⼤化来确定Delaunay三⾓形，本篇⽂章采⽤余弦值法来⽐较⾓度的⼤⼩关系，即⾓度越⼤对应的余弦值越⼩，如下所⽰：
# 解算右三⾓形余弦值
def Solve_Triangle_cos(Triangle):
c=Triangle.BaseLine.BeginPoint.Cal_Distans(Triangle.BaseLine.EndPoint.X,Triangle.BaseLine.EndPoint.Y)
wLine1.EndPoint.Cal_Distans(Triangle.BaseLine.EndPoint.X,Triangle.BaseLine.EndPoint.Y)
wLine1.EndPoint.Cal_Distans(Triangle.BaseLine.BeginPoint.X,Triangle.BaseLine.BeginPoint.Y)
cos=(a*a+b*b-c*c)/(2*a*b)
return cos
'''铣床主轴
查询最近点
在point_list列表⾥查询与当前点距离最近的点，并返回其所在列表中的下标索引，如下所⽰：
# 与某点距离最近的点
def NearistPoint(Point,Point_list):
d=1/EPSILON
index=0
for i in range(len(Point_list)):
if(Point_list[i].PointName!=Point.PointName):
if(Point.Cal_Distans(Point_list[i].X,Point_list[i].Y)<d):
d=Point.Cal_Distans(Point_list[i].X,Point_list[i].Y)
index=i
return index
创建Delaunay三⾓形
在基线边的右边查离散点使得该离散点与基线边之间形成的夹⾓最⼤，若存在这样的点返回这个点的point_list中的下标索引值，若不存在则返回none，如下所⽰：
# 由基线⽣成三⾓形
def CreatTRI(Line,Point_List):
cos=1.1
cosmin=1.1
index=''
for i in range(len(Point_List)):
if(Point_List[i].PointName==Line.BeginPoint.PointName or Point_List[i].PointName==Line.EndPoint.PointName):
continue
if(Judge_Right(Line,Point_List[i])):
triangle=Triangle(Line.BeginPoint,Line.EndPoint,Point_List[i])
cos=Solve_Triangle_cos(triangle)
if(cos<cosmin):
cosmin=cos
index=i
if(index!=''):
return index
边判重复
判断新加⼊边是否已经在Linelist中，在则表⽰重复，返回1，如下所⽰：
def Judge_Dup(Line_List):
line1=Line_List[-1]
for i in range(0,len(Line_List)-1):
if(Line_List[i]==line1):
return1
判右
判断离散点是否在基线边的右侧，是则返回1。利⽤计算机图形学的旋转平移变换技术，将基线边与离散点平移旋转⾄基线边起点在原点且基线⽅向与数学坐标x轴同向，若离散点y值⼩于0，则判定该离散点在基线边的右侧，如下所⽰：
# 判断寻点是否在基线边右侧是返回true (利⽤图形学平移旋转变化)
def Judge_Right(BaseLine,Point):
dx=BaseLine.EndPoint.X-BaseLine.BeginPoint.X
dy=BaseLine.EndPoint.Y-BaseLine.BeginPoint.Y
d=math.sqrt(dx*dx+dy*dy)
cos=dx/d
sin=dy/d
#旋转平移变换三⾓形顺时针旋转基线⽅向与X正轴重合
x=(Point.X-BaseLine.BeginPoint.X)*cos+(Point.Y-BaseLine.BeginPoint.Y)*sin
y=-(Point.X-BaseLine.BeginPoint.X)*sin+(Point.Y-BaseLine.BeginPoint.Y)*cos
if(y<0):
return1
添加边
将新⽣成的边添加到边的存储列表LineList，若边已经存在则不再添加，若不存在则添加⽣成，作为画出TIN的数据源，如下所⽰：
# 添加边
def AddLine(LineList,BaseStack,line):
LineList.append(line)
if(Judge_Dup(LineList)):
del LineList[-1]
del BaseStack[-1]
return LineList,BaseStack
添加基线边
向存储基线边的BaseStack栈列表中添加新的基线边，若新基线边已经在BaseStack中存在，则不在添加，反之则加⼊基线边栈。如下所⽰：
def AddBaseStack(BaseStack,line):
BaseStack.append(line)
if(Judge_Dup(BaseStack)):
del BaseStack[-1]
return BaseStack
添加三⾓形
向三⾓形列表Triangle_List中添加三⾓形triangle，若该三⾓形已经存在于三⾓形列表则不再添加，反之则添加。添加完成时，要给当前三⾓形的三边Belonging_Triangle赋值当前三⾓形的下标索引，记录这个三⾓形的三边归属三⾓形。如下所⽰：
#添加三⾓形
def AddTriangle(Triangle_List,triangle):
already=0
for tri in Triangle_List:
if(tri==triangle):
already=1
if(already==0):
Triangle_List.append(triangle)
#三⾓形存储后在刚存进的三⾓形三边上记录该三⾓形的列表索引号
Triangle_List[-1].BaseLine.Belonging_Triangle.append(len(Triangle_List)-1)
Triangle_List[-1].newLine1.Belonging_Triangle.append(len(Triangle_List)-1)
Triangle_List[-1].newLine2.Belonging_Triangle.append(len(Triangle_List)-1)
return Triangle_List
边的邻接三⾓形
除三⾓形边的当前归属三⾓形外，边上还应记录边的邻接三⾓形是哪⼀个，通过遍历查将三⾓形三边的邻接三⾓形下标索引也存储到Belonging_Triangle,⽅便后续等值线的⽣成。如下所⽰：
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议