1 - The basics

The basics of computational geometry

In this section I will introduce the basics of computational geometry.

Assume that I am working in a 2-dimensional space expect if I explicitly state otherwise. (I haven't decided if I will look at more dimensions)

Points

A point p = (x, y) consist of two real numbers indicating its position along the two coordinates.

In Ruby a point can be represent by

Point = Struct.new(:x, :y)

where I assume that x and y is real numbers. (One could add a check)

Whenever I talk about a point representing a vector then I mean the vector from (0,0) to (x,y)

Line-Segments

A line segment is the line spanning between two points p1 = (x1,y1) and p2 = (x2,y2).

In ruby it could be represent by a struct:

LineSegment = Struct.new(:p1, :p2)

where p1 and p2 both are Points.

Note that a directed line segment can be considered as a vector. Whenever I talk about a directed line segment then I mean from p1 to p2. Likewise I may use LineSegment to represent a vector between two points.

Polygons

A polygon can be consider to consist of at least 3 points in a sequence. Creating LineSegments for each consecutive pair of points and for the first and last point will then create the edges in the polygon.

class Polygon

attr_reader :ps

attr_reader :edges

def initialize(p1, p2, p3, *ps)

@ps = [p1, p2, p3] + ps

create_edges

end

def create_edges

@edges = []

for i in -1...(ps.size-1)

@edges << LineSegment.new(ps[i], ps[i+1])

end

end

end

Orientation

The orientation of the coordinate system is also to be considered. The typical one in math is the one where x is the horizontal axis decreasing towards west and increasing towards east and y is the vertical axis increasing towards north and decreasing towards south. It can be split into 4 quadrants where quadrant 1 is the area were x and y are not negative. Quadrant 2 is the area where y is not negative and x is not positive. Quadrant 3 is the area where x and y is not positive. Quadrant 4 is the area where x is not negative and y is not positive.

If we mirror the coordinate system along the horizonal axis and then only look at quadrant 4 for 0 <= x <= 640 and 0 <= y <= 480 we have the visible section of rmxp games.

Basically y increases when moving towards south and decreases when moving towards north.