In [1]:
from ICGChapter02 import *

In [2]:
# Comment out the line below if the graphics do not display
%config InlineBackend.figure_format = 'retina'

In [3]:
%%javascript
IPython.OutputArea.prototype._should_scroll = function(lines) {return false;}


# Chapter 3: Triangles and the relationship of points to lines¶

In this chapter, we will start to work with triangles, and see how they are an essential tool in computational geometry.

In [4]:
displayTOC("ICGChapter03.ipynb")


# Polygons¶

Contents

Because triangles are three sided polygons, we need to consider a few basic principles of polygons first. We will consider polygons in much more detail later. Here are some definitions:

• Convex set: a set of points, $p_1, p_2, ...p_n$ such that all edges, $(p_i, p_j)$ where $i \le n$, $j \le n$ and $i \ne j$ lie within the set.
• Polygon: the region of a plane bounded by a closed curve. A polygon is a closed planar polygonal chain.
• Simple polygon: the region of a plane bounded by a simple (non self-intersecting closed curve).
• Convex polygon: a simple polygon whose interior is a convex set. A convex polygon is monotone with respect to any straight line.
• Triangle: a three-sided simple, convex polygon.
• Monotone polygon: a polygon is monotone with respect to a straight line L if every line perpendicular to L intersects the polygon at most twice.

Considering the definition of a polygon given above:

