Problem description

How to determine if a polygon is concave? First we need to clarify how concave polygons are defined and what their characteristics are.

It is described in the section 3.15.1 polygon Classification of Computer Graphics:

An interior Angle of a polygon is an Angle within the boundary of the polygon formed by two adjacent edges. If all the inner angles of a polygon are less than 180°, it is a convex polygon. . Polygons that are not convex are called concave polygons. The diagram below:

Then in the section 3.15.2 identifying concave polygons, it simply describes whether a polygon is concave by using the cross product of polygon edge vectors:

If you build a vector for each side of a polygon, the convexity and concavity can be tested using the cross product of adjacent edges. All vector cross products of convex polygons have the same sign. Therefore, if some cross products are positive and others are negative, they can be identified as concave polygons.

Then the section also gives a way to explain the cross product of edge vectors with a graph that is widely circulated on the Internet but whose origin is rarely explained:

If you don’t have a background, this might be a little confusing. Why can we judge concave polygons by deriving the homotropy of side vectors from the feature that the inner Angle of concave polygons is greater than 180 degrees? What is the shift in thinking here? The following to my shallow understanding to give you about.

Understand the edge vector cross product method

1. Move the edge vector

First, we draw a simple convex polygon: [P0, P1, P2, P3, P4]. Then, starting from the first point P0, we use every two points of the line segment as a vector in the direction of the points that make up the polygon, as shown in the following figure:

Then, keeping the size and direction of the vectors constant, move the starting points of all the side vectors to the origin of the coordinate system:

We can observe that the vectors u, V, W, a, and b appear in clockwise order. This is an important phenomenon, but before we go on let’s review what we know about cross products.

2. Review cross products

We only need to know that the result of the cross product is positive or negative. For example, if we take the vector v⃗\vec{v}v as the standard, it has the following characteristics:
vector
w ⃗ \vec{w} 在
v ⃗ \vec{v} 的 Clockwise direction, then
v ⃗ x w ⃗ < 0 \vec{v} \times \vec{w} < 0
If the vector
w ⃗ \vec{w} 在
v ⃗ \vec{v} 的 Counterclockwise direction, then
v ⃗ x w ⃗ > 0 \vec{v} \times \vec{w} > 0

3. The cross products of convex polygon edge vectors are all the same

Above we moved the starting points of the side vectors of a convex polygon to the origin of coordinates and found that all vectors are rendered in clockwise order.

In combination with the knowledge of the vector cross product, we can conclude that: when all the side vectors are cross-product in pairs in order, the results are all less than 0, that is, all the side vector cross products of the convex polygon have the same sign:


u ⃗ x v ⃗ < 0 v ⃗ x w ⃗ < 0 w ⃗ x a ⃗ < 0 a ⃗ x b ⃗ < 0 \vec{u} \times \vec{v} < 0 \\ \vec{v} \times \vec{w} < 0 \\ \vec{w} \times \vec{a} < 0 \\ \vec{a} \times \vec{b} < 0 \\

So what happens if it’s a concave polygon?

4. Different signs of the cross product of concave polygon edge vectors

Similarly, we move the edge vectors of a concave polygon to the origin of coordinates to observe:

As shown in the figure above, the concave polygon [P0, P1, P2, P3, P4] is observed to move the vectors behind it. The vectors U, V, W, A, and B are not in strict clockwise order. W ⃗\vec{w}w appears between u⃗\vec{u}u and v⃗\vec{v}v.

So if all the side vectors take the cross product in pairs, the result will have different signs:


u ⃗ x v ⃗ < 0 v ⃗ x w ⃗ > 0 w ⃗ x a ⃗ < 0 a ⃗ x b ⃗ < 0 \vec{u} \times \vec{v} < 0 \\ \vec{v} \times \vec{w} > 0 \\ \vec{w} \times \vec{a} < 0 \\ \vec{a} \times \vec{b} < 0 \\

It is because the interior Angle of concave polygon is greater than 180 degrees that concave polygon loses the side vector identity characteristic of convex polygon, so we can use this characteristic to distinguish whether polygon is concave or convex.

5 code recognition of concave polygons

// check whether the polygon is concave
// the cross product of all sides of a convex polygon has the same sign. If the cross product of all side vectors of a polygon has different signs, it can be considered as a concave polygon
func isConcavePolygon(vertexs: [CGPoint]) -> Bool {
    var allLines = [(CGPoint.CGPoint)] ()// Define all line segments according to two points before and after
    for (pointIndex, point) in vertexs.enumerated() {
        let p1 = point
        let p2 = vertexs[(pointIndex + 1) % vertexs.count]
        allLines.append((p1, p2))
    }

    // Calculate the cross product of two adjacent sides to determine whether the polygon is concave
    var preValue = crossproduct(vector1: allLines[0], vector2: allLines[1])
    for lineIndex in 1..<allLines.count {
        let current = allLines[lineIndex]
        let next = allLines[(lineIndex + 1) % allLines.count]
        let currentValue = crossproduct(vector1: current, vector2: next)
        // If the current two adjacent side cross products are not equal to the upper two adjacent side cross products, i.e. different signs, then it is a concave polygon
        if preValue ! = currentValue {
            return true
        }
        preValue = currentValue
    }

    return false
}

func crossproduct(vector1: (CGPoint.CGPoint), vector2: (CGPoint.CGPoint)) -> CGFloat {
    let p1 = vector1.0
    let p2 = vector1.1
    let q1 = vector2.0
    let q2 = vector2.1

    let crossproduct = (p2.x - p1.x) * (q2.y - q1.y) - (q2.x - q1.x) * (p2.y - p1.y)

    return crossproduct > = 0 ? 1 : -1
}
Copy the code