In [8]:
class Point:
"""
Represents a point in a 2D Euclidean plane.
"""
def __init__(self, x, y):
self.x = x
self.y = y
@property
def tuplify(self):
return self.x, self.y
def __lt__(self, other):
return self.tuplify < other.tuplify
def __repr__(self):
return str((self.x, self.y))
In [9]:
def orientation(p1, p2, p3):
"""
We are given the triangle spanned on the points p1, p2 and p3.
Return positive number if the triangle is positively oriented.
Return positive number if the triangle is negatively oriented.
Returns 0 if the triangle is degenerated.
"""
a = (p2.x - p1.x, p2.y - p1.y)
b = (p3.x - p1.x, p3.y - p1.y)
return a[0]*b[1] - b[0]*a[1]
Test the orientation method on a simple test case.
In [10]:
a = Point(0, 0)
b = Point(1, 0)
c = Point(0, 1)
d = Point(2, 0)
assert orientation(a, b, c) > 0
assert orientation(a, b, d) == 0
assert orientation(a, c, b) < 0
In [11]:
class Node:
"""
Node in a doubly linked link list.
"""
def __init__(self, data):
self.data = data
self.p, self.n = self, self
def link_after(self, new_node):
'''
Insert new_node into linked list after the self node.
'''
new_node.n, new_node.p = self.n, self
self.n.p, self.n = new_node, new_node
def __repr__(self):
ret = "{0}".format(self.data)
c = self
while c.n != self:
c = c.n
ret += " <-> {0}".format(c.data)
return ret
In [79]:
from random import random
def generify(points, epsilon=0.0001):
"""
Jiggle the points coordinates just a little so that they are in the
general position.
Returns the generator.
"""
for point in points:
e = 2*(random()-0.5)*epsilon
d = 2*(random()-0.5)*epsilon*e
yield Point(point.x + e, point.y + d)
Now we can start with our main method.
In [152]:
def triangulation(points):
'''
Construct line sweep triangulation.
'''
assert len(points) >= 3, 'Triangulation requires at least 3 points'
points = sorted(generify((Point(x, y) for (x,y) in points)))
nodes = [Node(point) for point in points]
triangles = []
triangles.append(points[:3])
if orientation(*triangles[0]) < 0:
nodes[0], nodes[1] = nodes[1], nodes[0]
nodes[0].link_after(nodes[1]), nodes[1].link_after(nodes[2])
for i in range(3, len(nodes)):
print(nodes[i-1])
add_node(nodes[i-1], nodes[i], triangles)
print(nodes[i])
print()
return triangles
def add_node(start, new, triangles):
'''
Process one node (containing point), add appropriate triangles.
'''
current = start
print('t1', new.data, current.n.data, current.data)
while orientation(new.data, current.n.data, current.data) > 0:
print('a1', new.data, current.n.data, current.data)
triangles.append([new.data, current.n.data, current.data])
current = current.n
print('t1', new.data, current.n.data, current.data)
last, current = current, start
print('t2', new.data, current.data, current.p.data)
while orientation(new.data, current.data, current.p.data) > 0:
print('a2', new.data, current.data, current.p.data)
triangles.append([new.data, current.data, current.p.data])
current = current.p
print('t2', new.data, current.data, current.p.data)
print (last.data)
print (current.data)
new.n = last
current.link_after(new)
Test the given method and plot the results.
In [153]:
from matplotlib import pyplot
%matplotlib notebook
points = [(1,3),(6,2),(0.5,3),(0,4),(8,1),(8,0)]
xs, ys = map(list, zip(*points))
pyplot.axis([min(xs)-1,max(xs)+1,min(xs)-1,max(ys)+1])
pyplot.plot( xs, ys, 'ro')
triangles = triangulation(points)
colors = "bgrcmykwbgrcmykwbgrcmykwbgrcmykw"
for i, (p1, p2, p3) in enumerate(triangles):
pyplot.plot([p1.x, p2.x], [p1.y, p2.y], c=colors[i], alpha=0.3)
pyplot.plot([p1.x, p3.x], [p1.y, p3.y], c=colors[i], alpha=0.3)
pyplot.plot([p2.x, p3.x], [p2.y, p3.y], c=colors[i], alpha=0.3)
In [154]:
from matplotlib import pyplot
from random import randint
%matplotlib notebook
#points = [(randint(1, 100), randint(1, 100)) for i in range(5)]
points = [(0,0),(3,9),(5,-1),(9,4), (7, -5)]
xs, ys = map(list, zip(*points))
pyplot.axis([min(xs)-1,max(xs)+1,min(ys)-1,max(ys)+1])
pyplot.plot( xs, ys, 'ro')
triangles = triangulation(points)
for i, (p1, p2, p3) in enumerate(triangles):
pyplot.plot([p1.x, p2.x], [p1.y, p2.y])
pyplot.plot([p1.x, p3.x], [p1.y, p3.y])
pyplot.plot([p2.x, p3.x], [p2.y, p3.y])
In [ ]: