Solved

Polygon algorithm

Posted on 2003-12-09
3
2,007 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

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

The uses clause is one of those things that just tends to grow and grow. Most of the time this is in the main form, as it's from this form that all others are called. If you have a big application (including many forms), the uses clause in the in…
Hello everybody This Article will show you how to validate number with TEdit control, What's the TEdit control? TEdit is a standard Windows edit control on a form, it allows to user to write, read and copy/paste single line of text. Usua…
The Email Laundry PDF encryption service allows companies to send confidential encrypted  emails to anybody. The PDF document can also contain attachments that are embedded in the encrypted PDF. The password is randomly generated by The Email Laundr…
In an interesting question (https://www.experts-exchange.com/questions/29008360/) here at Experts Exchange, a member asked how to split a single image into multiple images. The primary usage for this is to place many photographs on a flatbed scanner…

821 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