Board index » delphi » URGENT: determine if point is within polygon

URGENT: determine if point is within polygon

Hi,

I have written an algorithm long ago that was able to determine whether
a
point was within a polygon or not (something like: if the number of
times a line, starting from the point, going outwards, crosses the
polylines is odd then the point is within the polygon).
However, I can't find it anywhere and I really need this in a short
timeframe!!
Can anyone help me with sourcecode solving this problem (preferably
short...)

TIA Doef.

 

Re:URGENT: determine if point is within polygon


check the WIN32 help file on regions. You need to create the ploygon region,
then you can test for PtInRegion

example :

function PtInPolygon( const pt : TPoint; points ; array of TPoints);
var
   region : HRGN;
begin
   region := CreatePolygonRgn(Points, Length(Points), Alternate);
   result := PtInRegion( region, pt.x, pt.y );
   deleteobject( region );
end;

kevanB

Re:URGENT: determine if point is within polygon


Quote
"Oene Doevendans" <Doevend...@fel.tno.nl> wrote in message

news:39F6A8C6.7097F1AA@fel.tno.nl...
| Hi,
|
| I have written an algorithm long ago that was able to determine whether
| a
| point was within a polygon or not (something like: if the number of
| times a line, starting from the point, going outwards, crosses the
| polylines is odd then the point is within the polygon).
| However, I can't find it anywhere and I really need this in a short
| timeframe!!
|
| Can anyone help me with sourcecode solving this problem (preferably
| short...)
|

----------------------------------------------------------------------
Subject 2.03: How do I find if a point lies within a polygon?

The definitive reference is "Point in Polygon Strategies" by
Eric Haines [Gems IV] pp. 24-46.
The code in the Sedgewick book Algorithms (2nd Edition, p.354) is
incorrect.

The essence of the ray-crossing method is as follows.
Think of standing inside a field with a fence representing the polygon.
Then walk north. If you have to jump the fence you know you are now
outside the poly. If you have to cross again you know you are now
inside again; i.e., if you were inside the field to start with, the total
number of fence jumps you would make will be odd, whereas if you were
ouside the jumps will be even.
The code below is from Wm. Randolph Franklin <w...@ecse.rpi.edu
<mailto:w...@ecse.rpi.edu>>
with some minor modifications for speed. It returns 1 for strictly
interior points, 0 for strictly exterior, and 0 or 1 for points on
the boundary. The boundary behavior is complex but determined;
in particular, for a partition of a region into polygons, each point
is "in" exactly one polygon. See the references below for more detail.

int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
int i, j, c = 0;
for (i = 0, j = npol-1; i < npol; j = i++) {
if ((((yp[i]<=y) && (y<yp[j])) ||
((yp[j]<=y) && (y<yp[i]))) &&
(x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))

c = !c;

Quote
}
return c;
}

