Findling polygons in a list of points
Author
Hi i would be very greatful if anyone could give me a tip on how to solve this or were i can find information about it.
I have a list of 2d points, the point contains xpos ypos and a list of connecting points. Now what i want to do is to generate simple polygons out of the list of points. Is it possible to do at all?
Since you have a list of connecting points, you can sort the "edges" in *-wise order around each point, and find polygons by following the rightmost edge at each point you arrive (rightmost from the point where you came from). Mark the edges with the direction you followed them, and once all edges are marked you have a list of all polygons.
Author
Ty for the answers.
I did not see how Delaunay triangulation can help me realy as it triangulates as it see fit not as i want it (or so i think after a quick look at it).
I dont think that i made my problem clear so take a look at this ilustration (programmers art) http://www.imagedump.com/index.cgi?pick=get&tp=306980 .
I have a number of points in random order that i want to turn into a number of simple polygons. If I go with the turn right idea isn't there a risk that i miss zone 4 completly sinse it shares all endes with other zones. And how do i deside what way is cc-wise and what is c-wise?
Any ideas?
/Calle
I did not see how Delaunay triangulation can help me realy as it triangulates as it see fit not as i want it (or so i think after a quick look at it).
I dont think that i made my problem clear so take a look at this ilustration (programmers art) http://www.imagedump.com/index.cgi?pick=get&tp=306980 .
I have a number of points in random order that i want to turn into a number of simple polygons. If I go with the turn right idea isn't there a risk that i miss zone 4 completly sinse it shares all endes with other zones. And how do i deside what way is cc-wise and what is c-wise?
Any ideas?
/Calle
Your problem is not well defined. Delaunay triangulation will turn your points into simple polygons, and that is what you asked for. Your image shows a bunch of very arbitrary polygons. Maybe you could triangulate the points and then merge adjacent triangles together to make bigger polygons up to some limited size.
Author
The polygons represents a zone on a map. Once the user is done editing a map I want the user to be able to push a button and my editor will find all the diffrent zones.
An alternative would be to ask the user to fill the polygonlist manually but that will not be as user friendly.
btw i might have hade a translation error... are simple plygons only triangles?
/calle
An alternative would be to ask the user to fill the polygonlist manually but that will not be as user friendly.
btw i might have hade a translation error... are simple plygons only triangles?
/calle
CW and CCW are abbreviations for clockwise and counter-clockwise winding. Winding is simply which direction you number the vertices. Given a polygon with one vertex specified as 1 then you have two choices for which one is 2. Which of those you choose determines the numbers for the rest. Which you choose determines which direction around the polygon you go, i.e. cw or ccw. It is critical in 3D so you can tell the front from the back without having to explicitly state it.
It is useful in 2D as well even though front and back isn't particularly relevant. You need consistancy. It isn't that you use an edge only once, but rather you use it once in a given direction. You need the winding to insure that two polygons sharing an edge use it in opposite directions. Polygons 1 and 3 in your diagram share an edge. If you wind them in opposite directions they both use that edge in the same direction. So if you don't have consistancy in the winding then you can't tell if that edge can be used or not.
You could say that you can only use an edge twice. Say you start at a point used only by polygon one and generate polygon 1. Then say your next point is only a point used by polygon 1. Well, you can use each edge twice so you get polygon 1 again. Now you can't generate polygons 2, 3 or 4 because the edges they need have already been used twice. So isn't sufficent that an edge is only used a maximum of twice.
You should take the simple off. It's just a polygon. Polygons can be split into convex and concave polygons. People will generally assume convex if you say simple. Convex meaning a line connecting any two vertices does not intersect a side. Convex being simplier because there are fewer possible scenerios. An example being with convex polygons they cannot obstruct each other.
It is useful in 2D as well even though front and back isn't particularly relevant. You need consistancy. It isn't that you use an edge only once, but rather you use it once in a given direction. You need the winding to insure that two polygons sharing an edge use it in opposite directions. Polygons 1 and 3 in your diagram share an edge. If you wind them in opposite directions they both use that edge in the same direction. So if you don't have consistancy in the winding then you can't tell if that edge can be used or not.
You could say that you can only use an edge twice. Say you start at a point used only by polygon one and generate polygon 1. Then say your next point is only a point used by polygon 1. Well, you can use each edge twice so you get polygon 1 again. Now you can't generate polygons 2, 3 or 4 because the edges they need have already been used twice. So isn't sufficent that an edge is only used a maximum of twice.
You should take the simple off. It's just a polygon. Polygons can be split into convex and concave polygons. People will generally assume convex if you say simple. Convex meaning a line connecting any two vertices does not intersect a side. Convex being simplier because there are fewer possible scenerios. An example being with convex polygons they cannot obstruct each other.
But what constitutes a zone? Does the user just enter points and then the program arbitrarily turns them into polygons which represent zones? I would think defining the zones would be part of the map editing. What are the zones used for? If they are used for something the user needs to know about directly, they should be part of the map editing. If they are used for graphics or some other algorithm, then there are probably some properties you want the polygons to have, and that would help determine how to form them.
As it is you are just saying you want to take the points and make polygons. You haven't put any constraints on them. Do you want N polygons? N polygons of roughly the same area or number of vertices? What properties should the zones have?
As it is you are just saying you want to take the points and make polygons. You haven't put any constraints on them. Do you want N polygons? N polygons of roughly the same area or number of vertices? What properties should the zones have?
Author
The user will put in points and edges but the actual zone defining i want to automate. A zone is a polygon not having any points or edges inside it.
I am right now considering if i should not let the user define the zones by hand, i am not finding any good way to make this automated.
/calle
I am right now considering if i should not let the user define the zones by hand, i am not finding any good way to make this automated.
/calle
OK I think I misunderstood your problem; I didn't realize you already had all the edges defined.
Intuitively you can start with an edge and a point and rotate the edge counterclockwise around the point until it hits a second edge. This second edge is part of the same polygon. Then you rotate this second edge around its other point and find a third edge. This continues until you get back to the starting edge.
Then you can find the other polygon the edge is bordering by rotating the edge counterclockwise around its other point, and continue around that way.
In the implementation you wouldn't actually rotate the edges around until they collide, you'd be comparing the angles between the edges to figure out which edge it would collide with first if it were being rotated.
Also this algorithm will mark the area outside your edges as being another polygon, but its winding order will end up being clockwise instead of counterclockwise, while the interior polygons will have counterclockwise winding orders.
Intuitively you can start with an edge and a point and rotate the edge counterclockwise around the point until it hits a second edge. This second edge is part of the same polygon. Then you rotate this second edge around its other point and find a third edge. This continues until you get back to the starting edge.
Then you can find the other polygon the edge is bordering by rotating the edge counterclockwise around its other point, and continue around that way.
In the implementation you wouldn't actually rotate the edges around until they collide, you'd be comparing the angles between the edges to figure out which edge it would collide with first if it were being rotated.
Also this algorithm will mark the area outside your edges as being another polygon, but its winding order will end up being clockwise instead of counterclockwise, while the interior polygons will have counterclockwise winding orders.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
