Delaunay Traingulation

Tereth · 2015-03-23T21:51:02

I'm using a Voronoi Diagram for map generation, but the way I came to my Voronoi Diagram is incredibly dirty; I solved for the pixels within the polygons and not actually the vertices of the polygons. I then solve the vertices backwards. This takes an eon and occasionally fails to solve for vertices and adjacent polygons. I've looked at tutorials and explanations regarding Voronoi diagrams and Delaunay Triangulation and I understand how they work and I can draw them out on graph paper, but I'm having trouble putting these into an algorithm that produces a proper Voronoi Diagram. Obviously, this has been done before, but all of the tutorials I've found skip steps. I'll write out what my thoughts are so far and questions regarding each part. Please let me know where my logic falls short or if you know an answer to my question. Set -> n random points on a dSizeX x dSizeY grid My thoughts on a solution: -For each point (Pn) find all other points with that have non-crossing lines to (Pn) +The only solution I had for this was to make a line to all other points and cull out all that cross, keeping the lines that have closer points to Pn. This seems like an incredibly inefficient way to do this. Is there a better solution? -Find the bisecting perpendicular line to all lines left over [I've got this] -Find the intersections between all bisecting perpendicular lines to solve for Voronoi Vertices of the polygon. [I've got this] If you have any comments, suggestions or links to tutorials that you think would be helpful, I would greatly appreciate it. Also, if there's a simpler solution, I would be grateful for direction. Thank you! Here's a screenshot of my dirty diagram where I colored all polygons random colors: