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

Question

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

我所做的是+1对每个外部多边形命中和-1每个内部多边形命中进行计数。所得总和为：

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

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

但有两个主要缺点：

1. 我必须适用Clipper.PointInPolygon()于每一条 道路；
2. 我无法利用 的层次结构PolyTree。

有 Clipper 实践经验的人（@angus-johnson？）可以消除这种困惑吗？

我的问题再次是：我应该如何实现这个？虽然 Clipper 库中已经有现成的实际解决方案，但我是否要重新发明轮子？

旁注：PolyTree仍然需要测试每条 路径来确定PolyNode点在哪一条。没有Clipper.PointInPolyTree()方法，因此，据我所知PolyTree没有帮助。

分隔外多边形和内多边形的结构：

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

有过 Clipper 实践经验的人（@angus-johnson？）可以澄清这个困惑吗？

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

编辑（2019 年 9 月 13 日）：

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

函数 CrossProduct(const pt1, pt2, pt3: TPointD): double;
变量
  x1,x2,y1,y2：双精度；
开始
  x1 := pt2.X - pt1.X;
  y1 := pt2.Y - pt1.Y;
  x2 := pt3.X - pt2.X;
  y2 := pt3.Y - pt2.Y;
  结果 := (x1 * y2 - y1 * x2);
结尾;


函数 PointInPathsWindingCount(const pt: TPointD;
  const 路径：TArrayOfArrayOfPointD): 整数；
变量
  i，j，len：整数；
  p：TArrayOfPointD；
  上一个点：TPointD；
  上面是：布尔值；
  crossProd：双；
开始
  //nb: 当 pt 位于一行时返回 MaxInt ((2^32)-1)
  结果：= 0；
  for i := 0 到 High(路径) 执行
  开始
    j := 0;
    p := 路径[i];
    len := 长度(p);
    如果 len < 3 则继续；
    prevPt := p[len-1];
    while (j < len) and (p[j].Y = prevPt.Y) do inc(j);
    如果 j = len 则继续；
    isAbove := (prevPt.Y < pt.Y);
    while (j < len) 做
    开始
      如果是上面那么
      开始
        while (j < len) 和 (p[j].Y < pt.Y) 执行 inc(j)；
        如果 j = len 则中断
        否则如果 j > 0 则 prevPt := p[j -1];
        crossProd := CrossProduct(prevPt, p[j], pt);
        如果 crossProd = 0 那么
        开始
          结果：= MaxInt；
          出口;
        结尾
        否则如果 crossProd < 0 则 dec(Result);
      结束其他
      开始
        while (j < len) 和 (p[j].Y > pt.Y) 执行 inc(j)；
        如果 j = len 则中断
        否则如果 j > 0 则 prevPt := p[j -1];
        crossProd := CrossProduct(prevPt, p[j], pt);
        如果 crossProd = 0 那么
        开始
          结果：= MaxInt；
          出口;
        结尾
        否则如果 crossProd > 0 则 inc(结果);
      结尾;
      公司（j）；
      isAbove := 不是 isAbove;
    结尾;
  结尾;
结尾;

函数 PointInPaths(const pt: TPointD;
  常量路径：TArrayOfArrayOfPointD；fillRule: TFillRule): 布尔值；
变量
  wc：整数；
开始
  wc := PointInPathsWindingCount(pt, 路径);
  案例填写规则
    frEvenOdd: 结果 := Odd(wc);
    frNonZero: 结果 := (wc <> 0);
  结尾;
结尾;

关于利用 PolyTree 结构：

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