algorithm - 删除多边形边缘重复点的最快方法？

Question

如下所示，我有一个包含整数点的多边形:

type
  TPoint = array [1 .. 2] of Integer;
  TPointArray = array of TPoint;

边缘上的点按顺时针顺序给出，我想删除中间点(标记为红色)。

例如，给定任意连续的 3 个点 A、B、C，如果 B 恰好在 A 和 C 之间的线上，则可以安全地移除 B。

我怎样才能快速有效地做到这一点？

我的伪代码是:

procedure RemovePoints(var pt: TPointArray);
var
  i, j, sz, k, u: integer;
  xoffset, yoffset: integer;
begin
  sz := High(pt);
  i := 0;
  while (True) do
  begin
    Inc(i);
    // points represent array index, so can't be negative,
    // we use -1 to mark deletion
    if (pt[i][1] = -1) then continue;
    if (i = 0) then
    begin
      break; // finish a loop
    end;
    j := i + 1;
    if (j > sz) then
    begin
      j := 0;
    end;
    k := j + 1;
    if (k > sz) then
    begin
      k := 0;
    end;
    if ((pt[i][1] - pt[j][1] = pt[j][1] - pt[k][1]) and ((pt[i][2] - pt[j][2] = pt[j][2] - pt[k][2]))) then
    begin
      // remove pt[j];
      pt[j][1] := -1;
    end;
  end;
  // TODO: shrink the array to remove deleted points
end;

Answer 1

遍历列表并考虑相邻点 p、q 和 r 的三元组。确定前向向量 pq 和 qr 并检查它们是否共线。如果是这样并且他们面向同一方向，请标记要删除的点。

在第二遍中，过滤掉标记的点。

如果两个向量的叉积是零向量，则它们共线。平面中向量的叉积只有一个垂直于该平面的分量。所以检查:

pq.x * qr.y - pq.y * qr.x == 0

如果你想确保你没有删除 panhandle 的尖点，检查向量的点积是否为正:

pq.x * qr.x + pq.y * qr.y > 0

因为您有整数坐标，所以这些检查应该很简单。

这是一个使用您的命名法和类型的解决方案。它在单独的数组中跟踪要删除的节点。 (不能用虚拟值标记坐标，因为在确定是否删除下一个节点时，仍然需要完整的坐标。)

procedure RemovePoints(var pt: TPointArray);
Var i, j: Integer;
    p, q, r: TPoint;
    ax, ay: Integer;
    bx, by: Integer;
    del: Array of Boolean;

begin
  if Length(pt) > 2 then begin
    SetLength(del, Length(pt));
    for i := 0 to Length(pt) - 1 do del[i] := False;

    j := Length(pt) - 1;
    p := pt[j - 1];
    q := pt[j];

    for i := 0 to Length(pt) - 1 do begin
      r := pt[i];

      ax := q[1] - p[1];
      ay := q[2] - p[2];
      bx := r[1] - q[1];
      by := r[2] - q[2];

      if (ax*by - ay*bx = 0) and (ax*bx + ay*by > 0) then del[j] := True;

      p := q;
      q := r;
      j := i;
    end;

    j := 0;
    for i := 0 to Length(pt) - 1 do begin
      if not del[i] then begin
        pt[j] := pt[i];
        inc(j);
      end;
    end;

    SetLength(pt, j);
  end;
end;