Basic geometry functions

In this article we will see how to implement some basic geometry functions in 2D space. We will wirte line segment intersection and circumcircle.

Let's start with writing some basic functions. Then we will write next, more complexed functions. We can write them as static methods of Geometry class.

Distance between two points

We will count it using Pythagorean theorem ($c = \sqrt{a\times a + b \times b}$).

Code

public static function Distance(a, b):Number
{
   return(Math.sqrt( (b.x-a.x)*(b.x-a.x) + (b.y-a.y)*(b.y-a.y) ));
}

If a point is inside of a rectangle

Let's have rectangle, which is defined by top left corner and bottom right corner ("b" a "c"). We will ask, whether point "a" lies inside the rectengle. a.x must lie between b.x and c.x, same for a.y.

Code

public static function InRect(a, b, c):Boolean
{
   if(a.x >= Math.min(b.x, c.x) && a.x <= Math.max(b.x, c.x)
   && a.y >= Math.min(b.y, c.y) && a.y <= Math.max(b.y, c.y)) 
   return true;
   return false;
}

Intersection of two line segments

Let's have line segments "a" and "b" defined by two points (starting points "a1", "b1", and ending points "a2", "b2"). We want to know, whether they intersect each other. Firstly, we find the intersection of lines "a", "b". Then we check, whether that intersection point is located between starting and ending point of each line.

I use this formula for computing intersection. It is based on determinants.

Code

public static function GetLineIntersection(a1, a2, b1, b2):Point
{
   var dax = (a1.x-a2.x), dbx = (b1.x-b2.x);
   var day = (a1.y-a2.y), dby = (b1.y-b2.y);
			
   var Den = dax*dby - day*dbx;
   if (Den == 0) return null;	// parallel

   var A = (a1.x * a2.y - a1.y * a2.x);
   var B = (b1.x * b2.y - b1.y * b2.x);
			
   var I = new Point(0,0);
   I.x = ( A*dbx - dax*B ) / Den;
   I.y = ( A*dby - day*B ) / Den;
			
   if(InRect(I, a1, a2) && InRect(I, b1, b2)) return I;
   return null;
}

Circumcenter

Let us have three points (a, b, c). We are looking for a circle (center and radius), which intersects all three points. This circumcenter is the intersection of normals (a,b) and (b,c). Radius is distance between circumcenter and a (or b, or c).

Code

public static function GetCircumcenter(a, b, c):Point
{
   // m1 - center of (a,b), the normal goes through it
   var f1 = (b.x - a.x) / (a.y - b.y);
   var m1 = new Point((a.x + b.x)/2, (a.y + b.y)/2);
   var g1 = m1.y - f1*m1.x;

   var f2 = (c.x - b.x) / (b.y - c.y);
   var m2 = new Point((b.x + c.x)/2, (b.y + c.y)/2);
   var g2 = m2.y - f2*m2.x;

   // degenerated cases
   // - 3 points on a line
   if     (f1 == f2)   return null;
   // - a, b have the same height -> slope of normal of |ab| = infinity
   else if(a.y == b.y) return new Point(m1.x, f2*m1.x + g2);
   else if(b.y == c.y) return new Point(m2.x, f1*m2.x + g1);

   var x:Number = (g2-g1) / (f1 - f2);
   return new Point(x, f1*x + g1);
}