2
\$\begingroup\$

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?

\$\endgroup\$
4
  • \$\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\$ Commented Apr 2, 2017 at 22:50
  • \$\begingroup\$ Thank you @DMGregory, I'm using polypartition now. \$\endgroup\$ Commented Apr 4, 2017 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\$ Commented Apr 4, 2017 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\$ Commented Apr 4, 2017 at 20:34

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.