我怎么能在凹多边形中得到坑，我有一个多边形arr

Question

let arr=[[4,3],[4,9],[7,8],[9,8],[10,10],[10,4]]

我知道了[7,8],[9,8]这里有坑，我想写一个函数获取这个数组中的凹点怎么写

我使用过图形算法，但不适用于复杂的凹边。然后我就想能不能处理服务器给我的数据，是一个多边形

Answer 1

理论上，你可以得到多边形的面积。然后通过跳过一个点再次获得多边形的面积。如果多边形大于原来的面积，就得到一个凹点。

面积公式：Shoelace formula 作者 Gauß

const getArea = points => Math.abs(points.reduce((a, p, i, pp) => a + (p[1] + pp[(i + 1) % pp.length][1]) * (p[0] - pp[(i + 1) % pp.length][0]), 0)) / 2;

let points = [[4, 3], [4, 9], [7, 8], [9, 8], [10, 10], [10, 4]],
    area = getArea(points),
    concave = points.filter((_, i, pp) => getArea(pp.filter((_, j) => i !== j)) > area);

console.log(area);
console.log(concave);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

您可以取入射到顶点的两条连续边的叉积：符号会告诉您该点是凸点还是凹点。

function sign(arr, i) {
    let n = arr.length;
    let i0 = i == 0 ? n-1 : i-1;  // Previous vertex
    let i1 = i == n-1 ? 0 : i+1;  // Next vertex
    let ax = arr[i][0] - arr[i0][0], bx = arr[i1][0] - arr[i][0];
    let ay = arr[i][1] - arr[i0][1], by = arr[i1][1] - arr[i][1];
    return Math.sign(ax*by - ay*bx);
}

一个问题是符号还取决于循环是顺时针还是逆时针。你可以做的是检查左上顶点的符号（该顶点肯定是严格凸的），如果顶点的符号乘以左上顶点的符号为负则它是凹的。

对于左上顶点，我指的是在具有最小 y 的顶点中具有最小 x 的顶点。在进行这种计算之前，您应该删除重复的顶点。

我怎么能在凹多边形中得到坑，我有一个多边形arr

How can I get pit in concave polygon, I have a polygon arr

javascript

polygon

concave