Basic Shapes, Polygons, Trigonometry

Computers are being used more and more to solve geometric problems. Geometric objects like points, lines and polygons are the basis of a broad variety of important applications and give rise to an interesting set of problems and algorithms. Geometric algorithms are important in design and analysis systems modeling physical objects, graphics design, medicine and game development. A designer working with a physical object has a geometric intuition. This is however part of the difficulty of geometric programming as certain "obvious" operations you do with a pencil, such as finding the intersection of two lines, requires non-trivial programming to do correctly with a computer. The field of geometric algorithms is interesting to study because of its strong historical context; geometry was the most valued of the classic mathematical topics. Even above the gateway to Plato's academy appears the inscription "Let no one who is ignorant of geometry enter here."

Computational Geometry in Surgery:
Geometric problems appear in modeling of medical objects, human-body tissue structures, medical imaging and even computer aided surgery. Below is an image of a surface model of the human cortex.

Most of the larger scale geometric programs depend on simple geometric objects defined in a two-dimensional space. The fundamental object is a point, which we consider to be a pair of integers--the "coordinates" are the usual Cartesian (even though other systems are plausible). A line segment is merely the shortest distance between any two points. Lines are however of infinite length in both directions, as opposed to line segments. Here we discuss only lines limited to the plane.

Representation:

Lines can be represented either as points or equations. Every line can be completely described by a pair of points \((x_1,y_1)\) and \((x_2,y_2)\). It can also be described by equations of the form \(y = mx + b\), where \(m\) is the slope of the line, i.e. \( m = \frac{\Delta y}{\Delta x} \), and \(b\) is the \(y\)-intercept .

Vertical lines are however a problem because they cannot be described by such an equation because of the division by zero. The equation \(x = k\) represents a vertical line that crosses the \(x\)-axis at the point \((k,0)\). This problem can be avoided by using the more general formula

\[ax + by + c = 0.\]

We can thus conceive two possible representation of lines: either the point representation or the \(a,b,c\) equation representation above. Let us start by representing a point in code:

1
2
3
4
5
6
7
8
9

class point:
    '''Represents a Cartesian coordinate point'''
    def __str__(self ):
        '''Allows printing of the point'''
        return "(" + str(self.x) + "," + str(self.y) + ")"    
    def __init__(self , x , y ):
        '''This initializes the class'''
        self.x = x
        self.y = y

We can proceed to formulating a two-point representation of a line:

1
2
3
4
5
6
7
8
9

class line:
    '''Takes two point objects to represent a line/line segment'''
    def __str__(self):
        ''' Prints out the line'''
        print( self.p1 , self.p2 )
    def __init__(self , point_1 , point_2 ):
        '''This initializes the class(Takes two point objects as input)'''
        self.p1 = point_1
        self.p2 = poitn_2

We can also easily implement the a,b,c form. Let us call this class line2:

1
2
3
4
5
6
7
8
9

class line2:
    '''Takes reals a,b and c to represent a line in the form ax+by+c=0'''
    def __str__(self):
        ''''Prints out the line'''
        print( self.a , self.b , self.c )
    def __init__(self , a , b , c ):
        self.a = a
        self.b = b
        self.c = c

These equation and point forms can be inter-converted using a function like the one below:

1
2
3
4
5
6
7
8
9

def point_to_line( pl , l ):
    '''Takes a point form of a line "pl" and a line object "l"'''
    if pl.p1.x == pl.p2.x:
        return line2( 1 , 0 , -pl.p1.x )
    else:
        a = -(pl.p1.y - pl.p2.y )/ (pl.p1.x - pl.p2. x )
        b = 1
        c = -(l.a * pl.p1.x ) - (l.b * pl.p1.y )
        return line2( a , b , c )

Polygons are a set of points that form a closed chain of non-intersecting line segments. By closed, we mean that the first vertex of the chain is also the last. "Non-intersecting" means that pairs of segments only touch at their endpoints.

