Search code examples
javascriptpolygonconcave

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

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

I know [7,8],[9,8] there it is pit, I want to write a function to get the concave point in this array how can I write.

I've used graphics algorithms, but not for complex concave edges. Then I thought about whether I could handle the data that the server gave me, which is a polygon.

Solution

  • In theory, you could get the area of the polygon. Then get the area of the polygon again by skipping a point. If the polygon is greater than the original area, you got a concave point.

    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; }