如下所示,我有一个包含整数点的多边形:
type
TPoint = array [1 .. 2] of Integer;
TPointArray = array of TPoint;
边缘上的点按顺时针顺序给出,我想删除中间点(标记为红色)。
例如,给定任意连续的3个点A、B、C,如果B恰好在A和C之间的直线上,则可以安全地移除B。
我怎样才能快速有效地做到这一点?
我的 Psedu 代码是:
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;
最佳答案
浏览列表并考虑相邻点 p、q 和 r 的三元组。确定前向向量pq和qr并检查它们是否共线。如果是这样并且它们面向同一方向,则标记要删除的点。
在第二遍中,过滤掉标记点。
如果两个向量的叉积是零向量,则它们是共线的。平面内向量的叉积只有一个垂直于该平面的分量。所以检查一下:
pq.x * qr.y - pq.y * qr.x == 0
如果您想确保不会删除狭长区域的尖点,请检查向量的点积是否为正:
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;
关于algorithm - 删除多边形边缘上的重复点的最快方法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32720024/