Polygons are essential for describing most shapes in planes. We could represent polygons as a set of lines using our line class. This is however not necessary because they can easily be represented as a set of coordinate points. We can then assume a segment exists between the \(i^\text{th}\) and \((i+1)^\text{th}\) points in the chain. We thus implement it as simply an array of point objects.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class polygon:
    '''represents a polygon'''
    def __str__(self):
        '''prints the polygon's vertices in no given order'''
        S = ""
        for v in self.vertices:
            S += v+" , "
        return S[0 : -2]
    def __init__(self , points):
        '''initializes the class'''
        self.vertices = points

We can for example represent the below triangle as

1 2 3

>>> Triangle = polygon([point(-1,3),point(5,5),point(4,-2)]) >>> print(Triangle) (-1,3) , (5,5) , (4,-2)

The Euclidean shortest path problem is a problem in computational geometry: given a set of polyhedral obstacles in a Euclidean space, and two points, find the shortest path between the points that does not intersect any of the obstacles.

We are given a start position \(L_{i}\) and a goal position \(L_{f}\), which we assume are in the free space. Our goal is to compute a shortest collision-free path from \(L_{i}\) to \(L_{f}\), that is, a shortest path that does not intersect the interior of any of the obstacles. Notice that we cannot say the shortest path, because it need not be unique. For a shortest path to exist, it is important that obstacles are open sets; if they were closed, then a shortest path would not exist, as it would always be possible to shorten a path by moving closer to an obstacle.

This is not necessarily a short path, because some arcs are between nodes that are far apart, whereas others are between nodes that are close to each other. An obvious improvement would be to give each arc a weight corresponding to the Euclidean length of the segment connecting its incident nodes, and to use a graph search algorithm that finds a shortest path in a weighted graph, such as Dijkstra’s algorithm or propagating a wavefront from one of the points until it meets the other. Although this may improve the path length, we still do not get the shortest path. For now we will discuss Dijkstra's algorithm on a visibility graph.

In three (and higher) dimensions the problem is NP-hard in the general case, but there exist efficient approximation algorithms that run in polynomial time based on the idea of finding a suitable sample of points on the obstacle edges and performing a visibility graph calculation using these sample points.

The visibility graph of \(L_{i}\), \(L_{f}\), and the obstacle set is a graph whose vertices are \(L_{i}\), \(L_{f}\), and the obstacle vertices, and vertices \(v\) and \(w\) are joined by an edge if \(v\) and \(w\) are either mutually visible or if \((v, w)\) is an edge of some obstacle. It follows from the above claim that the shortest path can be computed by first computing the visibility graph and labeling each edge with its Euclidean length, and then computing the shortest path by, say, Dijkstra's algorithm . Note that the visibility graph is not planar, and hence may consist of \(O\big( n^{2}\big)\) edges.

Dijkstra(G,start) finds all shortest paths from \(L_{i}\) to each other vertex in the graph, and shortestPath(G,Li,Lf) uses Dijkstra to find the shortest path from \(L{i}\) to \(L_{f}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

from priodict import priorityDictionary

def Dijkstra(G,start,end=None):
    """
    Find shortest paths from the start vertex to all
    vertices nearer than or equal to the end.

    """

    D = {}  # dictionary of final distances
    P = {}  # dictionary of predecessors
    Q = priorityDictionary()   # est.dist. of non-final vert.
    Q[start] = 0

    for v in Q:
        D[v] = Q[v]
        if v == end: break

        for w in G[v]:
            vwLength = D[v] + G[v][w]
            if w in D:
                if vwLength < D[w]:
                    raise ValueError, \
            elif w not in Q or vwLength < Q[w]:
                Q[w] = vwLength
                P[w] = v

    return (D,P)

def shortestPath(G,start,end):
    """
    Find a single shortest path from the given start vertex
    to the given end vertex.
    The input has the same conventions as Dijkstra().
    """

    D,P = Dijkstra(G,start,end)
    Path = []
    while 1:
        Path.append(end)
        if end == start: break
        end = P[end]
    Path.reverse()
    return Path