Solved

Polygon algorithm

Posted on 2003-12-09
3
2,001 Views
Last Modified: 2012-06-27
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
Comment
Question by:klompen
3 Comments
 
LVL 26

Expert Comment

by:Russell Libby
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

by:
mgazza earned 65 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

by:sftweng
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

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…
Have you ever had your Delphi form/application just hanging while waiting for data to load? This is the article to read if you want to learn some things about adding threads for data loading in the background. First, I'll setup a general applica…
When you create an app prototype with Adobe XD, you can insert system screens -- sharing or Control Center, for example -- with just a few clicks. This video shows you how. You can take the full course on Experts Exchange at http://bit.ly/XDcourse.
Need to grow your business through quality cloud solutions? With everything required to build a cloud platform and solution, you may feel like the distance between you and the cloud is quite long. Help is here. Spend some time learning about the Con…

932 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now