While working on the AI player for a real-time strategy game, I came upon a rather specific problem and discovered a nifty solution. I had been considering using the data in Unity’s pathfinding NavMesh with the aim of extracting the edges from the sets of vertices that composed it. However, when looking in Scene View, I found that the NavMesh appeared to be made up of not only triangles but also other polygons with more sides. This posed a potential problem as well as an interesting geometric question: Given only the vertices of a convex quadrilateral, how do you determine which pairs of vertices form the edges? While I ultimately did not need it for my AI implementation, I thought I’d share the solution in the article below.
How to Find the Edges of a Convex Quadrilateral Given the Vertices?
Let’s say you’re given four points as coordinates which define the corners of a quadrilateral. You also happen to know that this quadrilateral is convex (in the context of the NavMesh display, all polygons are convex). So how can you determine which pairs of points form the outer edges of this polygon? After all, some pairs could turn out to be the interior diagonals, so we need some method to choose the correct pairs.
If you were to choose four edges at random, you could get lucky and happen to choose all the outer edges of the quadrilateral. But with six edges to choose from and four chosen, there are 15 possible combinations of which only one is correct.
However, we can significantly reduce the problem space if we imagine that we choose four vertices in order. Furthermore, we’ll consider only the three consecutive edges between them, since the fourth can be easily inferred by connecting the last vertex to the first. When we do this, we find there are essentially three resulting scenarios: one interior diagonal occurs in the sequence, two diagonals occur, or none i.e. an ordering of vertices that correctly outlines the quadrilateral. These scenarios are illustrated here:
We’re now one significant step closer to our solution having better defined the problem space. But how can we distinguish between these using only math? It’s easy enough to figure out using only our eyes, but we need a way to distinguish between these scenarios in code.
Consider the fact that we know the quadrilateral is convex. Consequently, we can deduce that following the outline of the quadrilateral will always result in the same turn direction from one edge to the next (i.e. clockwise or counter-clockwise). It turns out the cross product is perfect for calculating the turn direction between three points. Putting this calculation to use, we see that our target scenario of zero diagonals passes this turn direction test whereas the scenario with one diagonal does not — the angles change direction from the first half of the Z- or N-shape to the second half. Great! We’re nearly there.
But wait, using this turn direction test, our scenario with two diagonals would still pass: the angles ABC and BCD take the same turn direction (counter-clockwise in the illustration above). However, there is another feature of this case that is unlike the others: the two diagonals wind up intersecting each other. Coincidentally, we can again use the cross product to detect this intersection.
So we now have the two tests needed to determine which of the three scenarios an order of vertices results in, both of which happen to use the cross product. Depending on the scenario, we can then flip the order of the appropriate pair of vertices to get the correct sequence that outlines the quadrilateral. Our final algorithm thus looks like this:
Check the turn direction of ABC versus BCD If unequal flip C & D Else, check whether AB intersects CD If intersects, flip B & C Else, order is correct After any flips, our edges are now AB, BC, CD, and DA
And that’s it! While perhaps a niche problem, the solution winds up being quite efficient and elegant if I do say so myself. I hope you find this helpful, either directly or indirectly, in your own geometric adventures!
In future posts, I’ll elaborate on other handy uses of the cross product, as well as describe in much detail how I wound up using the NavMesh data in my AI solution.