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
    - the polygon is CW oriented and
    - expansion is required
    - polygon is CW oriented and
    - contraction is requested
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
 if deltaX = 0 then
   if deltaY > 0 then result := pi05 else result := pi15;
 result := arctan((deltaY)/(deltaX));
 if deltaX < 0 then result := result + pi;
 if result < 0 then result := result + pi2;
Angle between vectors
function V12angle(dir1,dir2 : single) : single;
//return angle between vectors v1,v2 in radians
 result := dir2 - dir1;
 if result > pi then result := result-pi2
  else if result < -pi then result := result+pi2;
Summing the angles
function SumAngles : single;
var i : byte;
 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);
Data formats
Const maxpoint = 40;
type  Tvector = record
                x,y   : single;
                dx,dy : single;
                dir   : single;       //direction 0..+-pi
                modulus : single;
     TVectorList = array[1..maxpoint] of TVector;
     TFpoint = record
                x : single;
                y : single;
     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;
 if R then m := 1 else m := -1;
 with v do
   dd := offset/modulus;
   x := x+dd*dy*m;
   y := y-dd*dx*m;

Form and buttons

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

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.


drawing a polygon
[draw] button down.
    - mouse DOWN on paintbox and move
    - mouse UP to end.
modify a polygon
[modify] button down
    - mouse DOWN on point and move
    - mouse UP to stop
[undo] : remove last added vector.
[clear] : erase polygon
[save] : polygon is stored and remains drawn in grey.
[reload]: restore saved polygon.