
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.



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.



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 mathstyle cartesian coordinate system (Y increases upward) or on a computer
graphicsstyle (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.



The default polygon orientation is counter clockwise. We used a method of calculating the signed area to determine of the polygons given is ordered counter clockwise or clockwise. If they are clockwise, we simply reverse them. The polygons are laid out
in an ordinary coordinate system with Yaxis 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.



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);
}
...



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.

