主页 / 问题 / 1289540
Accepted
Anton Shchyrov
Asked:2022-06-04 01:04:54 +0000 UTC2022-06-04 01:04:54 +0000 UTC

属于多边形的点

  • 772

有一个代码可以检查一个点是否属于一个多边形

function IsInPoly(const ARegion: array of TPoint; const ASearchPoint: TPoint): Boolean;
var
  LPrevPoint, LCurPoint: TPoint;
  Li: Integer;
  DX, DY, StepX, StepY: Integer;
  Step: Double;
  Rotation: Double;
begin
  LPrevPoint := ARegion[0];
  Rotation := 0;
  for Li := 1 to Length(ARegion) - 1 do begin
    LCurPoint := ARegion[Li];
    DX := LCurPoint.X - LPrevPoint.X;
    DY := LCurPoint.Y - LPrevPoint.Y;
    StepX := LPrevPoint.X - ASearchPoint.X;
    StepY := LPrevPoint.Y - ASearchPoint.Y;
    if (StepX <> 0) or (StepY <> 0) then begin
      Step := (DX * StepY - DY * StepX) / (StepX * StepX + StepY * StepY);
      Rotation := Rotation + Step;
    end;
    LPrevPoint := LCurPoint;
  end;
  Result := (Abs(Rotation) > 5);
end;

帮助识别此算法。我在谷歌的文章中没有看到类似的描述。结果，我不明白代码在原理上是否有效？

在这里，据我了解(DX, DY)，这是一个从上一个点到下一个点，以及(StepX, StepY)从所需点到上一个点的向量。什么是Step和Rotation？

алгоритм

1 个回答

  1. Best Answer

    不，算法是错误的。

    一个反例是一个有角的正方形 (1, 0), (0, -1), (-1, 0), (0, 1)，测试点是 (0, 0)。

    在这种情况下，(StepX * StepX + StepY * StepY)它始终为 1，我们将三角形的面积相加OAᵢAᵢ₊₁，加起来为 4，小于 5。

    （该算法似乎需要在末尾复制起点。）

    据我了解，该算法的作者想AᵢXAᵢ₊₁为 all加上定向角度i，这个总和理论上应该给外部点 0 和内部点 2π。正确的实现应该是这样的：

    DX1 := LCurPoint.X - ASearchPoint.X;
DY1 := LCurPoint.Y - ASearchPoint.Y;
DX2 := LPrevPoint.X - ASearchPoint.X;
DY2 := LPrevPoint.Y - ASearchPoint.Y;
S := DX1 * DY2 - DX2 * DY1; // ориентированная площадь, произведение сторон на синус
P := DX1 * DX2 + DY1 * DY2; // скалярное произведение, произведение сторон на косинус
if (S <> 0) or (P <> 0) then begin
  Angle := ArcTan2(S, P);
  Rotation := Rotation + Angle;
end;

    最后将角度与 进行比较2 * PI。另外，最好在算法本身中复制起点。不要忘记补偿计算误差：角度加起来可能不会正好为2π。

    更流行的算法：

    1. 依次计算多边形各边的向量，乘以(为测试点)AᵢAᵢ₊₁的叉积。如果所有这些叉积都具有相同的符号（在几何上：沿每一边的路径上的一个点始终在左侧（或右侧），那么该点在内部。该算法仅适用于凸多边形。（也许它可以通过计算符号变化的奇偶性来推广到任意多边形，我无法从夏天证明。）AᵢAᵢ₊₁XAᵢXX
    2. 通过该点画一条任意直线（例如水平线），并计算与构成边的每个线段X的交点。如果在点的左侧（或右侧）有偶数个交点（例如，零），那么我们在外面，或者奇数，然后在里面。为了不处理线穿过顶点的情况，可以选择不一定是水平线，任何不与任何线重合的线（它们的数量是有限的）。此解决方案本着 Jordan 曲线定理的精神，适用于任何非自相交多边形。XXAᵢ
    • 2

相关问题