The code may be further accelerated, at some loss in clarity, by
avoiding the central computation when the inequality can be deduced,
and by replacing the division by a multiplication for those processors
with slow divides. For code that distinguishes strictly interior
points from those on the boundary, see [O'Rourke (C)] pp. 239-245.

References:
[Gems IV] pp. 24-46
[O'Rourke (C)]
[Glassner:RayTracing]

Re:URGENT: determine if point is within polygon


In article <39F6A8C6.7097F...@fel.tno.nl>, Doevend...@fel.tno.nl says...
Quote
> point was within a polygon or not

I'd be inclined to use CreatePolygonRgn() to create a region matching the
polygon's shape, and then call PtInRegion() to determine whether the
point is within it. What the heck - make Windows do the work!
--
Neil J. Rubenking
Contributing Technical Editor
PC Magazine

Re:URGENT: determine if point is within polygon


Quote
"Neil J. Rubenking" wrote:

> I'd be inclined to use CreatePolygonRgn() to create a region matching the
> polygon's shape, and then call PtInRegion() to determine whether the
> point is within it. What the heck - make Windows do the work!
> --

My sentiments exactly Neil (and KevanB). I'll give it a try!

Thanks all for replying so soon (and no Earl, it's not a home
assignment, I'm past that for over 15 years now... thanks for your
suggestions anyway!).

Re:URGENT: determine if point is within polygon


  TPolygon = array[0..0] of TPoint;
  PPolygon = ^TPolygon;

function PointInPolygon(P: TPoint; Polygon: PPolygon; Points: Integer);
  { Returns:  1 = point P inside polygon }
  {           0 = point P on edge of polygon }
  {          -1 = point P outside polygon }
var
  Index      : Integer;
  Count      : Integer;
  { Vars for calculating intersection between partition and division line. }
  { Use real types (Extended) to avoid aritmetic overflow.                 }
  Denominator: Extended;
  Numerator  : Extended;
  Fraction   : Extended;
  XPar,YPar  : Extended; {starting point of partition line}
  XDiv,YDiv  : Extended; {starting point of division line}
  dXPar,dYPar: Extended; {delta (slope) of partition line}
  dXDiv,dYDiv: Extended; {delta (slope) of division line}

begin
  Result := -1;
  if Points < 2 then Exit;

  { Compute the delta X and delta Y for the partition line. }
  { As partition line for the calculations we use a line    }
  { starting in point P and extending 10 values rightwards. }
  XPar := P.X;
  dXPar := XPar+10.0; {extend orignal point to make a line}
  dXPar := dXPar-XPar;
  YPar := P.Y;
  dYPar := YPar;
  dYPar := dYPar-YPar;

  Count := 0;
  Index := 0;
  while (Index < Points) and (Result <> 0) do begin
    { Compute the delta X and delta Y for the current division (edge)
line. }
    XDiv := Polygon^[Index].X;
    dXDiv := Polygon^[(Index+1) mod Points].X;
    dXDiv := dXDiv-XDiv;
    YDiv := Polygon^[Index].Y;
    dYDiv := Polygon^[(Index+1) mod Points].Y;
    dYDiv := dYDiv-YDiv;

    { Compute denominator and numerator to find the relation }
    { of the division line to the partition line.}
    Denominator := (dYPar*dXDiv)-(dXPar*dYDiv);
    Numerator := ((XPar-XDiv)*dYPar)+((YDiv-YPar)*dXPar);

    if not (Denominator = 0.0) then begin
    { The lines are not parallel. }
      { Calculat the fraction of the division line for the intersection
point. }
      Fraction := Numerator/Denominator;

      if (Fraction >= 0.0) and (Fraction < 1.0) then begin
      { The intersection point is between the starting and ending }
      { point of the division line, or on it's starting point. }
      { For each line we include the starting point but not the }
      { ending point as part of the line. The ending point of a }
      { given line will be the starting point of the next line. }

        { Recompute denominator, numerator, and fraction to find }
        { the relation of the partition line to the division line.}
        Denominator := (dYDiv*dXPar)-(dXDiv*dYPar);
        Numerator := ((XDiv-XPar)*dYDiv)+((YPar-YDiv)*dXDiv);
        Fraction := Numerator/Denominator;

        if Fraction = 0.0 then Result := 0 { point P is on the edge }
        else if Fraction > 0.0 then Inc(Count);
      end;
    end;

    Inc(Index);
  end;

  if Result <> 0 then begin
    if Count and 1 > 0 then Result := 1
    else Result := -1;
  end;
end;

Re:URGENT: determine if point is within polygon


"Neil J. Rubenking" <jrubenki@SPAM-B-G...@mother.com> wrote in message
news:MPG.14607cf2aad345cc9896fb@newsgroups.borland.com...

Quote
> In article <39F6A8C6.7097F...@fel.tno.nl>, Doevend...@fel.tno.nl says...
> > point was within a polygon or not

> I'd be inclined to use CreatePolygonRgn() to create a region matching the
> polygon's shape, and then call PtInRegion() to determine whether the
> point is within it. What the heck - make Windows do the work!
> --
> Neil J. Rubenking
> Contributing Technical Editor
> PC Magazine

-----------------------------------------------------------------------
This solution is brought to you by Joe Hecht's TExcellent products,
solving Form.Print and bitmap printing problems. Joe Hecht's TExcellent
products can be found at: http://www.code4sale.com/joehecht
-----------------------------------------------------------------------

Good point. I will point out that Windows will rasterize the entire
region into scanline segments, and for a very large region, this has
been the source of GDI memory problems in the past (and
present).

For the most part, I like to zip though the poly's lines, throwing
out all that do not cross though the y coordinate in question, and that
are left of the x coordinate in question, then count the number of
crossings for the remaining lines to the right. You can use the
Odd/Even method (if the number of crossings is odd, your inside),
or you can choose to inc your count if the vector your crossing is
"rising", and dec your count if the vector your crossing is "falling",
and your inside when the count is non-zero. Both of these methods
require special handeling of the case where you pass though the point
of the vector (and not through the vector itself).

Performace is another issue entirly. If you need to do many such
tests on a polygon, a faster method is to draw the polygon to a
monochrome bitmap (DIB), then simply test if the pixel location in
question is black or white. Very fast, but can uses a lot of
memory.

Glad to see ya back in the newsgroups Neil... we have missed you :)

 Joe

Re:URGENT: determine if point is within polygon


Quote
> Performace is another issue entirly. If you need to do many such
> tests on a polygon, a faster method is to draw the polygon to a
> monochrome bitmap (DIB), then simply test if the pixel location in
> question is black or white. Very fast, but can uses a lot of
> memory.

Have you made a speed comparison of this? I do a lot of such tests as athe
mouse moves over a map image,using a ptInrect first to "home" in on a given
polygon region.. I dont unfortunetly have the time this week to undertake
such a test..

KevanB

Other Threads