3
\$\begingroup\$

Is there an algorithm for drawing an outline around around an arbitrary group of hexagons? The polygon outline drawn may be concave. See the images below, the green line is what I am trying to achieve. The hexagons are stored as vertices and drawn as polygons.

Edit:

I've uploaded images that should explain more. I want to favour convex hulls because it's conveys an area of control more quickly. Each hexagon is stored in a multidimensional array so they all have x and y coordinates, I can easily find adjacent hexagons and the opposite vertex, i.e. adjacentHexagon = getAdjacentHexagon( someHexagon, NORTHWEST ) if there isn't a hexagon immediately adjacent it will continue to search in that direction until it finds one or hits the map edges.

enter image description here enter image description here enter image description here enter image description here

|improve this question
\$\endgroup\$
  • \$\begingroup\$ It looks like the line-drawing behavior in the second screenshot differs from that in the first. In the first screenshot the lines are drawn in a sort of "path", connecting each hex to the hexes before and after it. In the second screenshot, the lines form a sort of "bounding polygon." Which one are you asking about? \$\endgroup\$ – Wackidev Jun 8 '12 at 18:25
  • 1
    \$\begingroup\$ A couple of things that might help if you clarified them: Is it guaranteed that the hexagons will be aligned on lines angled at +-30°, as they are in your sketches? As @Wackidev said, the second sketch looks more like a convex hull. Also, do you want just the outline, or a polygon/set of triangles of the shape defined by the outline? Another thing...do you just want the algorithm to choose some path, or what criteria do you want it to use to select the path? If you want it to take a specific path, it might be easier to keep that path as a list of indices somewhere. \$\endgroup\$ – user13213 Jun 8 '12 at 19:45
  • \$\begingroup\$ I've explained some more in the edit, and yes all hexes are tessellated on a grid and stored in a multidimensional array. \$\endgroup\$ – Perky Jun 8 '12 at 21:01
  • \$\begingroup\$ Is there any additional clustering info on your data? For instance, there are several different valid ways of outlining the first set of hexes (consider a 'tree' that connects the pair of red hexes on the right connected to the hex due left of the lower of that pair, and treats the hex right above the white hex as a leaf node). And is the convex hull actually favorable in situations where it can be drawn, and if so, why? It feels like your core question right now is still behavioral, not algorithmic, and that explicitly defining your desired behavior will make an algorithm self-evident. \$\endgroup\$ – Steven Stadnicki Jun 8 '12 at 21:53
  • \$\begingroup\$ as well as each hex having an x, y co-ordinate they are also connected via the white lines you see. These white line connections a generated randomly from map to map. The reason I want to favour convex hull is because the player will spend most their times zoomed out and I want large visual areas to convey areas of control. I've changed to images to be more specific to what I am looking for. \$\endgroup\$ – Perky Jun 8 '12 at 22:31
7
\$\begingroup\$

It seems to me that the easiest way to do this would be in two steps:

  • Determine the smallest possible convex polygon surrounding all red nodes.

  • Expand the convex polygon until it reaches the largest possible area without intersecting with white nodes.

Suppose we start with this situation:

Programmer art 1

Look at that glorious programmer art. I've chose red and green for the node colors because it makes things a bit more visible.

Think of it like a balloon. First we wrap it around the nodes as tight as possible, and then we'll blow it up as much as it will allow.

We want to create a conbex polygon around all the edges. So we start at an arbitrary node, let's say the one at the top-left.

  • Starting at the top-left corner on the first node, we move around it in a clockwise fashion, towards the node in the top-center.
  • When the distance between the points on the first node with the center of the second node becomes greater instead of smaller, we jump to the next node.
  • The next node is never the node we came from, unless we've reached the last node. In that case, we traverse the node graph in reverse order.

This is a very basic algorithm, but it works. Here's what you should end up with:

Programmer art 2

Unfortunately, this polygon is too thin. Lines have collapsed onto each other. So let's expand the polygon with a new algorithm.

  • Store the original convex polygon we made.
  • For every line segment, try creating a new line segment to the next point in sequence if that's valid. For example, instead of a line segment {Node1, point2}{Node1, point3}, create a line segment {Node1, point2}{Node2,point1}
  • Create a new convex polygon using this line segment.
  • Check if a green node falls within this new convex polygon.
  • If it doesn't, use this convex polygon from now on.
  • Use a fitness function to determine whether the line segment is better or worse than the old line segment. An example could be: greatest distance between points.
  • Stop iterating for this point when the fitness function returns a worse value.

What you should now end up with is this:

Programmer art 3

This algorithm isn't perfect and still needs work, but it should give you a start.

P.S.: I spent over an hour on this problem, it was extremely interesting to solve!

|improve this answer
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.