简单多边形凸包的线性Graham扫描
据推测，Graham扫描算法应该在线性时间内找到简单多边形的凸包，而不需要nlogn排序步骤(因为简单多边形的顶点已经有效排序)。我有一个格雷厄姆扫描的实现，它似乎工作得很好：
function ccw(a: Vertex, b: Vertex, c: Vertex) {
return (b.y - a.y)*(c.x - a.x) - (b.x - a.x)*(c.y - a.y);
}
// Graham Scan Convex Hull Algorithm
// This is destructive
export function convexHull(points: Vertex[]) {
const n = points.length;
if (n <= 3) return points;
// Assume the first point is bottom-left-most
const p0 = points[0];
// Sort by angle
points.sort((a, b) => {
const c = ccw(p0, a, b);
return c === 0 ? a.x - b.x : c;
});
// Keep points in the result if they "turn left"
let len = 1;
for (let i = 1; i < n; i++) {
let b = points[len-1];
let c = points[i];
//if (b.x === c.x && b.y === c.y) { continue; } // identical points are already filtered out
if (len >= 2) {
let a = points[len-2];
while (ccw(a, b, c) >= 0) {
len--;
if (len < 2) { break; }
b = a;
a = points[len-2];
}
}
points[len++] = c;
}
points.length = len;
return points;
}(请注意，多边形表示已经被旋转，因此在调用该函数之前，该点肯定是最左下角的点。)
给定测试数据
[
{ x: 0, y: -1 },
{ x: 0.2886751345948129, y: -0.5 },
{ x: 0.8660254037844387, y: -0.5 },
{ x: 0.5773502691896257, y: 0 },
{ x: 0.8660254037844387, y: 0.5 },
{ x: 0.28867513459481287, y: 0.5 },
{ x: 0, y: 1 },
{ x: -0.28867513459481287, y: 0.5 },
{ x: -0.8660254037844387, y: 0.5 },
{ x: -0.5773502691896257, y: 0 },
{ x: -0.8660254037844387, y: -0.5 },
{ x: -0.2886751345948129, y: -0.5 }
]对于一个简单的半径-1，六角星，这给出了正确的结果，一个六边形：
[
{ x: 0, y: -1 },
{ x: 0.8660254037844387, y: -0.5 },
{ x: 0.8660254037844387, y: 0.5 },
{ x: 0, y: 1 },
{ x: -0.8660254037844387, y: 0.5 },
{ x: -0.8660254037844387, y: -0.5 }
]但是，如果删除角排序，即使输入是一个简单的多边形，它最终会附加一个额外的内部顶点：
[
{ x: 0, y: -1 },
{ x: 0.8660254037844387, y: -0.5 },
{ x: 0.8660254037844387, y: 0.5 },
{ x: 0, y: 1 },
{ x: -0.8660254037844387, y: 0.5 },
{ x: -0.8660254037844387, y: -0.5 },
{ x: -0.2886751345948129, y: -0.5 }
]任何帮助调试此或建议使用的备用算法将不胜感激。我想使用Lee的算法，但我在任何地方都找不到一个很好的参考实现或完整的psuedocode，而且散文和图表的解释太难理解了。我可以使用Melkman的算法，但我实际上并不需要在线构建，我更愿意避免在可能的情况下使用deque而不是堆栈。
回答 2
Stack Overflow用户
发布于 2022-08-18 21:34:43
嗯，我不知道如何调试我所拥有的版本，但是我坐在一个空白的屏幕上，认真地思考如何从头开始重新实现格雷厄姆扫描，我想出了一些实际可行的方法：
// Graham scan. Assumes a simple polygon.
// This is destructive, collecting hull
// vertices in the prefix of the input array.
export function polygonHull(points: Vertex[]) {
const n = points.length;
// There can never be fewer than 4 vertices.
// Assume the first point is bottom-left-most
const p0 = points[0];
let top = 1;
for (let i = 2; i < n; i++) {
// Duplicate points are pre-filtered
// if (points[top].x === points[i].x && points[top].y === points[i].y) { continue; }
points[++top] = points[i];
while (top >= 2 && ccw(points[top-2], points[top-1], points[top]) >= 0) {
points[top - 1] = points[top]; // delete internal point
top--;
}
}
// Fix up the join between the tail and start
while (ccw(points[top-1], points[top], p0) >= 0) { top--; }
points.length = top + 1;
return points;
}其想法是尽可能使用循环双链接列表来坚持该算法的原始版本；然后只需对数组表示进行最小的修改，并对数组末端的不连续性进行特殊处理。
Stack Overflow用户
发布于 2022-09-01 08:58:15
你的信息是错误的，格雷厄姆扫描不一定“工作”在一个简单的多边形。事实是：
- 格雷厄姆扫描处理线性时间中的排序点(星状或单调多边形)，
。
- ，Melkman算法工作在线性时间的简单多边形上。
这就是说，对于小多边形来说，排序并不是什么大事。我最喜欢的版本是单调链版本，因为它避免了对极坐标的转换。
大多边形，除非它们是病态的，是由几个已经排序的序列组成的，所以使用k路合并排序是有利的。
如果你的点集有很大比例的内部点，初步的拒绝拉快艇可能会感兴趣-甚至导致线性预期的时间。不确定大型简单多边形是否享有此属性。
https://stackoverflow.com/questions/73406649
复制相似问题
腾讯云开发者
