多边形命中测试算法中的点

Question

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

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

> 0：命中；
<= 0: 未命中（在洞外或洞内）。

HitData class 根据绕组数分隔路径以避免不必要的重新计算 orientation。 Clipper.PointInPolygon() 应用于每个路径总和很容易计算。

但是有两个主要缺点：

我必须将 Clipper.PointInPolygon() 应用到 EVERY path;
我无法利用 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 测试时，其嵌套节点（多边形）也将失败。外部节点将增加绕组数，内部孔将减少绕组数。

多边形命中测试算法中的点

Point in polygon hit test algorithm

clipperlib