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

Question

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.

Answer 1

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.

• Formula for area: Shoelace formula by 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

You can take the cross product between two consecutive edges incident on the vertex: the sign will tell if the point is convex or concave.

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

a problem is that the sign depends also on if the loop is clockwise or counter-clockwise. What you can do is checking the sign of the top-left vertex (that vertex is for sure strictly convex), if the sign of a vertex multiplied by the sign of top-left vertex is negative then it's concave.

With top-left vertex I mean the vertex with minimum x among the ones with minimum y. You should remove duplicate vertices before doing this kind of computation.