# Findling polygons in a list of points

This topic is 5151 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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?

##### Share on other sites
study theory and code for Delaunay triangulation

##### Share on other sites
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.

##### Share on other sites
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

##### Share on other sites
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.

##### Share on other sites
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

##### Share on other sites
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.

##### Share on other sites
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?

##### Share on other sites
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

##### Share on other sites
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.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 12
• 30
• 9
• 16
• 12