1. A polygon has $n$ consecutive vertexes $v_1, v_2, ... v_n$. The edges of the polygon $e_1, e_2, ... e_n$ are the line segments $(v_1, v_2), (v_2, v_3), ... (v_n, v_1)$
2. The edges are connected end to end to form a curve. In other words, the intersection of $e_i$ and $e_{i+1}$ is the vertex $v_i$: $$e_i \cap e_{i+1} = v_{i+1} \: for \: i=1..n$$
3. The last vertex of the last edge is connected back to the first vertex of the first edge (a closed curve). An alternate definition (that we don't use in this text) is that the first and last vertexes are identical. $$e_n \cap e_1 = v_1$$

If non-consecutive edges do not intersect, then it is a simple closed curve and therefore a simple polygon: $$e_i \cap e_j = 0 \: for \: j \ne i+1$$

A convex polygon has an interior that is a convex set. In other words for a convex polygon, every edge between two vertexes must be inside the polygon. For this to be the case, every internal angle must be $\le 180^{\circ}$. We won't provide a proof of this, but it means that convex polygons are always simple. If a polygon is not convex, then it is concave. Concave polygons are not necessarily simple.

As we said above, a triangle is a polygon with three sides. It is simple and convex, because intersections and concavities are impossible when there are only three sides.

## Representing polygons in Python¶

Contents

We will represent a polygon as a closed polygonal chain. Here are some point lists for example polygons that we will use later:

In [5]:
CONVEX_HEXAGON_PLIST = PointList((4, 0), (2, 4), (-2, 4), (-4, 0), (-2, -4), (2, -4))
CONCAVE_HEXAGON_PLIST = PointList((4, 0), (2, 4), (-2, 4), (0, 0), (-2, -4), (2, -4))
SQUARE_PLIST = PointList((2, -2), (2, 2), (-2, 2), (-2, -2))


This is what they look like:

In [6]:
#Demo
@interact(poly=["Convex hexagon", "Concave hexagon", "Square"])
def _demoPolygons(poly="Convex hexagon"):
# Geometry
if poly == "Convex hexagon":
pol = CONVEX_HEXAGON_PLIST
if poly == "Concave hexagon":
pol = CONCAVE_HEXAGON_PLIST
if poly == "Square":
pol = SQUARE_PLIST

# Graphics
cgc = CGCanvas("Example closed polygonal chains")
polygon(cgc, pol, linewidth=2)
labelPointList(cgc, pol, template="$v_{}$")

cgc.show()
#Demo


We will adopt the convention that polygon vertexes are always listed in an anti-clockwise order. In other words, if you step from one vertex to the next, the interior of the polygon is always on your left hand side. This anti-clockwise convention is very important, as we will see shortly when we come to calculate polygon areas.

Now that we know how to represent polygons we can begin to investigate their properties. We will start with the simplest polygon - the triangle.

# Triangles¶

Contents

We all know what a triangle is, but here is a formal definition:

• Triangle: a three-sided polygon.

the following graphics function draws a colored and labeled triangle:

In [7]:
def triangle(cgc, plist, labels=("a", "b", "c"), dot=False, colors=("red", "green", "blue"), **kwargs):
"""Draw a triangle and label its vertexes."""
if dot: circles(cgc, plist)
a,b,c = plist
lineSegment(cgc, a, b, color=colors[0], **kwargs)
lineSegment(cgc, b, c, color=colors[1], **kwargs)
lineSegment(cgc, c, a, color=colors[2], **kwargs)
text(cgc, offsetPoint(a), text=labels[0], color=colors[0])
text(cgc, offsetPoint(b), text=labels[1], color=colors[1])
text(cgc, offsetPoint(c), text=labels[2], color=colors[2])


For example:

In [8]:
#Demo
def _demoTriangle():
# Geometry
t = PointList((0,3), (0,0), (4,0))

# Graphics
cgc = CGCanvas("Triangle")
triangle(cgc, t, dot=False)
cgc.show()

_demoTriangle()
#Demo


## Signed area of a triangle¶

Contents

A key function in computational geometry is the function that gives the signed area of a 2D triangle that is positive if the vertexes are given in an anti-clockwise order, and negative if they are given in a clockwise order.

Because this function is so important, we will spend some time developing it. We will start in 3D, because that is the basis of the 2D function, and then define a flexible and efficient 2D function.

Given a triangle, $T$, in 3D space with vertexes $a$, $b$ and $c$, we can convert the edges $(a,b)$ and $(a,c)$ to edge vectors simply by subtracting $a$. This translates the triangle to put $a$ at the origin. So we have:

$\overrightarrow{v} = b - a$

$\overrightarrow{w} = c - a$

The area of the triangle is then given by:

$$A(T_{3D}) = \frac{|\overrightarrow{v} \times \overrightarrow{w}|}{2}$$

A proof of this is beyond this book, but any text on coordinate geometry should explain it.

We need a Point3D class to help us with this. This class is the pretty much the same code as our standard Point class but with an extra $z$ coordinate. We don't need all of this code for our purposes here, but we have included it for completeness.

In [9]:
class Point3D:
"""A class to represent a point in 3D space with x, y and z coordinates. Point3D objects are immutable."""
def __init__(self, x=0, y=0, z=0):
self.__x = x
self.__y = y
self.__z = z

@property
def x(self):
"""Return the x coordinate."""
return self.__x

@property
def y(self):
"""Return the y coordinate."""
return self.__y

@property
def z(self):
"""Return the z coordinate."""
return self.__z

def __eq__(self, p):
return (self.x == p.x) and (self.y == p.y) and (self.z == p.z)

def __ne__(self, p):
return (self.x != p.x) or (self.y != p.y) or (self.z != p.z)

def __add__(self, p):
return Point(self.x + p.x, self.y + p.y, self.z + p.z)

def __sub__(self, p):
return Point3D(self.x - p.x, self.y - p.y, self.z - p.z)

def __mul__(self, p):
return Point(self.x * p.x, self.y * p.y, self.z * p.z)

def __truediv__(self, p):
return Point(self.x/p.x, self.y/p.y, self.z/p.z)

def __hash__(self):
return hash((self.x, self.y, self.z))

def __iter__(self):
return iter((self.x, self.y, self.z))

def __str__(self):
return "({},{},{})".format(self.x, self.y, self.z)

def __repr__(self):
return "Point({!r},{!r},{}!r)".format(self.x, self.y, self.z)


We can now define a function for the area of a triangle in 3D as follows:

In [10]:
def triangleArea3D(a, b, c):
"""Calculate the signed area of the triangle defined by the Point3D objects a, b, and c. Positive if points ant-clockwise."""
v = b - a
w = c - a
cross = np.cross((v.x, v.y, v.z), (w.x, w.y, w.z))
return np.linalg.norm(cross)*0.5


Of course, we don't have to use built-in functions, we can just multiply everything out as follows:

$$\overrightarrow{v} \times \overrightarrow{w} = -a_z b_y + a_y b_z + a_z c_y-b_z c_y - a_y c_z + b_y c_z, a_z b_x - a_x b_z - a_z c_x + b_z c_x + a_x c_z - b_x c_z, -a_y b_x + a_x b_y + a_y c_x - b_y c_x - a_x c_y + b_x c_y$$

No - I didn't do that by hand, I used a symbolic algebra system - Mathematica to be precise.

This gives:

$$A(T_{3D}) = \frac{1}{2}\sqrt{(-a_y b_x + a_x b_y + a_y c_x - b_y c_x - a_x c_y + b_x c_y)^2 + (a_z b_x - a_x b_z - a_z c_x + b_z c_x + a_x c_z - b_x c_z)^2 + (-a_z b_y + a_y b_z + a_z c_y - b_z c_y - a_y c_z + b_y c_z)^2}$$

For 2D triangles, T, where the z coordinate is 0, this simplifies quite a bit because we lose all of the terms involving z:

$$A(T) = \frac{1}{2}\sqrt{(-a_y b_x + a_x b_y + a_y c_x - b_y c_x - a_x c_y + b_x c_y)^2} = \frac{1}{2}(-a_y b_x + a_x b_y + a_y c_x - b_y c_x - a_x c_y + b_x c_y)$$

We can implement this function as follows:

In [11]:
def triangleArea(a,b,c):
"""Calculate the signed area of the triangle defined by the Points a, b, and c. Positive if points ant-clockwise."""
return 0.5* (-a.y * b.x + a.x * b.y + a.y * c.x - b.y * c.x - a.x * c.y + b.x * c.y)


Another way to express the $A(T_{3D})$ is as half the determinant of a matrix comprising the $x$, $y$ and $z$ coordinates of the points:

$$A(T_{3D}) = \frac{1}{2} \left | \begin{bmatrix} a _x & a_y & a_z\\ b_x & b_y & b_z \\ c_x & c_y & c_z \end{bmatrix} \right |$$

For 2D points, the $z$ coordinates are set to 1:

$$A(T) = \frac{1}{2} \left | \begin{bmatrix} a _x & a_y & 1\\ b_x & b_y & 1 \\ c_x & c_y & 1 \end{bmatrix} \right |$$

Using the NumPy library this is trivial to implement:

In [12]:
#Demo
def triangleAreaDet3D(a, b, c):
return np.linalg.det([[a.x, a.y, a.z], [b.x, b.y, b.z], [c.x, c.y, c.z]])

def triangleAreaDet(a, b, c):
return np.linalg.det([[a.x, a.y, 1], [b.x, b.y, 1], [c.x, c.y, 1]])
#Demo


But which version is faster? We will look at the 2D case only, because that is our main interest here, but the 3D case will be similar. We can ask Python to profile the functions for us as follows:

In [13]:
# %prun for i in range(10000) : triangleArea(Point(0, 0), Point(1, 0), Point(1, 1)) # time = 0.120

In [14]:
# %prun for i in range(10000) : triangleAreaDet(Point(0, 0), Point(1, 0), Point(1, 1)) # time = 0.514


If you want to see the results on your own system, you can uncomment the two cells above and run them.

The result is that triangleArea(...) is just over four times faster than triangleAreaDet(...). This isn't surprising, because even though triangleAreaDet(...) uses the hugely efficient NumPy mathematics library, it still makes a lot of expensive function calls, whereas triangleArea(...) only uses basic arithmetic.

Below is an interactive demo program for triangleArea(...). Notice how the triangle area is positive when the points are ordered anti-clockwise and negative when they are ordered clockwise.

In [15]:
#Demo
@interact(ax=(-5,5), ay=(-5,5), bx=(-5,5), by=(-5,5), cx=(-5,5), cy=(-5,5))
def _demoTriangleArea(ax=0, ay=3, bx=0, by=0, cx=4, cy=0):
# Geometry
a = Point(ax,ay)
b = Point(bx, by)
c = Point(cx, cy)
area = triangleArea(a, b, c)

# Graphics
cgc = CGCanvas("Triangle area, a to b to c = {}".format(area))
triangle(cgc, PointList(a,b,c))
cgc.show()
#Demo


Now that we have a function to determine the signed area of a triangle, we can use this function to develop some fundamental algorithms of computational geometry - those that determine the relationships of points to lines.

# Triangles and the relationships of points to lines¶

Contents

If we treat a triangle as a line segment $(a, b)$ and a point $c$, then the signed triangle area tells us about the relationship between point $c$ and the line $L$ determined by the line segment:

1. If triangle $(a, b, c)$ area is $\gt 0$, then point $c$ is to the left of line $L$ as you travel from $a$ to $b$. Otherwise it is to the right.

2. If triangle $(a, b, c)$ area is $\ge 0$ then point $c$ is to the left of the line $L$ or collinear with it.

3. If triangle $(a, b, c)$ area is $= 0$ then point $c$ is collinear with the line $L$.

You can easily verify this for yourself by playing about with the, "Triangle area", demonstration in the previous section.

## isCollinear, isLeft, isLeftOn, isRight, isRightOn¶

Contents

We can now define the following functions:

In [16]:
def isCollinear(a, b, c):
"""Return True if Points a, b and c are collinear."""
return triangleArea(a, b, c) == 0

def isLeft(a, b, c):
"""Return True if Point c is to the left of line (a, b) but not on it."""
return triangleArea(a, b, c) > 0

def isLeftOn(a, b, c):
"""Return True if Point c is to the left of or on the line (a, b)."""
return triangleArea(a, b, c) >= 0

def isRight(a, b, c):
"""Return True if Point c is to the right of line (a, b) but not on it."""
return not isLeftOn(a, b, c)

def isRightOn(a, b, c):
"""Return True if Point c is to the right of or on the line (a, b)."""
return isLeft(a, b, c)


There are a couple of things to note:

1. We clearly distinguish between the line $L$ defined by the line line segment $(a, b)$ and the line segment itself. Lines have infinite length, so point $c$ does not need to be on the line segment between $a$ and $b$ for these functions to return True - they work over the infinite length of the line.

2. It is crucial to understand what "left" actually means in this context: if you are traveling along the line from $a$ to $b$, then "left" means on your left hand side.

## Between¶

Contents

Another important relationship we need to test for is "between" - is point $c$ is between $a$ and $b$? By "between", we mean that $c$ is somewhere on the line segment $(a, b)$. This breaks down into two considerations:

1. For $c$ to be between $a$ and $b$ it is necessary (but not sufficient) that it is collinear with $a$ and $b$.

2. The point $c$ must not be off either end of the line segment $(a, b)$. In other words, $c_x$ must be between $a_x$ and $b_x$ AND $c_y$ must be between $a_y$ and $b_y$.

We can express this second constraint as follows:

$((a_x \le c_x \le b_x) \lor (b_x \le c_x \le a_x)) \land ((a_y \le c_y \le b_y) \lor (b_y \le c_y \le a_y))$

Where $\land$ means logical and, and $\lor$ means logical or.

This translates directly into Python code as follows:

In [17]:
def isBetween(a, b, c):
"""Return True if Point c is somewhere on the line segment (a, b)."""
if not isCollinear(a, b, c):
return False
return ((a.x <= c.x <= b.x) or (b.x <= c.x <= a.x)) and ((a.y <= c.y <= b.y) or (b.y <= c.y <= a.y))


## Demo program for relationships between points and lines¶

Contents

Here is a demo program for the functions we defined in this section. Move the interactive point around and see see when the various functions return True or False:

In [18]:
#Demo
@interact(cx=(-5,5), cy=(-5,5))
def _demoPointCBetweenAAndB(cx=0, cy=3):
# Geometry
c = Point(cx, cy)
a = Point(-4,0)
b = Point(4, 0)

between = isBetween(a, b, c)
collinear = isCollinear(a, b, c)
leftOn = isLeftOn(a, b, c)
left = isLeft(a, b, c)

# Graphics
cgc = CGCanvas("isBetween = {}, isCollinear = {}, isLeftOn = {}, isLeft ={}".format(between, collinear, leftOn, left))

if between:
col = cols(1)
elif left:
col = cols(2)
elif leftOn:
col = cols(3)
elif collinear:
col = cols(4)
else:
col = cols(5)

circles(cgc, [a, b])
text(cgc, pt=a + Point(0,-0.7), text="a")
text(cgc, pt=b + Point(0,-0.7), text="b")

interactor(cgc, c, color=col)

cgc.show()
#Demo


# Points in general position¶

Contents

Now that we have a test for collinearity we can write a test to see if a set of points is in general position. The algorithm is simple: take all subsets of the point set that have cardinality 3, and if none of these is collinear, then the point set is in general position.

In Python, we can generate all subsets of a set of $n$ points of size 3 as follows:

In [19]:
#Demo
def subsets3(n):
subsets = []
for i in range(n):
for j in range(i+1, n):
for k in range(j+1, n):
subsets.append([i, j, k])
return subsets

subsets3(4)
#Demo

Out[19]:
[[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]]

However, we won't use this approach, because Python has the itertools library. This contains itertools.combinations(...), which does the same thing, but faster:

In [20]:
#Demo
list(itertools.combinations(range(4), 3))
#Demo

Out[20]:
[(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]

We can use this to write a function to check a point set for general position:

In [21]:
def isGeneralPosition(plist):
"""Return True if a list of Points is in general position."""
perms = itertools.combinations(plist, 3)
for p in perms:
if isCollinear(p[0], p[1], p[2]):
return False
return True


Here is a demo program. Move the points around and see under what conditions they go into and out of general position:

In [22]:
#Demo
@interact(p0x=(-5,5), p0y=(-5,5), p1x=(-5,5), p1y=(-5,5), p2x=(-5,5), p2y=(-5,5), p3x=(-5,5), p3y=(-5,5))
def _demoPointsInGeneralPosition(p0x=0, p0y=3, p1x=0, p1y=0, p2x=4, p2y=0, p3x=3, p3y=0):
# Geometry
plist = PointList((p0x, p0y), (p1x, p1y), (p2x, p2y), (p3x, p3y))
gp = isGeneralPosition(plist)

# Graphics
cgc = CGCanvas("Points in general position is {}".format(gp))
col = "green" if gp else "red"
circles(cgc, plist, color=col)
labelPointList(cgc, plist)

cgc.show()
#Demo


## Probability of a random point set being in general position¶

Contents

At this point it is interesting to revisit our randomPointSetNonGP(...) function with the question, what is the probability of generating a random point set in general position? If we were using floating point numbers, then the answer would be almost certainty, because there are so many possibilities to choose from. If we are using integers on a grid, then the answer depends on the size of the grid, and how many points we ask for.

We can perform an experiment: If the size of the grid is $n$ x $n$ and we ask for a set of $m$ random points, we can calculate the probability they are in general position by running randomPointSetNonGP(...) many times and recording what proportion of the runs give a result in general position. Here is a function to do this:

In [23]:
def GPProbability(n, m, runs=500):
"""Return the probability of a Point set generated with randomPointSetNonGP(...) is in general position."""
gp = 0
for r in range(runs):
if isGeneralPosition(randomPointSetNonGP(m, start=1, end=n)):
gp += 1
return gp/runs


For example, if we have $n$ = 11 (our standard grid) and ask for 10 points, the probability that these 10 points will be in general position is:

In [24]:
#Demo
GPProbability(11, 10)
#Demo

Out[24]:
0.052

This is very low! Let's plot probability of general position vs. $\frac{m}{n}$ for $n = 11$, to see what is going on. Here is a function to generate a probability curve for $m = 0$ to $m = mMax$:

In [25]:
def GPProbabilityCurve(n, mMax, runs=500):
"""Probability curve for a set of m points chosen from a square grid of n points being in general position."""
x = []
y = []
for m in range(mMax):
x.append(m/n)
y.append(GPProbability(n, m, runs=500))
return [x, y, n]


Here is the curve for $n = 11$ and $m=0$ to $m=15$:

In [26]:
#Demo
x, y, n = GPProbabilityCurve(11, 15)

plt.plot(x, y)
plt.ylabel("Probability of GP for n = {}".format(n))
plt.xlabel(r"Ratio $\frac{m}{n}$")
plt.show()
#Demo


You can see from the above graph for $n = 11$, that as $m$ approaches $n$, and $\frac{m}{n}$ approaches 1, the probability of the point set being in general position gets very low. Rather than take values off the above graph, we can calculate $m$ for a given probability $P(n)$:

In [27]:
def mForPn(P, n):
"""Calculate the size of a Point set drawn from a square grid of n Points that has a probability P of being in general position."""
m = 0
while GPProbability(n, m) > P:
m += 1
return m


Use the demo program below to find $m$ for a given $P(n)$. You can see that for $n = 11$ and a $P(n)$ of 0.5 (a 50:50 chance) you can ask for no more than 7 points:

In [28]:
#Demo
@interact(P=[0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9], n=range(3, 15))
def _demoProbs(P=0.5, n=11):
print(r"For n = {}, the number of points, m, for probability of {} = {}".format(n, P, mForPn(P, n)))
#Demo


We can also explore the effect of increasing $n$:

In [29]:
#Demo
curves = [GPProbabilityCurve(n, 2*n, runs=500) for n in range(1, 14, 2)]

for c in curves:
x, y, n = c
plt.plot(x, y, label="n={}".format(n))

plt.ylabel("Probability of GP")
plt.xlabel(r"Ratio $\frac{m}{n}$")
plt.legend()
plt.show()
#Demo


The above graph shows that as $n$ increases, the ratio $\frac{m}{n}$ for which you can get any given probability of a general position set decreases.

You can see that this simple experiment has allowed us to get a much clearer idea of how likely the function RandomPointSetNonGP(...) will give a point set in general position. It is often necessary to perform experiments such as this in order to understand the behavior of certain functions.

## Random point sets in general position¶

Contents

In this section we will use the function isGeneralPosition(...), to create a simple constructive algorithm to generate random sets of points in general position. As usual, we will generate points on an $n$ x $n$ grid, so the maximum number of points we can have is obviously $n^2$, in which case there is a point on each intersection of the grid.

Firstly, we need to work out the maximum number of points it is possible to have in general position for a given grid.

The no-three-in-line problem asks for the maximum number of points that can be placed on an $n$ x $n$ grid so that no three points are collinear. This number is at most $2n$, since if $2n + 1$ points are placed in the grid, then by the pigeonhole principle some row and some column must contain three points. Given this result, on our usual $(-5, -5)$ to $(5, 5)$ grid, which is 11 x 11, the maximum number of general position points is 11 x 2 = 22.

Here is a simple constructive algorithm to generate a point set $P$ of $m$ random points in general position where $m \lt 2n$ and $n$ is the side of the grid:

1. Let $P = \emptyset$ (the empty set)

2. While $|P| \lt m$

2.1 Generate a random point, $p$.

2.2 If $P \cup \{p\}$ is in general position then $P = P \cup \{p\}$

The algorithm generates random points and adds them to the set if they are in general position until we have the number we want. To implement this, we first of all need a function to tell us if a point is in general position with respect to a point set:

In [30]:
def isPointInGP(pts, p):
"""Return True if p is in general position with respect to Point set pts."""
ptsGP = copy.deepcopy(pts)
ptsGP.append(p)
return (p not in pts) and isGeneralPosition(ptsGP)


Next, we simply add points in general position to get our point set:

In [31]:
def randomPointSetGP(m, start=-5, end=5):
"""Return a random set of m points in general position."""
pts = []
m = min(m, int((end - start + 1) + (end - start + 1)/2))
while len(pts) < m:
p = Point(random.randint(start, end), random.randint(start, end))
if isPointInGP(pts, p):
pts.append(p)
return pts


Notice that for a given $n$ x $n$ grid we have set the maximum number of points in general position to be the integer value of $n + \frac{n}{2}$. This is a purely pragmatic value based on our experience with the function. The problem is that if we allowed the maximum possible number of points ($2n$) we might never be able to get there because of how the early random points are positioned, and this would lead to an infinite loop. The value of $n + \frac{n}{2}$ is nice compromise that is low enough that the algorithm always terminates (note: we do not have a proof for this) and we get a good random scattering of points that doesn't look too constrained.

Here is a demo program. Notice that the function limits the number of points as we just described:

In [32]:
#Demo
@interact(m=(0,20))
def _demoRandomPointSet(m):
# Geometry
pts = randomPointSetGP(m)

# Graphics
cgc = CGCanvas("Random point set in general position for m = {}".format(len(pts)))
circles(cgc, pts)
cgc.show()
#Demo


# The relationship of points to the half-plane¶

Contents

Sometimes all we need to know is what side of a line a set of points is on. Another way of saying this is whether a set of points all lie in the same open half plane (points on the line not included) or closed half plane (points on the line included). These functions are trivial given the functions we developed above:

In [33]:
def isSameSide(a, b, plist):
"""Return True if all Points in plist are on the same side (but not on) line (a,b)."""
left = right = True
for p in plist:
left = left and isLeft(a, b, p)
right = right and isRight(a, b, p)
return left or right

def isSameSideOn(a, b, plist):
"""Return True if all Points in plist are on the same side or on line (a,b)."""
leftOn = rightOn = True
for p in plist:
leftOn = leftOn and isLeftOn(a, b, p)
rightOn = rightOn and isRightOn(a, b, p)
return leftOn or rightOn


Here is a demo program:

In [34]:
#Demo
@interact(p0x=(-6, 6), p0y=(-6,6), p1x=(-6, 6), p1y=(-6,6), p2x=(-6, 6), p2y=(-6,6))
def _demoIsSameSide(p0x=5, p0y=-3, p1x=4, p1y=3, p2x=-3, p2y=5):
# Geometry
plist = PointList((p0x, p0y), (p1x, p1y), (p2x, p2y))
a = Point(-5, 5)
b = Point(5, -5)
sameSide = isSameSide(a, b, plist)
sameSideOn = isSameSideOn(a, b, plist)

# Graphics
cgc = CGCanvas("Same side = {}, same side on = {}".format(sameSide, sameSideOn))
line(cgc, a, b)
if sameSide:
col = "green"
elif sameSideOn:
col = "blue"
else:
col = "red"
for p in plist:
interactor(cgc, p, color=col)

cgc.show()
#Demo


# Summary¶

Contents

Triangles are the key to computational geometry. They allow us to discover relationships between points and lines by forming them into triangles and considering the signed triangle areas. These relationships are the building blocks for the more complex algorithms we will introduce in subsequent chapters. Always remember that for our algorithms to work, we need to adhere to our convention that polygon vertexes always go in an anticlockwise order.