Convex Hull

Topics: Developer Forum
Sep 15, 2009 at 1:39 AM

Hey, I was wondering if Farseer has a method for creating a convex hull around vertices. If not, do you think this would be something worth including in the Vertices class? I'm willing to code something up and submit it if anyone's interested.

Coordinator
Sep 15, 2009 at 11:18 PM

Well, both yes and no.

We don't have any specific convex hull tools, but we have tools that use convex hull algorithms inside of them (parts of the algorithms anyway). I'm not sure we have any clean implementation of a convex hull algorithm (most tools inside the Vertices class are user contributions).

If you get something working with a decent speed, I would be happy to take a look at it and possibly include it in the Vertices class.

Sep 18, 2009 at 7:05 PM

Ok, I'll do that, but I'd like to check with something that I'm not certain of. What is the standard polygon winding order that Farseer uses? Is it CCW? If so, is it CCW on a math-style cartesian coordinate system (Y increases upward) or on a computer graphics-style (Y increases downward)? It's just been confusing me quite a bit, because once you flip the axis, CW becomes CCW and normals point the other way and all sorts of good stuff.

Just so you know, I'm planning to implement Melkman's Algorithm. It won't handle a random set of points, but it works on a simple polyline (no intersecting lines) and runs in O(n). I think that should be acceptable because I assume most people will want a convex hull around an existing polygon, and not so often a random set of points.

Coordinator
Sep 18, 2009 at 8:04 PM

The default polygon orientation is counter clock-wise. We used a method of calculating the signed area to determine of the polygons given is ordered counter clock-wise or clock-wise. If they are clock-wise, we simply reverse them. The polygons are laid out in an ordinary coordinate system with Y-axis increasing upwards.

I've had a look at the Melkman's Algorithm before. Zzzzrrr from the Box2D forums played with it a little and implemented it in Scala. The thread can be found here.

Sep 18, 2009 at 9:38 PM

Ok, so my algorithm will output a convex hull wound CCW (with Y axis pointing upward), which will result in a polygon drawn CW on screen (am I correct?). The winding does not matter for the polygon being acted on.

Thanks for the link. It looks like Zzzzrrr referenced the same PDF that I had found. I see in the Scala code that no effort is made to avoid overstepping the bounds of the array. Does Scala provide for this (i.e. is arr(-1) equivalent to arr(arr.Length()-1))? It sure makes this sort of algorithm a bit less messy. Another thing, I don't think Zzzzrrr's implementation handles collinear points (something that the PDF's algorithm did not address). My algorithm is modified so that collinear points do not cause issues (unless the points aren't in order, but I would argue that in that case, it is no longer a simple polyline either).

I'm going to take a break and have lunch, and then look at submitting my code. I've done some debugging and it seems to be working fine now. I don't think I should be submitting example code or testing code, so for anyone who will want to see how it works, see that it works, or just test it, I included the following code in the Advanced Samples Demo8Screen.cs file:

In place of:

public override void Draw(GameTime gameTime)
{
    if (_leftGeom != null)
        _leftPolyBrush.Draw(_leftGeom.Position, _leftGeom.Rotation);

    ...

Put:

private int rotatenum = 0;
public override void Draw(GameTime gameTime)
{
    if (_leftGeom != null) {
        _leftPolyBrush.Draw(_leftGeom.Position, _leftGeom.Rotation);
        Vertices verts =  new Vertices(_leftGeom.WorldVertices);
        //Rotate vertices
        for (int i = 0; i < rotatenum; i++) {
            verts.Add(verts[0]);
            verts.RemoveAt(0);
        }
        rotatenum = (rotatenum + 1) % verts.Count; //Try starting on every point
        verts = verts.GetConvexHull();
        //Draw the convex hull
        PolygonBrush _convexPolyBrush = new PolygonBrush(verts, Color.Black, Color.Yellow, 2, 0.2f);
        _convexPolyBrush.Load(ScreenManager.GraphicsDevice);
        _convexPolyBrush.Draw(Vector2.Zero, 0);
    }
    ...

Sep 19, 2009 at 2:16 AM

This is just an update to say that I've submitted a patch with the GetConvexHull() code. It is Patch ID 3922. Feel free to try it out, and I'd like to hear if anyone finds any issues or areas where performance can be improved.