clipperlib - 多边形中的点 HitTest 算法

Question

我需要测试一个点是否击中带有孔和岛的多边形。我想了解我应该如何做到这一点。这没有记录，我找不到任何解释或示例。

我所做的是对每个外部多边形命中计数+1，对每个内部多边形计数-1打。结果总和是:

• > 0:命中；
• <= 0:未命中(在洞外或洞内)。

HitData 类根据绕数分隔路径，以避免不必要的方向重新计算。通过将 Clipper.PointInPolygon() 应用于每个路径，总和很容易计算。

但是有两个主要缺点:

1. 我必须将 Clipper.PointInPolygon() 应用于每个 路径；
2. 我无法利用 PolyTree 的层次结构。

有过 Clipper 实践经验的人( @angus-johnson ？)可以解答这个困惑吗？

我的问题是:我应该如何实现这个？尽管 Clipper 库中已经提供了实际的解决方案，但我是否要重新发明轮子？

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.

分隔外部和内部多边形的结构:

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);
            }
        }
    }
}

这是测试点的算法:

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?

我不清楚你的困惑是什么。正如您所观察到的，Clipper 库没有提供函数来确定一个点是否位于多个路径内。

编辑(2019 年 9 月 13 日):

好的，我现在已经创建了一个 PointInPaths 函数(在 Delphi Pascal 中)，用于确定一个点是否位于多个路径内。请注意，此函数适应不同的多边形填充规则。

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;

关于利用 PolyTree 结构:

PolyTree 中的顶部节点是外部节点，它们一起包含每个(嵌套)多边形。因此，您只需要在这些顶部节点上执行PointInPolygon，直到找到肯定的结果。然后在该节点嵌套路径(如果有)上重复PointInPolygon，寻找正匹配。显然，当外部节点未通过 PointInPolygon 测试时，其嵌套节点(多边形)也会失败。外部节点将增加缠绕数，内部孔将减少缠绕数。