Problem description

How to cut a concave polygon into multiple convex polygons?

The commonly used methods of cutting concave polygons are Vector Method and rotation Method.

The basic idea is to use the cutting method to cut a concave polygon, and then judge whether the cut graph is concave polygon, if there is still concave polygon, then continue to cut.

So here is a pre-requisite: how to determine whether any polygon is a concave polygon, see my previous article “How to Identify concave polygons”.

This paper mainly introduces the use of vector method to cut concave polygons.

Vector method

1. Find the cross product of the different-sign side vectors

Reviewing the article “How to Distinguish Concave Polygons”, we know that the cross of the edge vector of concave polygons is stored in the different sign, as shown in the following figure:

The cross product of the side vectors of polygons [P0, P1, P2, P3, P4] is as follows:


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 can be seen that u⃗×v⃗\vec{u} \times \vec{v}u ×v is greater than 0, and the rest are less than zero. The cross product of the side vectors p0p1 and p1p2 turns out to be the only different sign here.

Here we agree that the points that make up the concave polygon are arranged clockwise, so if ** is greater than 0 ** in the cross product of the edge vectors, we can judge that the two edges are concave positions. That is, edge P0P1 is the position where the edge begins to recede. Record the position of this edge and then proceed with the next step of processing this edge.

Note: If the points that make up a concave polygon are arranged counterclockwise, the result of the side vectors computed in order should be judged as the cross product less than 0.

2. Extend the different sign edge for cutting

In the previous step, we found p0p1, the “different sign edge”. We extend it until it intersects one edge of the polygon, as shown below:

As can be seen from the figure, the extension line P0P1 intersects at point A on P2P3.

This extension line is the cut line of A concave polygon, which is cut into two polygons: [P1, P2, A] and [P0, A, P3, p4].

Then we judge whether the two polygons after cutting still have concave polygons, and find that there is no concave polygon, then the concave polygon is cut.

The description here seems simple, but if you want to abstract this problem into code, you need to address two issues explicitly:

  1. How to find the position of the intersection, namely the edge of the intersection and the coordinates of the intersection.
  2. How to split the original array after obtaining the coordinates of intersections and get two polygon arrays with the correct order of points.

3. Find the intersection

To find out which side of a polygon the extension line of P0P1 intersects, let’s review the method of how to determine whether a polygon is legitimate:

If you want to determine whether the two line segments P1P2 and Q1Q2 intersect, one of the steps looks like this:

Because P1Q1⃗\vec{P_1Q_1}P1Q1 is counterclockwise in P1P2⃗\vec{P_1P_2}P1P2, then: P1P2⃗×P1Q1⃗>0\vec{P_1P_2} \times \vec{P_1Q_1} > 0P1P2 ×P1Q1 >0

Because P1Q2⃗\vec{P_1Q_2}P1Q2 is in the clockwise direction of P1P2⃗\vec{P_1P_2}P1P2: P1P2⃗×P1Q2⃗<0\vec{P_1P_2} \times \vec{P_1Q_2} < 0P1P2 ×P1Q2 <0

