Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# Polygon algorithm

Posted on 2003-12-09
Medium Priority
2,018 Views
In delphi, we can draw a polygon by using array of TPoint :

Canvas.Polygon(Points: Array of TPoint);

How can we know that a TPoint is "inside" that polygon ? I meant like "hit test" function.

For rectangle (x1,y1,x2,y2), I can use this "If" clause :

// Testing P.X and P.Y
if (P.X >= x1) And (P.Y >= y1) And (P.X <= x2) And (P.Y <= y2) then HIT := TRUE;

Anyone know the algorithm ?
0
Question by:klompen
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 26

Expert Comment

ID: 9905777

You could create a region, and use the PtInRegion to determine if the point falls inside the polygon.

eg:

function PtInPolygon(Point: TPoint; Polygon: Array of TPoint): Boolean;
var  hrgnPoly:      HRGN;
begin

// Create polygon region
hrgnPoly:=CreatePolygonRgn(Polygon, Succ(High(Polygon)), WINDING);

// Make sure the region was created
if (hrgnPoly = 0) then
// Failure
result:=False
else
begin
// Check to see if point lies inside of the region
result:=PtInRegion(hrgnPoly, Point.X, Point.Y);
// Delete the region
DeleteObject(hrgnPoly);
end;

end;

Example usage (draws a triangle on the form and checks to see if mouse down event is in the triangle):

procedure TForm1.FormMouseDown(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer);
begin

if PtInPolygon(Point(X, Y), [Point(100, 100), Point(140, 1), Point(180, 100)]) then
ShowMessage('Point in polygon');

end;

procedure TForm1.FormPaint(Sender: TObject);
begin

// Draw the polygon so you have something visual to go by
Canvas.Polygon([Point(100, 100), Point(140, 1), Point(180, 100)]);

end;

Also, for the rectangle, there is a PtInRect function that you could use...

Hope this helps,
Russell

0

LVL 1

Accepted Solution

mgazza earned 260 total points
ID: 9906225
or use this function

function PointInPoly(APoint : TPoint ; APoly : array of TPoint) : boolean;
Var
i, j : integer;
npol : integer;
begin
Result := false;
npol := length(APoly);
for i := 0 to npol - 1 do begin
j := (i + 1) mod npol;
if ((((APoly[i].Y <= APoint.Y) and (APoint.Y < APoly[j].Y)) or
((APoly[j].Y <= APoint.Y) and (APoint.Y < APoly[i].Y))) and
(APoint.X < (APoly[j].X - APoly[i].X) * (APoint.Y - APoly[i].Y) /
(APoly[j].Y - APoly[i].Y) + APoly[i].X)) then
Result := not Result;
end;
end;
0

LVL 7

Expert Comment

ID: 9906813
You might like to explore the math behind a concept called the "convex hull", e.g., at http://mathworld.wolfram.com/ConvexHull.html
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article explains how to create forms/units independent of other forms/units object names in a delphi project. Have you ever created a form for user input in a Delphi project and then had the need to have that same form in a other Delphi proj…