Get a polygons from edges

[furqan_sindhu]

we dont know about the no of sides, each polygon has different no of sides what is meant by ordered list in this case? the list is totally random, just a list of all the edges, no ordering at all. :( :) Thanks for looking into this! ANY IDEA NOW?

[73Zeppelin]

furqan_sindhu wrote:

what is meant by ordered list in this case? the list is totally random, just a list of all the edges, no ordering at all.

This is what I was trying to understand when I asked about an ordered list. If all the points are simply in a random list, how can you possibly reconstruct the polygons based only on a list of random points? The problem is that polygons can take on complicated shapes, so you need to know something about number of sides and/or which points should belong to which polygons. At the very minimum, the points should be ordered according to which polygon they belong to. Is there no way of doing this? Can't you create a polygon class that contains a list of points, for example?

[Member 4194593]

You might want to check in "Algorithms" by Robert Sedgewick, published by Addison-Welsley. He has several algorithms, including "Convex Hull" and "Voronoi" for solutions for these problems. Dave.

[73Zeppelin]

I'm not familiar with the book or the algorithms, but I don't think he's trying to construct the convex hull. I think he's got a randomized list of polygon edges for separate polygons and he's trying to reconstruct the component polygons from the list. A convex hull can certainly be determined given the points, but I'm not convinced that's what he wants to do.

[Member 4194593]

My reply was more directed to his statement that he didn't know what to do with his Voronoi edges. In addition, his stated edges do NOT form three polygons. There are two missing edges one between 2,2 and 2,3, and the other between 2,0 and 4,0, both of which he filled in in the case of the polygon descriptions. He is forming a convex hull with enclosed polygons. He also probably wants to split up the polygons into triangles, but that is another topic. Dave.

[73Zeppelin]

So the list isn't even complete? Hmmmm. Methinks he needs to put a little more forethought into this one. It helps to have the problem well-defined first!

[furqan_sindhu]

well, i dont know anything at all. i just have a list of edges and thats all. I was working on this and uptil now, i have come up with some code that gives me all possible polygons from those edges. All possible means that it returns those polygons as well that contain multiple small polygons too. I am trying to come up with something to eliminate these bigger polygons :) :) Anyways! i think i will get it done, inshaALLAH.

[furqan_sindhu]

oh, i had a look at your message a little late "Member 4194593". thanks for your reply. i think i accidentally missed those edges. my apologize!!! i dont want to construct triangles, rather polygons. i will have a look at those alogs!

[Member 4194593]

I have thought about the problem these last few days. Googled for "Convex Hull" and read all of the related articles. Usually only points are given, not edges. If edges are given, wouldn't at least those edges be required in the final solution? I don't think that eliminating one of these edges would be a solution. If you are given a triangle, then it is a triangle area, you can't make it a square by combining it with some other area - people don't take kindly to "re-districting" or "Gerrymandering". Fortunately, it has been proven that you only need 4 colors to tint your map when you get it done. I would be interested in the exact phrasing of the problem as given, along with your final solution. I love algorithms and I frequent these halls daily. I am serious about the book "Algorithms" - there is such an abundance of simple piece-wise efficient solutions to this type of problem described in this book, and Sedgwick explains it so clearly. Dave.

[darrellp]

I think you have some errors in the list of edges. For instance, your polygons include an edge from (2,0) to (2,3) but there is no such edge in your list of edges. Anyway, I think what you're suggesting here is that you've got a list of edges and vertices which define a mesh (often referred to a "boundary representation") and you want to find the polygons in that mesh. I'd suggest that you look at Winged Edge representation, turn your edges into a winged edge rep and get your polys from that. Essentially, you'd have to keep a list of vertices with the edges around them in clockwise order, then traverse each vertex and trace out each poly between adjacent edges. You have to be careful about skipping over polys that have already been listed which means you have to keep track of the polygons each edge separates. It'd be a bit ugly, but I think that's pretty much what's required. It would also mean that the area surrounding the entire mesh will be represented as a "polygon". You can recognize that polygon by looking at the rightmost vertex, getting the first edge from it that is CCW from vertical and the flagging the polygon clockwise from that edge as the "exterior polygon". If you're looking for a Voronoi diagram that keeps a record of all the polygons, I've got one that I've been thinking about putting up on CodeProject. There's a fortune algorithm already out there on CodeProject, but it has some bugs and pretty much has a dump of edges like you're talking about without an indication of the polygons each edge goes with. Mine gives a full winged edge representation of the diagram which includes all the polygons, edges and vertices with them all hooked together intelligently. If that's what you're looking for, perhaps I'll put my fortune algorithm up earlier rather than later.