Hello All! I had somehow represent concave polygon in 2R space, and after minute of guessing I just pick conception like split con-cave polygon to group of convexes to provide collision routine tests. I have a soup of 2D points that should be preprocessed somehow, also there should be some verification for those con-caves that is self-intersecting to prevent it from collisions. But after few-time in google, I found nothing interesting, and even don't know where to start... So maybe you guys help me find out liks to papers or point me to some code-sample to implement this thing? Thanks in advance!

I've never done it, its a complex issue truely. I have seen it done, at least the general method and the result, I can't find it but if I do I'll post it here.

The general method was

- Pick a random point, then two points closest to that one. This is a virtual triangle
- Pick a random point that is outside this triangle, now you have 2 triangles.
- Keep doing this until you can no longer pick any points that would be outside the polygon formed from your triangles. This should create a convex polygon.

Edit:

Still haven't found exactly it, but this guy seems to have read the same stuff
http://stackoverflow.com/questions/359673/random-but-regular-polygon-generator

Yeah, maybe it's about some triangulation, I dunno yet, but here is picture,
it's mean that algorithm should build all possible pattern and only then pick
such one that is more efficient (has few triangles)



And I don't think that is the same as pick any random 3 points and continue build further... beause we can build inside our ARCH :D

I think you are going to have to come up with some rules about the types of polygons you want (maybe the "minimum triangle count" rule will be enough) because as you point out, the other method could make triangles inside the arch and you don't want that.

I'm curious, what are you trying to do with these points?

Also, where are these points coming from and what do you intend to do with the resulting shape? Do the points have an "order" they came in (ie drawn with a mouse) or is it really just a bunch of points without order?

These answers might give away some of your secret plans, but they might also let someone be able to help you more specificially (;

Ok, I draw collision shape in editor for platformer geometry, so I guess, save draw ordering is possible.

Added: I think maybe 'convex-cization' method will have as enter parameter array of points ordered from first to last point to build concave polygon by traveling from beginning to the ending of array, the problem now is howto triangulate
that polygon.

[Edited by - Lolmen on May 28, 2009 9:52:33 PM]

We had a discussion of this very topic a few days ago.

2 Alvaro
found noting except some formules to check is it skinny triangle...
And some very scientific samples of polysoup triangulation...

Quote:Original post by Lolmen
Ok, I draw collision shape in editor for platformer geometry, so I guess, save draw ordering is possible.

Added: I think maybe 'convex-cization' method will have as enter parameter array of points ordered from first to last point to build concave polygon by traveling from beginning to the ending of array, the problem now is howto triangulate
that polygon.

Here's a good method for breaking a polygon into triangles, I used it to make a fill tool for a game that is now on the shelves in the stores and it worked great (;

http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

Quote:Original post by Lolmen
2 Alvaro
found noting except some formules to check is it skinny triangle...

Well, you mentioned something about the "most efficient pattern", so I figure you want to avoid skinny triangles too. What else would "most efficient" mean?

Quote:And some very scientific samples of polysoup triangulation...

My first response in that thread is a link to an actual implementation of constrained Delaunay triangulation, which is how I suggest you find the "most efficient" triangulation. Farther down the thread I give another alternative, which is to start with any triangulation (ear clipping would do) and then do a bunch of Delaunay flips to get rid of skinny triangles, if possible. Nothing too scientific, IMHO.

Quote:Original post by alvaro
My first response in that thread is a link to an actual implementation of constrained Delaunay triangulation, which is how I suggest you find the "most efficient" triangulation. Farther down the thread I give another alternative, which is to start with any triangulation (ear clipping would do) and then do a bunch of Delaunay flips to get rid of skinny triangles, if possible. Nothing too scientific, IMHO.

The standard greedy algorithm for ear clipping (grab first available ear from an ordered list of ears) can produce skinny triangles. Doing the "Delaunay flips" after the fact certainly works, but Graham Rhodes' suggestion (in another thread) of using the empty circumcircle condition to be smarter about ear selection is a good one. That idea is the heart of the operation to remove a point from a Delaunay triangulation, although the sorting of ears is based on a ratio of the determinant from the circumcircle test and the determinant whose sign tells you whether a vertex is convex or reflex. If you want to see an illustration of this, and then adapt the idea to triangulation of any triangle, see my Geometric Tools web site, files Wm4IncrementalDelaunay2.{h,cpp}. The ears are stored in a priority queue (as compared to my TriangulateEC ear clipper that stores them in an ordered list).

As you noted ("if possible"), skinny triangles can occur even in a Delaunay triangulation. Recall that the union of the Delaunay triangles is a convex polygon. Imagine such a polygon that has one very long edge, the remaining edges short. Now imagine the closest input point to the long edge is nearly on that edge. This point and the long edge will form a skinny triangle, and no amount of "Delaunizing" will change that :)

Constrained Delaunay triangulations have similar issues, where skinny triangles can occur (a triangle contains a required edge).