我实施的 Bowyer-Watson Delaunay 三角剖分不会删除包含超三角形点的三角形
A Bowyer-Watson Delaunay Triangulation I implemented doesn't remove the triangles that contain points of the super-triangle
Python 3.7.2,虽然我怀疑这条信息是否很有用。
Pygame 1.7.2。我主要用它来绘制三角剖分。所有计算均使用普通公式完成。
根据维基百科,Bowyer-Watson 算法的伪代码如图所示:
function BowyerWatson (pointList)
// pointList is a set of coordinates defining the points to be triangulated
triangulation := empty triangle mesh data structure
add super-triangle to triangulation // must be large enough to completely contain all the points in pointList
for each point in pointList do // add all the points one at a time to the triangulation
badTriangles := empty set
for each triangle in triangulation do // first find all the triangles that are no longer valid due to the insertion
if point is inside circumcircle of triangle
add triangle to badTriangles
polygon := empty set
for each triangle in badTriangles do // find the boundary of the polygonal hole
for each edge in triangle do
if edge is not shared by any other triangles in badTriangles
add edge to polygon
for each triangle in badTriangles do // remove them from the data structure
remove triangle from triangulation
for each edge in polygon do // re-triangulate the polygonal hole
newTri := form a triangle from edge to point
add newTri to triangulation
for each triangle in triangulation // done inserting points, now clean up
if triangle contains a vertex from original super-triangle
remove triangle from triangulation
return triangulation
但是,当我 运行 我的代码从最终三角剖分中删除了一些具有超三角形顶点的三角形时,它并没有删除所有这些三角形。
这是我的代码:
import pygame
import pygame.gfxdraw
import math
import random
pygame.init()
def circumcenter(a, b, c):
ad = a[0] * a[0] + a[1] * a[1]
bd = b[0] * b[0] + b[1] * b[1]
cd = c[0] * c[0] + c[1] * c[1]
D = 2 * (a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]))
return pygame.Vector2((1 / D * (ad * (b[1] - c[1]) + bd * (c[1] - a[1]) + cd * (a[1] - b[1])),
1 / D * (ad * (c[0] - b[0]) + bd * (a[0] - c[0]) + cd * (b[0] - a[0]))))
def LineIsEqual(line1,line2):
if (line1[0] == line2[0] and line1[1] == line2[1]) or (line1[0] == line2[1] and line1[1] == line2[0]):
return True
return False
def distance(point1,point2):
return math.sqrt((point1[0]-point2[0])**2 + (point1[1]-point2[1])**2)
class Triangle:
def __init__(self,a,b,c):
self.a = a
self.b = b
self.c = c
self.edges = [[self.a,self.b],
[self.b,self.c],
[self.c,self.a]]
self.circumcenter = circumcenter(a,b,c)
def IsPointInCircumcircle(self,point):
if (self.a.distance_to(self.circumcenter) > point.distance_to(self.circumcenter)):
return True
return False
def HasVertex(self,point):
if (self.a == point) or (self.b == point) or (self.c == point):
return True
return False
def Show(self,screen,colour):
for edge in self.edges:
pygame.draw.aaline(screen,colour,edge[0],edge[1])
def DelaunayTriangulation(points,width,height):
triangulation = []
superTriangleA = pygame.Vector2(-100,-100)
superTriangleB = pygame.Vector2(2*width+100,-100)
superTriangleC = pygame.Vector2(-100,2*height+100)
superTriangle = Triangle(superTriangleA,superTriangleB,superTriangleC)
triangulation.append(superTriangle)
for point in points:
badTriangles = []
for triangle in triangulation:
if triangle.IsPointInCircumcircle(point):
badTriangles.append(triangle)
polygon = []
for triangle in badTriangles:
for triangleEdge in triangle.edges:
isShared = False
for other in badTriangles:
if triangle == other:
continue
for otherEdge in other.edges:
if LineIsEqual(triangleEdge,otherEdge):
isShared = True
if isShared == False:
polygon.append(triangleEdge)
for badTriangle in badTriangles:
triangulation.remove(badTriangle)
for edge in polygon:
newTriangle = Triangle(edge[0],edge[1],point)
triangulation.append(newTriangle)
for triangle in triangulation:
if triangle.HasVertex(superTriangleA) and triangle in triangulation:
triangulation.remove(triangle)
if triangle.HasVertex(superTriangleB) and triangle in triangulation:
triangulation.remove(triangle)
if triangle.HasVertex(superTriangleC) and triangle in triangulation:
triangulation.remove(triangle)
return triangulation
background = 20,40,100
white = 255,255,255
width = int(500)
height = int(500)
amount = int(100)
screen = pygame.display.set_mode((width,height))
screen.fill(background)
points = []
for i in range(amount):
x = random.randint(1,width-1)
y = random.randint(1,height-1)
points.append(pygame.Vector2(x,y))
delaunay = DelaunayTriangulation(points,width,height)
for triangle in delaunay:
triangle.Show(screen,white)
pygame.display.update()
当同一个列表被迭代时,您不能 .remove()
列表中的元素。删除项目后,列表会发生变化:
for triangle in triangulation:
if triangle.HasVertex(superTriangleA) and triangle in triangulation:
triangulation.remove(triangle)
有一些方法可以解决这个问题。
一个解决方案是通过 triangulation[:]
:
创建列表的 shallow copy
onSuper = lambda triangle : triangle.HasVertex(superTriangleA) or triangle.HasVertex(superTriangleB) or triangle.HasVertex(superTriangleC)
for triangle in triangulation[:]:
if onSuper(triangle):
triangulation.remove(triangle)
或者创建一个要删除的三角形列表 (to_be_removed
) 并将它们从列表中删除:
to_be_removed = []
for triangle in triangulation:
if onSuper(triangle):
to_be_removed.append(triangle)
for triangle in to_be_removed:
triangulation.remove(triangle)
或创建一个新列表:
triangulation = [triangle for triangle in triangulation if not onSuper(triangle)]
以上所有解决方案都会导致相同的三角剖分。
并添加到@Rabbid76 的答案中;消耗资源最少的方法,因为它不涉及创建副本或附加列表:
反向循环移除:
for i in range(len(triangulation)-1, -1, -1):
triangle = triangulation[i]
if triangle.HasVertex(superTriangleA): #why this? -> and triangle in triangulation:
triangulation.remove(triangle)
由于您只从末尾删除项目并且向后工作,因此您永远不会以影响迭代的方式修改列表。
Python 3.7.2,虽然我怀疑这条信息是否很有用。
Pygame 1.7.2。我主要用它来绘制三角剖分。所有计算均使用普通公式完成。
根据维基百科,Bowyer-Watson 算法的伪代码如图所示:
function BowyerWatson (pointList)
// pointList is a set of coordinates defining the points to be triangulated
triangulation := empty triangle mesh data structure
add super-triangle to triangulation // must be large enough to completely contain all the points in pointList
for each point in pointList do // add all the points one at a time to the triangulation
badTriangles := empty set
for each triangle in triangulation do // first find all the triangles that are no longer valid due to the insertion
if point is inside circumcircle of triangle
add triangle to badTriangles
polygon := empty set
for each triangle in badTriangles do // find the boundary of the polygonal hole
for each edge in triangle do
if edge is not shared by any other triangles in badTriangles
add edge to polygon
for each triangle in badTriangles do // remove them from the data structure
remove triangle from triangulation
for each edge in polygon do // re-triangulate the polygonal hole
newTri := form a triangle from edge to point
add newTri to triangulation
for each triangle in triangulation // done inserting points, now clean up
if triangle contains a vertex from original super-triangle
remove triangle from triangulation
return triangulation
但是,当我 运行 我的代码从最终三角剖分中删除了一些具有超三角形顶点的三角形时,它并没有删除所有这些三角形。
这是我的代码:
import pygame
import pygame.gfxdraw
import math
import random
pygame.init()
def circumcenter(a, b, c):
ad = a[0] * a[0] + a[1] * a[1]
bd = b[0] * b[0] + b[1] * b[1]
cd = c[0] * c[0] + c[1] * c[1]
D = 2 * (a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]))
return pygame.Vector2((1 / D * (ad * (b[1] - c[1]) + bd * (c[1] - a[1]) + cd * (a[1] - b[1])),
1 / D * (ad * (c[0] - b[0]) + bd * (a[0] - c[0]) + cd * (b[0] - a[0]))))
def LineIsEqual(line1,line2):
if (line1[0] == line2[0] and line1[1] == line2[1]) or (line1[0] == line2[1] and line1[1] == line2[0]):
return True
return False
def distance(point1,point2):
return math.sqrt((point1[0]-point2[0])**2 + (point1[1]-point2[1])**2)
class Triangle:
def __init__(self,a,b,c):
self.a = a
self.b = b
self.c = c
self.edges = [[self.a,self.b],
[self.b,self.c],
[self.c,self.a]]
self.circumcenter = circumcenter(a,b,c)
def IsPointInCircumcircle(self,point):
if (self.a.distance_to(self.circumcenter) > point.distance_to(self.circumcenter)):
return True
return False
def HasVertex(self,point):
if (self.a == point) or (self.b == point) or (self.c == point):
return True
return False
def Show(self,screen,colour):
for edge in self.edges:
pygame.draw.aaline(screen,colour,edge[0],edge[1])
def DelaunayTriangulation(points,width,height):
triangulation = []
superTriangleA = pygame.Vector2(-100,-100)
superTriangleB = pygame.Vector2(2*width+100,-100)
superTriangleC = pygame.Vector2(-100,2*height+100)
superTriangle = Triangle(superTriangleA,superTriangleB,superTriangleC)
triangulation.append(superTriangle)
for point in points:
badTriangles = []
for triangle in triangulation:
if triangle.IsPointInCircumcircle(point):
badTriangles.append(triangle)
polygon = []
for triangle in badTriangles:
for triangleEdge in triangle.edges:
isShared = False
for other in badTriangles:
if triangle == other:
continue
for otherEdge in other.edges:
if LineIsEqual(triangleEdge,otherEdge):
isShared = True
if isShared == False:
polygon.append(triangleEdge)
for badTriangle in badTriangles:
triangulation.remove(badTriangle)
for edge in polygon:
newTriangle = Triangle(edge[0],edge[1],point)
triangulation.append(newTriangle)
for triangle in triangulation:
if triangle.HasVertex(superTriangleA) and triangle in triangulation:
triangulation.remove(triangle)
if triangle.HasVertex(superTriangleB) and triangle in triangulation:
triangulation.remove(triangle)
if triangle.HasVertex(superTriangleC) and triangle in triangulation:
triangulation.remove(triangle)
return triangulation
background = 20,40,100
white = 255,255,255
width = int(500)
height = int(500)
amount = int(100)
screen = pygame.display.set_mode((width,height))
screen.fill(background)
points = []
for i in range(amount):
x = random.randint(1,width-1)
y = random.randint(1,height-1)
points.append(pygame.Vector2(x,y))
delaunay = DelaunayTriangulation(points,width,height)
for triangle in delaunay:
triangle.Show(screen,white)
pygame.display.update()
当同一个列表被迭代时,您不能 .remove()
列表中的元素。删除项目后,列表会发生变化:
for triangle in triangulation: if triangle.HasVertex(superTriangleA) and triangle in triangulation: triangulation.remove(triangle)
有一些方法可以解决这个问题。
一个解决方案是通过 triangulation[:]
:
onSuper = lambda triangle : triangle.HasVertex(superTriangleA) or triangle.HasVertex(superTriangleB) or triangle.HasVertex(superTriangleC)
for triangle in triangulation[:]:
if onSuper(triangle):
triangulation.remove(triangle)
或者创建一个要删除的三角形列表 (to_be_removed
) 并将它们从列表中删除:
to_be_removed = []
for triangle in triangulation:
if onSuper(triangle):
to_be_removed.append(triangle)
for triangle in to_be_removed:
triangulation.remove(triangle)
或创建一个新列表:
triangulation = [triangle for triangle in triangulation if not onSuper(triangle)]
以上所有解决方案都会导致相同的三角剖分。
并添加到@Rabbid76 的答案中;消耗资源最少的方法,因为它不涉及创建副本或附加列表:
反向循环移除:
for i in range(len(triangulation)-1, -1, -1):
triangle = triangulation[i]
if triangle.HasVertex(superTriangleA): #why this? -> and triangle in triangulation:
triangulation.remove(triangle)
由于您只从末尾删除项目并且向后工作,因此您永远不会以影响迭代的方式修改列表。