Basic Shapes, Polygons and Trigonometery

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, require 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, and 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 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 and $b$ is the $y$-intercept: $m = \frac{\Delta y}{\Delta x}$.

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 representations 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 = point_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)