Identify if a point is within a polygon?

Question

I'm making a custom control in Delphi (inherited from TCustomControl) which consists of a number of polygon list items (irregular shapes). I need to implement mouse events per item, but first I need to be able to detect if the mouse position is within a given polygon (array of TPoint). I am catching the Hit Test message (WM_NCHITTEST) and this is where I will need to do this validation. I have a number of polygons, I will do a loop through each polygon item and perform this check to see if the mouse's X/Y position is within this polygon.

procedure TMyControl.WMNCHitTest(var Message: TWMNCHitTest);
var
  P: TPoint; //X/Y of Mouse
  Poly: TPoints; //array of TPoint
  X: Integer; //iterator
  I: TMyListItem; //my custom list item
begin
  P.X:= Message.XPos;
  P.Y:= Message.YPos;
  for X := 0 to Items.Count - 1 do begin
    I:= Items[X]; //acquire my custom list item by index
    Poly:= I.Points; //acquire polygon points

    //Check if Point (P) is within Polygon (Poly)...?

  end;
end;

Just to point out, I am missing one line of code `P:= ScreenToClient(P);` just after assigning `P.X` and `P.Y`. This converts those points from being relative to the screen to being relative to the control. — Jerry Dodge, May 10 '12 at 20:57
Of course it could be as easy as `P:= ScreenToClient(Point(Message.XPos, Message.YPos));` (turn 3 lines of code into one) — Jerry Dodge, May 10 '12 at 23:38

score 16 · Accepted Answer · answered May 10 '12 at 19:25

16

You can use PtInRegion:

function PointInPolygon(Point: TPoint; const Polygon: array of TPoint): Boolean;
var
  rgn: HRGN;
begin
  rgn := CreatePolygonRgn(Polygon[0], Length(Polygon), WINDING);
  Result := PtInRegion(rgn, Point.X, Point.Y);
  DeleteObject(rgn);
end;

answered May 10 '12 at 19:25

David Heffernan

601,492
42
1,072
1,490

This was my first idea as well. I assume the overhead of creating a GDI region isn't too bad (?). – Andreas Rejbrand May 10 '12 at 19:38
4

@Andreas I don't imagine the overhead is bad. GDI region should be very lightweight. If it was a problem then you could cache the regions alongside the polygons. – David Heffernan May 10 '12 at 19:39
Excellent! I won't have much of a problem with overhead because I don't expect this control to have many more than 20 list items (which is already a big number for this control). – Jerry Dodge May 10 '12 at 20:03
Note that this approach works fast for rectilinear polygons (region contains few internal rectangles) and decelerates for large regions with curved or slanted borders (when region contains a lot of internal rectangles) – MBo Mar 20 '14 at 10:58

score 5 · Answer 2 · answered May 10 '12 at 19:27

5

You can use the ray casting algorithm found here: http://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm

Most computer graphics classes use this as an example.

answered May 10 '12 at 19:27

MrWuf

1,478
1
14
30

score 2 · Answer 3 · answered Mar 20 '14 at 10:02

Checking if point is inside of a polygon can be done by imagining a horizontal line through that point, then from left to right counting how many times this imagined line crosses a polygon. If number of polygon crosses before hitting a point is odd then point is inside, if even then point is outside of a polygon.

score 0 · Answer 4 · answered Mar 26 '17 at 23:44

There is another technique that we use extensively, which doesn't involve any math at all and can handle extremely complex embedded controls of any shape at all. Simply have an off-screen image of the control with all the parts color-coded (as shown in the image below) that the user could click.

As they move their mouse, simply look at the color of the pixel underneath the mouse in our off-screen image and that tells us exactly what button/control they are over -- white for not over it, and any series of colors for the various parts.

Color mask

//Pseudo-Code

function MouseOverControl(LocalMousePos:TPoint):ControlID;
begin
   //sanity check
   Result:=IDNull;
   if (LocalMouse.X < 0) or (LocalMouse.X > ControlWidth) or 
      (LocalMouse.Y < 0) or (LocalMouse.Y > ControlHeight) then
          exit;
   case OffScreenControlMask.Canvas.Pixels[LocalMousePos.X,LocalMousePos.Y] of
    clwhite:exit;
    clRed:result:=ControlIDOne;
    clGreen:result:=ControlIDTwo;
    clBlue:result:=ControlIDThree;
  ... etc
   end;
end;

NOTE: The attached Color Mask image represents five identical circular controls broken up into quadrants with a center button (and since they all use the same colors we have constants for each color and we determine which one of the five the mouse is over by a simple XPosition) along with an additional irregular control to their right and a set or rectangular buttons beneath.

Identify if a point is within a polygon?

4 Answers4