Polyline fits inside another?

Hi,
I have two closed polylines. Is there a way to find out if one polyline can fit inside another?
Thanks,
Mike

 

You could transform one polyline so that it's first vertex lines up with the
first vertex of the other. Then check to see if each vertice on the first is
inside the boundary of the second polyline.

Here's an alogithm that determines whether or not a point lies inside a
polyline. It's written in Delphi (Pascal) but it should give you an idea of
how to procede.

[pre]

{------------------------------------------------------------------------------}

type
TPoint2D = Record
X: Double;
Y: Double;
end;

{------------------------------------------------------------------------------}

function Angle2D(P1, P2: TPoint2D): Double;
var
Delta: Double;
Theta1: Double;
Theta2: Double;
begin
Theta1 := ArcTan2(P1.Y, P1.X);
Theta2 := ArcTan2(P2.Y, P2.X);
Delta := Theta2 - Theta1;

while Delta > PI do
begin
Delta := Delta - (2 * PI);
end;

while Delta < -PI do
begin
Delta := Delta + (2 * PI);
end;

Result := Delta;
end;

{------------------------------------------------------------------------------}

function IsInsidePolygon(Vertices: array of TPoint2D; Point: TPoint2D): Boolean;
var
Angle: Double;
I: Integer;
P1: TPoint2D;
P2: TPoint2D;
begin
Angle := 0;
for I := Low(Vertices) to High(Vertices) - 1 do
begin
P1.X := Vertices.X - Point.X;
P1.Y := Vertices.Y - Point.Y;
P2.X := Vertices[I + 1].X - Point.X;
P2.Y := Vertices[I + 1].Y - Point.Y;
Angle := Angle + Angle2D(P1, P2);
end;

if Abs(Angle) < PI then
begin
Result := FALSE;
end
else
begin
Result := TRUE;
end;
end;

{------------------------------------------------------------------------------}
[/pre]

 

That's a good idea, but it is incomplete. Lining up the first vertex of one with the first vertex of the other may result in overlapping, whereas lining up the fourth vertex of one with the seventh vertex of the other may be produce a compliant result.

Further, depending on the requirements/constraints of the original problem it may be possible to produce a solution only by mirroring one of the polylines.

Finally, it still may not be possible to get a solution where *any* of the vertices are lined up (ie touching) but might be possible if the interior polyline was moved further in (ie away) from all the vertices. For this situation imagine a big star and a slightly smaller star inside - if you were to coincide any of their points there would be overlaps but if you aligned their centroids and rotated the inner one appropriately you would get a solution.

After all that, I'm sorry I'm not providing an actual answer to the original question. You may like to seek a mathematical answer at the Dr Math forum http://mathforum.org/dr.math/ .

Regards

Wayne Ivory
IT Analyst Programmer
Wespine Industries Pty Ltd