Point in polygon hit test algorithm

Question

I need to test if a point hits a polygon with holes and isles. I'd like to understand how I'm supposed to do this. That's not documented and I can't find any explanation or examples.

What I do is count +1 for every outer polygon hit and -1 for every inner polygon hit. The resulting sum is:

• > 0: hit;
• <= 0: miss (outside or in a hole).

The HitData class separates paths based on winding number to avoid unnecessary recomputation of orientation. With Clipper.PointInPolygon() applied to every path the sum is easy to compute.

But there are two major drawbacks:

1. I have to apply Clipper.PointInPolygon() to EVERY path;
2. I can't leverage the hierarchy of PolyTree.

Can someone who has hands-on experience with Clipper (@angus-johnson?) clear up this confusion?

Again, my question is: how am I supposed to implement this? Am I re-inventing the wheel, while there's an actual solution readily available in the Clipper Library?

Side note: PolyTree still requires to test EVERY path to determine which PolyNode the point is in. There's no Clipper.PointInPolyTree() method and, thus, AFAIK PolyTree doesn't help.

The structure that separates outer and inner polygons:

public class HitData
{
    public List<List<IntPoint>> Outer, Inner;

    public HitData(List<List<IntPoint>> paths)
    {
        Outer = new List<List<IntPoint>>();
        Inner = new List<List<IntPoint>>();

        foreach (List<IntPoint> path in paths)
        {
            if (Clipper.Orientation(path))
            {
                Outer.Add(path);
            } else {
                Inner.Add(path);
            }
        }
    }
}

And this is the algorithm that tests a point:

public static bool IsHit(HitData data, IntPoint point)
{
    int hits;

    hits = 0;

    foreach (List<IntPoint> path in data.Outer)
    {
        if (Clipper.PointInPolygon(point, path) != 0)
        {
            hits++;
        }
    }

    foreach (List<IntPoint> path in data.Inner)
    {
        if (Clipper.PointInPolygon(point, path) != 0)
        {
            hits--;
        }
    }

    return hits > 0;
}

Answer 1

Can someone who has hands-on experience with Clipper (@angus-johnson?) clear up this confusion?

It's not clear to me what your confusion is. As you've correctly observed, the Clipper library does not provide a function to determine whether a point is inside multiple paths.

Edit (13 Sept 2019):

OK, I've now created a PointInPaths function (in Delphi Pascal) that determines whether a point is inside multiple paths. Note that this function accommodates the different polygon filling rules.

function CrossProduct(const pt1, pt2, pt3: TPointD): double;
var
  x1,x2,y1,y2: double;
begin
  x1 := pt2.X - pt1.X;
  y1 := pt2.Y - pt1.Y;
  x2 := pt3.X - pt2.X;
  y2 := pt3.Y - pt2.Y;
  result := (x1 * y2 - y1 * x2);
end;


function PointInPathsWindingCount(const pt: TPointD;
  const paths: TArrayOfArrayOfPointD): integer;
var
  i,j, len: integer;
  p: TArrayOfPointD;
  prevPt: TPointD;
  isAbove: Boolean;
  crossProd: double;
begin
  //nb: returns MaxInt ((2^32)-1) when pt is on a line
  Result := 0;
  for i := 0 to High(paths) do
  begin
    j := 0;
    p := paths[i];
    len := Length(p);
    if len < 3 then Continue;
    prevPt := p[len-1];
    while (j < len) and (p[j].Y = prevPt.Y) do inc(j);
    if j = len then continue;
    isAbove := (prevPt.Y < pt.Y);
    while (j < len) do
    begin
      if isAbove then
      begin
        while (j < len) and (p[j].Y < pt.Y) do inc(j);
        if j = len then break
        else if j > 0 then prevPt := p[j -1];
        crossProd := CrossProduct(prevPt, p[j], pt);
        if crossProd = 0 then
        begin
          result := MaxInt;
          Exit;
        end
        else if crossProd < 0 then dec(Result);
      end else
      begin
        while (j < len) and (p[j].Y > pt.Y) do inc(j);
        if j = len then break
        else if j > 0 then prevPt := p[j -1];
        crossProd := CrossProduct(prevPt, p[j], pt);
        if crossProd = 0 then
        begin
          result := MaxInt;
          Exit;
        end
        else if crossProd > 0 then inc(Result);
      end;
      inc(j);
      isAbove := not isAbove;
    end;
  end;
end;

function PointInPaths(const pt: TPointD;
  const paths: TArrayOfArrayOfPointD; fillRule: TFillRule): Boolean;
var
  wc: integer;
begin
  wc := PointInPathsWindingCount(pt, paths);
  case fillRule of
    frEvenOdd: result := Odd(wc);
    frNonZero: result := (wc <> 0);
  end;
end;

With regards leveraging the PolyTree structure:

The top nodes in PolyTree are outer nodes that together contain every (nested) polygon. So you'll only need to perform PointInPolygon on these top nodes until a positive result is found. Then repeat PointInPolygon on that nodes nested paths (if any) looking for a positive match there. Obviously when an outer node fails PointInPolygon test, then its nested nodes (polygons) will also fail. Outer nodes will increment the winding count and inner holes will decrement the winding count.