Use A to denote the cross product of P1P2⃗×P1Q1⃗\vec{P_1P_2} \times \vec{P_1Q_1} P1P2 ×P1Q1, Using B to represent the cross product of P1P2⃗×P1Q2⃗\vec{P_1P_2} \times \vec{P_1Q_2}P1P2 ×P1Q2, then the geometric phenomenon that the ends of one segment are on either side of another segment can be expressed by the formula: A (B < 0 {\ times} B < 0 (B < 0

Suffice it to recall that P1P2 is the extension line we used to cut the polygon, and Q1Q2 is any side of the polygon.

In order to find the intersection of the extension line and one of the sides of the polygon, we can use this method to calculate the extension line and the sides of the polygon one by one in order, find the first result A×B<0A{\times}B<0A×B<0, and then know where the intersection is.

According to the method here, let’s go back to the concave polygon:

As shown above, cp1=P0P1⃗×P0P2⃗>0cp1 = \vec{P_0P_1} \times \vec{P_0P_2} >0cp1 =P0P1 ×P0P2 >0, Cp2 =P0P1⃗×P0P3⃗<0cp2 = \vec{P_0P_1} \times \vec{P_0P_3} <0cp2 =P0P1 ×P0P3 <0,

So cp1 times cp2 is going to be less than 0, so the intersection is going to be on p2p3.

And then we can use these four points, P0, P1, P2, p3, to figure out the line function, to figure out the coordinate A, and we won’t go into the details of how to figure out the coordinate A by using these two line functions.

Here’s a bit of code to follow the steps:

/// Cut concave polygons for multiple convex polygons, vector cutting method
func divideConcavePolygon(vertexs: [CGPoint])- > [[CGPoint]] {
    guard vertexs.count > 3 else { return[]}// Out of the outer loop flag
    var breakFlag = false
    // Note that vertexs points are arranged clockwise
    for index in 0..<vertexs.count {
        let index1 = (index + 1) % vertexs.count
        let index2 = (index + 2) % vertexs.count
        let p0 = vertexs[index]
        let p1 = vertexs[index1]
        let p2 = vertexs[index2]
        let crossProduct = crossproduct(vector1: (p0, p1), vector2: (p1, p2))
        
        // If the cross product is greater than 0, the vector p1p2 is counterclockwise from the vector p0p1
        // p0p1 is an odd edge
        if crossProduct > 0 {
            
            // Compute with the rest of the polygon to find the intersection
            for i in 0..<vertexs.count {
                let current = vertexs[i]
                let next = vertexs[(i + 1) % vertexs.count]
                
                // Skip the current edge (extension edge)
                if index = = i || index = = (i + 1) % vertexs.count {
                    continue
                }
                
                let cp1 = crossproduct(vector1: (p0, p1), vector2: (p0, current))
                let cp2 = crossproduct(vector1: (p0, p1), vector2: (p0, next))

                // Find the edge where current and next intersect
                if cp1 * cp2 < 0 {
                    // TODO:- According to the extension line and the edge of the intersection point, calculate the intersection point coordinate newPoint
                    // TODO:- Cut the polygon array and add newPoint to the array
                    // Jump out of the nested loop and mark the need to jump out of the outer loop
                    breakFlag = true
                    break}}}if breakFlag { break}}// TODO:- Returns the cut convex polygon array
    return polygons
}
Copy the code

4. Split the original array

After cutting through the extension line of the opposite sign to get the coordinate A of the intersection point, we also need to split the original array to get an array of two polygons.

Let’s go back to the concave polygon above:

We want to split the original coordinate array into [P1, P2, A] and [P0, A, P3, p4]. Observe that the points in the array are arranged clockwise. This order is important both to ensure the shape of the polygon and to continue cutting the remaining polygons using the cutting method above.

The original polygon array is [P0, P1, P2, P3, P4], convert it to the array index as [0, 1, 2, 3, 4], observe that we need to intercept [1, 2], and then leave [0, 3, 4], and insert the coordinates of A in the appropriate position.

Let’s add a splice extension that takes an interval from an array and mutates it as well:

extension RangeReplaceableCollection {
    mutating func splice<R: RangeExpression> (range: R) -> SubSequence where R.Bound = = Index {
        let result = self[range]
        self.removeSubrange(range)
        return result
    }
}
Copy the code

As shown in the concave polygon image above, the intersection point A is on p2p3, i.e. between the array indexes current = 2 and next = 3. The index of the hetero edge is index0 = 0 and index1 = 1

var polygon2 = vertexs
var polygon1 = Array(polygon2.splice(range: index1.current))
// Insert the intersection A coordinates
polygon1.append(A)
polygon2.insert(A, at: index0 + 1)
Copy the code

Here, we should also pay attention to the case that the index of the edge where the coordinate of the intersection point is located is less than the index of the other side, which can be illustrated by the following figure:

In the concave polygon shown in the figure, the intersection point A is on p0P1, that is, between the array indexes current = 0 and next = 1, and the indexes for the hetero edges are index0 = 2 and index1 = 3

Here is a piece of code posted to understand the interception of this interval:

if current > index0 {
    var polygon2 = vertexs
    // if current is greater than index0, split interval is [index1, current]
    var polygon1 = Array(polygon2.splice(range: index1.current))
    // Insert the intersection A coordinates
    polygon1.append(A)
    polygon2.insert(A, at: index0 + 1)}else {
    var polygon2 = vertexs
    // if current is less than index0, then split interval is [current+1, index0]
    var polygon1 = Array(polygon2.splice(range: current + 1.index0))
    // Insert the intersection A coordinates
    polygon1.append(A)
    polygon2.insert(A, at: index0 + 1)}Copy the code

5. Pay attention to the coordinate system

So far, the vector method for dividing concave polygons has been explained. When I did a Demo on iOS to verify this algorithm, I found that the cutting position was not correct at the beginning, as shown below:

As can be seen from the figure, the actual cutting position is opposite to the position I imagined when deducing the algorithm. I am puzzled.

And then I remembered that the x and y coordinate system on iOS is not the same as the geometric coordinate system, the y axis is pointing down. So in the eyes of the algorithm, this graph is actually upside down, so there is no problem with the algorithm. Here is a special note of caution.