Hi,

I expect this has been asked before but I honestly don't really know how to go about finding the information since most of my searches don't contain the information I expect.

My problem at the moment is that I am trying to create a list of indices from a set of points. The points have to work in clockwise direction to create the custom 2D geometry.

I have draw out some images to hopefully explain what I want to do and the way I am currently thinking about going about it.

In Shape A (0) I have my 6 points which make up my shape and in Shape A (1) you can see what shape it should create if the points are connected one after the other starting at 1 and ending at 1. To Draw the shape I ideally would like to segment the shape into triangles and have the points of each triangle as shown in Shape A (2).

Now the way I am currently thinking about doing this is to actually start with breaking the shape into as many quads as possible since I feel they are easier to work with and once all the quads have been found its just a matter of cutting them in half to create all the triangles for the shape. So in Shape A (3) I would start with points 1, 2, 3, 4 and check to see if they can create a valid quad which does not have any sides intersecting each other and that the quad does not have any of the other points of the shape inside of it. In Shape A (3) 1, 2, 3, 4 is valid and points 2 and 3 can now be ignored since they wont ever have anything else connect to them. Since there are now only 4 points left the next quad should be 4, 5, 6, 1.

I haven't tried it with too many shapes on paper but I believe that system should work and in Shape B it also works but unlike shape A points 1, 2, 3, 4 don't create a valid quad as can be seen in Shape B (0). So points 2, 3, 4, 5 are then checked and again they wont make a valid quad. 3, 4, 5, 6 do how ever and 4 and 5 are now take out. 6, 7, 1, 2 should also not make a valid quad but 7, 1, 2, 3 will (1 and 2 are then take out). That then leaves 3, 6, 7 left to create a triangle.

The only issue I have though is when it comes to concave shapes as can be seen in Shape C (0). 1, 2, 3, 4 is valid as well as 4, 5, 6, 7. As you can see though 4, 5, 6, 7 does not correctly create the shape and also means 5 and 6 are ignored leaving 8, 9, 1, 4 to be valid even though 5 and 6 are inside of the quad. If the concave section is spotted and is ignored correctly then Shape C (1) should be the result.

Sorry if I have explained this really poorly. It all make sense in my head but I sometimes struggle explaining it.

If there are any simpler method of doing this of anything that you think will help that would be good enough.

Thanks

Chris

One algorithm that should work in this situation to break the shape into convex hulls that can be drawn more easily:

1. Pick a point, add it a list A which shall be our first convex sape

2. Cycle through points going clockwise

3. Check each such point to make sure that it is further clockwise than the previously checked one

4. If it's not clockwise not, then ignore add it to a list of points left over

5. If it is clockwise, add it to the convex hull

5a. If it is clockwise and the previous one was not, run this algorithm recursively, making a new convex shape by iterating over the list of left-over points (clear left-over point list when done)

6. Continue until all points have been checked

I hope that's clear. Basically, anything that isn't still going clockwise is a new convex (recusively, since this might also need to be broken up), but anything that is, is. This isn't guaranteed to have the best possible break-up of convex shapes and I'm sure you could come up with weird shapes that it would break up inefficiently. But I suspect it will work for the vast majority of things. It is guaranteed that for any non-self-intersecting shape it will fill exactly its interior and none of its exterior. Don't expect it to work sanely with self-intersections. Also, your choice of initial point will affect how it makes the convex shapes.

Note that a convex shape can be drawn by picking any point and drawing a 'triangle fan' out from that point, like the (out-dated?) OpenGL function for that.

One algorithm that should work in this situation to break the shape into convex hulls that can be drawn more easily:

1. Pick a point, add it a list A which shall be our first convex sape

2. Cycle through points going clockwise

3. Check each such point to make sure that it is further clockwise than the previously checked one

4. If it's not clockwise not, then ignore add it to a list of points left over

5. If it is clockwise, add it to the convex hull

5a. If it is clockwise and the previous one was not, run this algorithm recursively, making a new convex shape by iterating over the list of left-over points (clear left-over point list when done)

6. Continue until all points have been checked

I hope that's clear. Basically, anything that isn't still going clockwise is a new convex (recusively, since this might also need to be broken up), but anything that is, is. This isn't guaranteed to have the best possible break-up of convex shapes and I'm sure you could come up with weird shapes that it would break up inefficiently. But I suspect it will work for the vast majority of things. It is guaranteed that for any non-self-intersecting shape it will fill exactly its interior and none of its exterior. Don't expect it to work sanely with self-intersections. Also, your choice of initial point will affect how it makes the convex shapes.

Note that a convex shape can be drawn by picking any point and drawing a 'triangle fan' out from that point, like the (out-dated?) OpenGL function for that.

This is interesting and much better than what I proposed as it avoids the costly segment vs segment intersection tests. Do you know what it's called?

Sounds like gift wrapping to me: http://en.wikipedia.org/wiki/Gift_wrapping_algorithm

Thanks for the replies so far. I'm going to have to look through them tomorrow and work out how they function.

I also noticed I said convex instead of concave with the last shape. I have no problem with convex shapes its when the shape has a concave section I have a problem.

One algorithm that should work in this situation to break the shape into convex hulls that can be drawn more easily:

1. Pick a point, add it a list A which shall be our first convex sape

2. Cycle through points going clockwise

3. Check each such point to make sure that it is further clockwise than the previously checked one

4. If it's not clockwise not, then ignore add it to a list of points left over

5. If it is clockwise, add it to the convex hull

5a. If it is clockwise and the previous one was not, run this algorithm recursively, making a new convex shape by iterating over the list of left-over points (clear left-over point list when done)

6. Continue until all points have been checked

I hope that's clear. Basically, anything that isn't still going clockwise is a new convex (recusively, since this might also need to be broken up), but anything that is, is. This isn't guaranteed to have the best possible break-up of convex shapes and I'm sure you could come up with weird shapes that it would break up inefficiently. But I suspect it will work for the vast majority of things. It is guaranteed that for any non-self-intersecting shape it will fill exactly its interior and none of its exterior. Don't expect it to work sanely with self-intersections. Also, your choice of initial point will affect how it makes the convex shapes.

Note that a convex shape can be drawn by picking any point and drawing a 'triangle fan' out from that point, like the (out-dated?) OpenGL function for that.

I tried out what you mentioned one paper and It makes a lot of sense and is far quicker than the ideas I was coming up with.
It also will help with box2D when I come to allow for concave shapes.

I will code it in tomorrow or tonight and see if it all works but I believe it should do. The only time I can see it breaking is when a lines intersect which should not happen any way.