Background and problem analysis

Before using drones to map an area, we will first select an area on the map, and then plan the flight route, and the area to map is often a polygon. In MeshKit iOS, we added the ability to edit polygon regions, which involves determining whether or not the polygon edited by the user is valid.

First we need to determine a standard:What is an illegal polygon? We can explain it simply by looking at the following picture:

We can see that the first two are concave polygons and convex polygons respectively, and the last one is what we call an illegal polygon. We can see that the characteristic of this illegal polygon is that one side intersects another side.

So to judge whether a polygon is legal, we just need to judge whether all the line segments that make up the polygon have intersection. Of course, the intersection we say here is normal intersection, that is, the intersection point is not on the end point of the line segment.

Ok, so now the problem can be reduced to: how to determine whether two line segments meet properly.

Algorithm analysis

So we’re going to have to use the cross product of the vectors.

A cross product, also known as a cross product, is a binary operation of two vectors in three dimensions.

I recommend the 3Blue1Brown video for a quick review of cross product concepts (the two screenshots below are from this video). 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, the vector w⃗\vec{w}w is in the clockwise direction of v⃗\vec{v}v, V ⃗×w⃗<0\vec{v} \times \vec{w} < 0v ×w <0:

If the vector w⃗\vec{w}w is in the counterclockwise direction of v⃗\vec{v}v, then v⃗×w⃗>0\vec{v} \times \vec{w} > 0v ×w >0:

So how do we use the properties of the cross product to determine whether line segments intersect?

Let’s start with the most direct line segment intersection:

There is an obvious intersection between line segment P1P2P_1P_2P1P2 and line segment Q1Q2Q_1Q_2Q1Q2. A simple conclusion can be drawn from the above figure: If one line segment has two ends on either side of another line segment, then these two line segments might intersect, and notice that they might intersect, but we’ll talk about the other case later.

We can convert the above graph into a vector:

Does this sound familiar, does this look very similar to the cross product?

Vector P1Q2⃗\vec{P_1Q_2}P1Q2 in the clockwise direction of P1P2⃗\vec{P_1P_2}P1P2 then: 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

We mentioned earlier that if one line segment has two ends on either side of another line segment, then these two line segments might intersect. Why might they intersect? If we move segment Q1Q2Q_1Q_2Q1Q2 to the right, we have the following situation:

As can be seen from the figure above, the two ends of segment Q1Q2Q_1Q_2Q1Q2 are on either side of segment P1P2P_1P_2P1P2, but they do not intersect.

So how do you rule that out? It’s actually quite simple. We’ve been using line segment P1P2P_1P_2P1P2 as the main point of view, and if we change the main point of view to line segment Q1Q2Q_1Q_2Q1Q2, So it’s easy to see that the end points of segment P1P2P_1P_2P1P2 are not on either side of segment Q1Q2Q_1Q_2Q1Q2. So let’s go back to the intersecting picture above. In order to fully judge the intersection of two line segments, this time we take Q1Q2Q_1Q_2Q1Q2 as the main perspective to look at the problem and find the cross product:

Vector Q1P2⃗\vec{Q_1P_2}Q1P2 is counterclockwise in Q1Q2⃗\vec{Q_1Q_2}Q1Q2, then: Q1Q2⃗×Q1P2⃗>0\vec{Q_1Q_2} \times \vec{Q_1P_2} > 0Q1Q2 ×Q1P2 >0 vector Q1P1⃗\vec{Q_1P_1}Q1P1 clockwise in Q1Q2⃗\vec{Q_1Q_2}Q1Q2, Q1Q2⃗×Q1P1⃗<0\vec{Q_1Q_2} \times \vec{Q_1P_1} < 0Q1Q2 ×Q1P1 <0

To sum up, we can conclude that:


A = P 1 P 2 ⃗ x P 1 Q 1 ⃗ B = P 1 P 2 ⃗ x P 1 Q 2 ⃗ C = Q 1 Q 2 ⃗ x Q 1 P 1 ⃗ D = Q 1 Q 2 ⃗ x Q 1 P 2 ⃗ A = \vec{P_1P_2} \times \vec{P_1Q_1} \\ B = \vec{P_1P_2} \times \vec{P_1Q_2} \\ C = \vec{Q_1Q_2} \times \vec{Q_1P_1} \\ D = \vec{Q_1Q_2} \times \vec{Q_1P_2}

when
A x B < 0 A{\times} B < 0 &&
C x D < 0 C \times D < 0 When, the two line segments normatively intersect. As for how to calculate the cross product of vectors, I will not write in detail here, but give you a draft of the calculation for a look:

The sample code

Based on the contents of the calculation draft, we can easily implement this in code:

private func isIntersect(line1: (CGPoint.CGPoint), line2: (CGPoint.CGPoint)) -> Bool {
    let p1 = line1.0
    let p2 = line1.1
    let q1 = line2.0
    let q2 = line2.1

    let a1 = (p2.x - p1.x) * (q1.y - p1.y) - (q1.x - p1.x) * (p2.y - p1.y)
    let a2 = (p2.x - p1.x) * (q2.y - p1.y) - (q2.x - p1.x) * (p2.y - p1.y)
    
    let b1 = (q2.x - q1.x) * (p1.y - q1.y) - (p1.x - q1.x) * (q2.y - q1.y)
    let b2 = (q2.x - q1.x) * (p2.y - q1.y) - (p2.x - q1.x) * (q2.y - q1.y)
    
    if a1 * a2 < 0 && b1 * b2 < 0 {
        return true
    }
    return false
}
Copy the code

Due to the author’s limited ability, if there are mistakes in the article, please readers do not hesitate to comment.