Sign in to follow this  
Dekowta

Custom 2D geometry from a list of points.

Recommended Posts

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.

KzHulKi.png

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

Edited by Dekowta

Share this post


Link to post
Share on other sites

It seems to me that the set of lines drawn by connecting each numbered point to the next already uniquely defines the polygon, so the only real question is how to triangulate it, yes? The Wikipedia article on polygon triangulation might be a good place to start. In general I think the right approach is to split the polygon into sub-shapes that are easier to triangulate (e.g. convex polygons, monotone polygons); breaking it into quads the way you're suggesting seems plausible, but it looks like you haven't proven that it will work in all cases, so unless you can do that it might not be the best approach.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

I'm not an expert at this but I have solved this problem before.  I would recommend against using quads as a conceptual primitive for the algorithm, it will only make your life harder.  The first thing you need to do is establish a convention:  specify your points in order such that they traverse the boundary of the shape in counterclockwise order.  This is needed to consistently distinguish the inside of the shape from the outside and well as provide a convenient mathematical property for the edges.  If you have an edge vector (x, y) then the 2d cross product of (x, y) produces a vector that points outside of the shape.  The 2d cross product is defines as:

 

Cross2D(x, y) = (y, -x)

 

The gist of the tessellation algorithm is simple, it looks like this:

Initialize the set S to the edges on the boarder of your shape
Initialize the triangle set T to empty

For each edge (a, b) on the border of your shape
{
   For each vertex p on the border of your shape (that is not a or b)
   {
       triangle t = triangle(a, b, p)
       vector3  n = (b.x-a.x, b.y-a.y, 0) cross (p.x-a.x, p.y-a.y, 0)
       if n.z > 0 AND
       if edge (b, p) and edge (p, a) do not intersect any of the edges in the set S
       {
          1) add t to the triangle list T
          2) and add the edges (b, p) and (p, a) to to the edge set S
       }
    }
}

The set T now contains the set of triangles that tessellates your shape

This is the most basic algorithm for triangulating a 2d polygon.  The Wikipedia page cowsarenotevil pointed out will lead you to more intelligent algorithms.

Share this post


Link to post
Share on other sites

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?

Share this post


Link to post
Share on other sites

 

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

Share this post


Link to post
Share on other sites

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.

 

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this