I'm working on the map editor of a game, where you can create a grid of hexagons to paint. An example of a grid of radius 6:

Groups of hexagons of different colors

What I want

Once map creation is done, I would like to generate a mesh for each of these islands of color, with the least possible number of vertices.

What I have so far

My approach gives me a list of outer vertices for an island and a list of inner edges, which represent holes in the mesh. Outer and inner edges never overlap.

The gray area on the right of the image above has 3 holes, so what my code gives me is a list of vertices around the gray area and 3 lists of vertices for each hole inside it.

Problems I'm having

While I can already triangulate islands without holes, I can't find a way to turn the ones with holes into meshs. How should I approach solving this problem?

  • \$\begingroup\$ The general solution is something called Monotone Polygon Triangulation, where you take a couple of passes across a set of curves to break them into simple polygons that can be triangulated efficiently. In your case you might be able to skip some of that complexity by operating at the tile level, splitting the tiles into groups/chunks on either side of the hole. \$\endgroup\$ – DMGregory Apr 2 '17 at 22:50
  • \$\begingroup\$ Thank you @DMGregory, I'm using polypartition now. \$\endgroup\$ – Luke B. Apr 4 '17 at 14:41
  • \$\begingroup\$ It sounds like that would be worth writing up as an answer. If you give a high-level runthrough of the steps you took to integrate this, that could be a useful guide for future users with similar issues. \$\endgroup\$ – DMGregory Apr 4 '17 at 14:49
  • \$\begingroup\$ That's a good idea! I'm still having trouble with the library though (not a lot of documentation) so it might take a while. \$\endgroup\$ – Luke B. Apr 4 '17 at 20:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.