
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
or
 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
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 := resultpi2
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 vcount1 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 := ydd*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.
 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.
