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