Try this test case to see most of the edge-cases of a convex hull:
<brush points="200,200 200,200 150,100 100,200 110,110 200,100 210,190 100,100"/>
For brushes in CSG, you want to work with convex solids. You don't have to, but you really want to when you can. A nice authoring approach here is just let someoneone give you an un-ordered set of points and compute a convex hull. The algorithm I reinvented here is the "Jarvis March", I learned the name from this nice YouTube video, which also helped me find one bug in my implementation, and remove some of the redundant safety checks I was doing. To compute a convex hull with the Jarvis March:
- Pick a starting point on the convex hull. Try picking the minimum (x, y) point for this.
- Iterate, updating the current point as you go.
- Pick the point furthest to the right:
- Start with an arbitrary candidate point
- Iterate over all points, ignoring bad points (see the note on instabilities below).
- Check the point has a better angle from the current point than the candidate point does. You can do this nicely with a cross product.
- If it's better, update the candidate point.
- Record the candidate point in your hull, and move on to the next point.
- Stop when you eventually return to the starting point.
Some notes on instabilities:
- Make sure to handle zero-length edges (you just ignore an arbitrary one of the relevant points)
- Make sure to handle colinear edges (in the Jarvis March, you can prioritize farther-away verticies if the angle change is 0)
- Make sure your input data is sensible. I ran into multiple infinite loops caused by NaN sneaking into my data.