I was trying to make a simple random world generator for a geopolitical game yet to be done. I needed continent divided into territories and sea territories between them. I didn’t know at that point that I would solve a known mathematical problem.
The generator himself is divided into small elements. First not-so-random points are generated, spread evenly on the plane. After that, points are linked two by two with no overlapping. And then the real deal starts with polygon search in the produced graph.
The point generator
Not much to see here technically. To assure spreading, I implemented a minimum and a maximum distance between points. A new point needs to be farther than the minimum distance from every other point, and need to be closer than the maximum distance from the nearest point. For increased realism, the points are limited to a disk. Once there is more than 1000 misses (a new random point doesn’t fit in the rules) in a row, the point generation is complete.
The line generator
Since we had to calculate the distance between each new point and every other point, we do know the nearest points in the graph. That’s where we are going to draw lines, following a rule to limit the number of lines and allowing complex shapes : we only draw 2 lines from every point, even if the line has already been drawn. If the new line is overlapping another, we discard it and we draw a new one. We go on until we run out of points. At this point we have a nice little undirected graph with vertices and edges.
The polygon finder
For a human eye, finding all non-overlapping polygons in a graph is incredibly easy. But for a blind computer, it’s a little bit more complicated. But with a few simple rules, we can achieve what we want.
First of all, when we go through the graph, we always turn right. That way we always try to close the polygon we are in.
Then, when we found a cycle (e.g. during the course of the graph we fall back to a previous know vertice) we register it as a polygon of the graph. We now need a mean to know that we already found this polygon. We could check for polygon existence each time we find another one, but it would be terribly slow.
Instead, we rely on the fact that an edge of the graph can only belong to two contiguous polygons, and since we always go in circles the same direction, one edge can be traveled two ways, one for the polygon on one side, another for the contiguous polygon on the other side. Thus when we found a polygon, we forbid the algorithm to go through the edges in this direction again. But it still can (and will) go through them the other way, to find the contiguous polygons.
A problem remains : the outer edges of the graph don’t have contiguous polygons, and the algorithm may enter the outer edge circle looking for turning right, but since there would be no right, it will completely circle the graph counter-clockwise and believe that it is a polygon. It’s the only time where a found polygon can overlap the others. ((Of course, if the graph was concave, it would not work as easily as the center of the graph could be part of the outer polygon))
To circumvent this problem, we simply check that the point at the center of the graph is not included in the area of each found polygon. If it’s one of the point of the polygon, that’s not a problem, but if it is inside the area, that means that we found an overlapping polygon and discard it.
For each point of the graph, we try to find the contiguous polygons if they have not been already found. After all points have been tried, the polygon search is complete. We have a list of every non-overlapping polygon in the graph.
You can try it yourself at Worldgen v1 at Reactoweb Labs.
Feel free to play with the settings and post your best worlds !
Edit: Here’s a javascript implementation of this polygon-finding algorithm by Michael Chang of Puny Human Games. Feel free to check out their website and their projects as well!
it’s amazing, exactly what I was looking for!
I’m just not sure how to list all connections of a vertex in a consitent way, counterclockwise or clockwise? I found a way to do that with 2d points but not with 3d points = /
Glad it could have been of some use to you !
For the list of connections with 3D points, I would use a two-dimensionnal table with vertices references, just as I do with 2D points.
For example, with three points named A, B, and C, whatever their coordinates (either 2D or 3D), you can always maintain a connection table with the following format :
table[A] = [ B, C ] # A is connected to B and Ctable[B] = [ A ] # B is connected to A
table[C] = [ A ] # C is connected to A
This allows for unidirectional connections as well, in that case you don’t mirror the connection in the table when creating it. For example
table[A] = [ B, C ] # A is connected to B and Ctable[B] = [ A, C ] # B is connected back to A and to C
table[C] = [ A ] # C is only connected back to A
Hope it helps!
Hi MrPetovan,
Thank you very much for taking the time to explain it!!
sorry, I feel a bit stupid but I still didn’t get it =/
the way I’m trying to do is for each vertex of the graph I create a spanning tree using dfs
than for each vertex of the spanning tree I check if it is connected to the first vertex
it finds all the cycles but each one in a diferen order
here is what I have in python http://pastebin.com/54ePuQia
if you have a graph on that format:
graph = {vtx:[adjacent1, adjacent2, adjacent3], …}
what would be the Pseudocode to reorient those vertex connections to be in clockwise order or counter clockwise order?
thanks!!!
Was looking for a solution for this for months, on and off, trying all sorts of various algos that I was figuring out myself. I think the biggest breakthrough was your idea of marking edges as two-directional, and making sure each direction can only be traversed once.
My implementation is ugly as hell and really inefficient, but here it is in javascript, rendered with pixi.js:
https://dl.dropboxusercontent.com/u/705999/polyfinder/index.html
Thank you for this article!
I am so glad I helped someone else with this problem! I wasn’t sure who would need it anyway, I was just proud of myself for finding this simple but efficient solution. I added your implementation to the article as it’s more interactive than what I did.
Thanks again for stopping by!
congratulations! Excellent work! Very interesting algorithm.
I”m struggling and thinking hard to work out how you implemented this in your code, but to no avail.
I am working on a recursive algorithm but i cannot seem to be getting it right.
if you posted your code that would help a lot of people.
regards
Hey, this is great. I’d been trying out various approaches to this with varying success, myself. I had started to get an inkling for using edge directions in some way, but hadn’t quite honed in yet. Since testing whether a point is inside a non-convex polygon requires triangulating then testing the point against each resulting triangle (all rather costly!), it struck me that using Euler’s equation:
v – e + s = 2
Where v is num verts, e is num edges, and s is num polygons, for any planar graph, might help. The total number of polygons should (in most cases) end up being one greater than that equation predicts. The polygon with the largest number of constituent vertices / edges should be the shell that we want to discard. The rest are valid. Thoughts on this? I haven’t gotten around to implementing and testing this, myself.
Hi Oliver, there actually is a better method to check that a point is inside a non-convex polygon that doesn’t require triangulating and that I’m using in my own algorithm, check it out on Stack Overflow : http://stackoverflow.com/questions/217578/how-can-i-determine-whether-a-2d-point-is-within-a-polygon/218081#218081
Hi MrPetovan,
I’m just working on a problem where I want to find polygons in a user-defined graph. So far, your algorithm description was the best I found. However, I am having problems finding an algorithm for “turning right” (assuming I have a node with an incoming edge and multiple outgoing edges). Maybe that’s just because I’m not using the right search terms (I am neither very familiar with this whole graph topic, nor am I a native english speaker). It would be great if you could help me here or provide me some pointers to valuable sites. Thanks a lot!
Hi Fitsch, my method for “turning right”is pretty simple actually. Among all the outgoing edges, I take the smallest positive angle from the incoming edge. Positive means that if you get a negative angle from the incoming edge to any outgoing edge, you should add either 360° or 2π to get the equivalent positive angle.
Hi, this is almost exactly what I am trying to do! and it looks to be a clever and simple algorithm. Sadly, the link to the implementation is broken. Would you mind sharing your code? Thanks!
Hi Chris and thanks for stopping by! I never thought about publishing my code in the first place, I’m using it part of something, I’ll need some time to package it correctly. When it is ready, I will update both the post to remove the broken link and add mine.
Hi, I would love to see your algorithm but the link is broken.