Polygon: basic manipulations

In this post we will show how to manipulate polygons. First things, the best way to manipulate them is to store them in a linked list way, i.e. we define a polygon by the start point and each point is linked with its two neighbors, respecting the clockwise rule.

Left: clockwise polygon definition, right: counter-clockwise polygon definition

The area of the polygon is defined to the right of the vector formed by two consecutive points. You can see in the example, with two same set of points simply defined in the reverse order, we have one time the desired polygon and the second time the inversed area.

Now we want to have some operations on those polygons. First one is the membership of a point to the polygon. This is a known problem in computational geometry, called PIP for Point In Polygon: on Wikipedia. I choose to use the winding algorithm to solve this problem to avoid potential round error.

public function isPointInside(px:Number, py:Number):Boolean {
   var counter:int = 0;
   var xinters:Number;
   var p1:WPoint;
   var p2:WPoint;
   p1 = start;
   p2 = p1;
   do {
      p2 = p1.next;
      if (py > Math.min(p1.y, p2.y)) {
         if (py <= Math.max(p1.y, p2.y)) {
            if (px <= Math.max(p1.x, p2.x)) {
               if (p1.y != p2.y) {
                  xinters = (py - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x;
                  if (p1.x == p2.x || px <= xinters) { counter++; }
               }
            }
         }
      }
   }while((p1 = p1.next) != start);
   if (counter % 2 == 0) {
      return(false);
   } else {
      return(true);
   }
}
 

Now we can call this function to know if a given point is inside or outside a polygon. Note the method to use to iterate over the points of a polygon, like with Linked List. The complexity is O(n) where n is the number of points in the polygon. To have complete code, you also need the code of the classes.

public class WPolygon {
   public var start:WPoint;
}
public class WPoint {
   public var prev, next:WPoint;
   public var x:Number, y:Number;
   public var parent:*;
}
 

Next useful function is how to compute the area of the polygon. Without entering into details, there is a very simple algorithm to compute the area by adding partial projection for each couple of points.

public function area():Number {
   if(start.prev == start.next) {
      throw new Error("Area of polygon needs at least three points");
   }
   var result:Number = 0;
   var curr:WPoint = start;
   do {
      result += curr.x * curr.next.y - curr.next.x * curr.y;
   }while((curr = curr.next) != start) ;
   result /= 2;
   return result;
}
 

The algorithm comes from Polygon Area where you can find a little illustrated example to understand the method. The complexity is O(n) where n is the number of points in the polygon.
To finish this initial post, we show you the basic functions of adding/removing points. Note that we suppose that when we remove the point, we already know which point in the polygon we want to remove, i.e. we already have the pointer to it (and especially to its neighbors).

public function addPoint(x:Number, y:Number):WPoint {
   var nPoint:WPoint = new WPoint(x, y);
   
   start.prev.next = nPoint;
   nPoint.prev = start.prev;
   start.prev = nPoint;
   nPoint.next = start;
   
   nPoint.parent = this;
   
   return nPoint;
}

public function removePoint(point:WPoint):void {
   if(point.parent != this) {
      throw new Error("Removal fails, the point isnt in the polygon");
   }
   point.prev.next = point.next;
   point.next.prev = point.prev;
   point.parent = null;
}
 

You notice we returned the new point in the add function. If you want to use the point you need to use this pointer because it has the links to the neighbor points and the parent pointer set. Like in Linked List, the insertion and deletion is done in O(1) by simply setting the neighbors' pointers.