org.jbox2d.util.nonconvex
Class Polygon

java.lang.Object
  extended by org.jbox2d.util.nonconvex.Polygon

public class Polygon
extends java.lang.Object

This code is very old and doesn't work anymore. Will be updated for 2.0 soon...

Author:
ewjordan

Field Summary
static int maxVerticesPerPolygon
           
 int nVertices
           
 float[] x
           
 float[] y
           
 
Constructor Summary
Polygon(float[] _x, float[] _y)
           
Polygon(org.jbox2d.util.nonconvex.Triangle t)
           
Polygon(Vec2[] v)
           
 
Method Summary
 Polygon add(org.jbox2d.util.nonconvex.Triangle t)
           
 void addTo(PolygonDef pd)
           
static Polygon convexHull(float[] cloudX, float[] cloudY)
           
static Polygon convexHull(float[] cloudX, float[] cloudY, int nVert)
           
static Polygon convexHull(Vec2[] v)
          Find the convex hull of a point cloud using "Gift-wrap" algorithm - start with an extremal point, and walk around the outside edge by testing angles.
static Polygon convexHull(Vec2[] v, int nVert)
           
static Polygon[] decomposeConvex(Polygon p)
          Decomposes a non-convex polygon into a number of convex polygons.
static void decomposeConvexAndAddTo(Polygon p, BodyDef bd, PolygonDef prototype)
          Decomposes a polygon into convex polygons and adds all pieces to BodyDef using a prototype PolyDef.
 Vec2[] getVertexVecs()
           
 boolean isConvex()
           
 boolean isSimple()
           
static Polygon[] polygonizeTriangles(org.jbox2d.util.nonconvex.Triangle[] triangulated)
          Turns a list of triangles into a list of convex polygons.
 void set(Polygon p)
           
static org.jbox2d.util.nonconvex.Triangle[] triangulatePolygon(float[] xv, float[] yv, int vNum)
          Triangulates a polygon using simple O(N^2) ear-clipping algorithm.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

maxVerticesPerPolygon

public static int maxVerticesPerPolygon

x

public float[] x

y

public float[] y

nVertices

public int nVertices
Constructor Detail

Polygon

public Polygon(float[] _x,
               float[] _y)

Polygon

public Polygon(Vec2[] v)

Polygon

public Polygon(org.jbox2d.util.nonconvex.Triangle t)
Method Detail

getVertexVecs

public Vec2[] getVertexVecs()

set

public void set(Polygon p)

isConvex

public boolean isConvex()

isSimple

public boolean isSimple()

add

public Polygon add(org.jbox2d.util.nonconvex.Triangle t)

addTo

public void addTo(PolygonDef pd)

triangulatePolygon

public static org.jbox2d.util.nonconvex.Triangle[] triangulatePolygon(float[] xv,
                                                                      float[] yv,
                                                                      int vNum)
Triangulates a polygon using simple O(N^2) ear-clipping algorithm. Returns a Triangle array unless the polygon can't be triangulated, in which case null is returned. This should only happen if the polygon self-intersects, though it will not _always_ return null for a bad polygon - it is the caller's responsibility to check for self-intersection, and if it doesn't, it should at least check that the return value is non-null before using. You're warned! This is totally unoptimized, so for large polygons it should not be part of the simulation loop. For smaller ones it's less of an issue.


polygonizeTriangles

public static Polygon[] polygonizeTriangles(org.jbox2d.util.nonconvex.Triangle[] triangulated)
Turns a list of triangles into a list of convex polygons. Very simple method - start with a seed triangle, keep adding triangles to it until you can't add any more without making the polygon non-convex. Takes O(N*P) where P is the number of resultant polygons, N is triangle count. The final polygon list will not necessarily be minimal, though in practice it works fairly well.


decomposeConvex

public static Polygon[] decomposeConvex(Polygon p)
Decomposes a non-convex polygon into a number of convex polygons. Makes sure that each polygon has no more than common.Settings.maxPolyVertices vertices. Returns null if operation fails (usually due to self-intersection of polygon). Please report any other failures to ewjordan at gmail.


decomposeConvexAndAddTo

public static void decomposeConvexAndAddTo(Polygon p,
                                           BodyDef bd,
                                           PolygonDef prototype)
Decomposes a polygon into convex polygons and adds all pieces to BodyDef using a prototype PolyDef. All fields of the prototype are used for every shape except the vertices (friction, restitution, density, etc). If you want finer control, you'll have to add everything by hand. This is the simplest method to add a complicated polygon to a body.


convexHull

public static Polygon convexHull(Vec2[] v)
Find the convex hull of a point cloud using "Gift-wrap" algorithm - start with an extremal point, and walk around the outside edge by testing angles. Runs in O(N*S) time where S is number of sides of resulting polygon. Worst case: point cloud is all vertices of convex polygon -> O(N^2). There may be faster algorithms to do this, should you be needy for one - this is just the simplest. You can get O(N log N) expected time if you try, I think. Returns null if number of vertices passed is less than 3. FIXME?: May be buggy with colinear points on hull. Couldn't find a test case that resulted in wrong behavior. If one turns up, the solution is to supplement angle check with an equality resolver that always picks the longer edge. I think the current solution is working, though.


convexHull

public static Polygon convexHull(Vec2[] v,
                                 int nVert)

convexHull

public static Polygon convexHull(float[] cloudX,
                                 float[] cloudY)

convexHull

public static Polygon convexHull(float[] cloudX,
                                 float[] cloudY,
                                 int nVert)