Solved

Polygon algorithm

Posted on 2003-12-09
3
2,009 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
[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
  • Learn & ask questions
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

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Delphi application Soap connection 5 151
Delphi 2 87
How to save the image in the .cds File ClientDataSet? 1 40
Firemonkey Queue list 1 49
Creating an auto free TStringList The TStringList is a basic and frequently used object in Delphi. On many occasions, you may want to create a temporary list, process some items in the list and be done with the list. In such cases, you have to…
In my programming career I have only very rarely run into situations where operator overloading would be of any use in my work.  Normally those situations involved math with either overly large numbers (hundreds of thousands of digits or accuracy re…
How to Install VMware Tools in Red Hat Enterprise Linux 6.4 (RHEL 6.4) Step-by-Step Tutorial

739 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