Polygon Expansion

Polygon expansion / contraction

download Delphi project

download program

This Delphi project shows expansion and contraction of polygons.
Below is a picture of the project at work:

The grey lines are the original polygon, the black lines form the contracted polygon.
The process uses basic vector operations. So, I start with a brief explanation.

Vector geometry in a plane.

A vector (V) in 2D is a line segment defined by dx and dy (horizontal and vertical distances).

Vector addition

Multiplication by a scalar

Equation of a line

Intersection of lines

Parallel shift

Vector direction
(in radians)

Left and Right orientation
Left picture: counterclockwise (CCW). Right: clockwise (CW).

Expansion algorithm

A right shift of vectors is needed if

In other cases a left shift must take place.
The new points are the intersections of the shifted vectors.

Before expansion, the vector list is created from the list of points.
The angles between connecting vectors are summed to know CW or CCW orientation.

Using the vector list, the new points are calculated.

The program

 const offset = 0.025;           //displacement
    pi05 = 0.5*pi;
    pi15 = 1.5*pi;
    pi2 = 2*pi;

Vector direction

function VDir(deltaX,deltaY : single) : single;
//return direction of vector in radians
//(+,0) = 0; (0,+) = 0.5pi ; (-,0) = pi ; (0,-) = 1.5pi
begin
 if deltaX = 0 then
  begin
   if deltaY > 0 then result := pi05 else result := pi15;
   exit;
  end;
 result := arctan((deltaY)/(deltaX));
 if deltaX < 0 then result := result + pi;
 if result < 0 then result := result + pi2;
end;

Angle between vectors

function V12angle(dir1,dir2 : single) : single;
//return angle between vectors v1,v2 in radians
begin
 result := dir2 - dir1;
 if result > pi then result := result-pi2
  else if result < -pi then result := result+pi2;
end;

Summing the angles

function SumAngles : single;
var i : byte;
begin
 result := 0;
 for i := 1 to vcount-1 do
   result := result + V12Angle(vectorlist[i].dir,vectorlist[i+1].dir);
 result := result + V12Angle(vectorlist[vcount].dir,vectorlist[1].dir);
end;

Data formats

Const maxpoint = 40;
type  Tvector = record
                x,y   : single;
                dx,dy : single;
                dir   : single;       //direction 0..+-pi
                modulus : single;
               end;
     TVectorList = array[1..maxpoint] of TVector;
     TFpoint = record
                x : single;
                y : single;
               end;
     TFpoints = array[1..maxpoint] of TFpoint;
var Fpoints : TFpoints;   //in interface 
    pcount : byte;        //number of points
    vectorlist : TVectorlist;//in implementation
    vcount : byte;           //number of vectors

Vector shifting

procedure shiftvector(var v : Tvector; R : boolean);
//R : true for right shift
var dd,m: single;
begin
 if R then m := 1 else m := -1;
 with v do
  begin
   dd := offset/modulus;
   x := x+dd*dy*m;
   y := y-dd*dx*m;
  end;
end;

Form and buttons

The polygon is painted on a bitmap which is copied to form1.paintbox1.

Units
Unit1 holds the procedures for drawing and the event handlers.
The poly_unit takes care of the polygon specific procedures and data.
The clock_unit supplies a microseconds clock to measure processing time and
control the expansion speed.

For details please refer to the source code.

Operations

drawing a polygon
[draw] button down.

modify a polygon
[modify] button down

[undo] : remove last added vector.
[clear] : erase polygon
[save] : polygon is stored and remains drawn in grey.
[reload]: restore saved polygon.