Search code examples
algorithmhexpolygonhexagonal-tiles

Combine Arbitrary number of polygons together

I have an arbitrary number of polygons (hexes in this case) that are arranged randomly, but they are all touching another hex.

enter image description here

Each individual hex has 6 x,y vertices. The vertex's are known for all the hexes.

Can anyone point me in the direction of an algorithm that will combine all the hexes into a single polygon? Essentially I'm just looking for a function that spits out an array of vertex locations that are ordered in a way that when drawing lines from one to the next, it forms the polygon.

This is my method so far:

  1. Create array of all the vertices for all the hexes.
  2. Determine the number of times a vertex occurs in the array
  3. If vertex is in the array 3+ times, delete the vertices from the array.
  4. If vertex is in the array 2 times, delete one of them.

The next step is tricky though. I'm using canvas to draw out these polygons, which essentially involves drawing a line from one vertex to the next. So the order of the vertices in the final array is important. It can't be sorted arbitrarily.

Also, I'm not looking for a "convex hull" algorithm, as that would not draw the polygon correctly.

Are there any functions out there that do something like this? Am I on the right track or is there a better more efficient way?

Solution

  • I would do something like this:

    1. List all the sides. A side is defined by two pairs of coordinates.
    2. If any side shows up more than once remove all instances of that side.
    3. Pick an arbitrary side, and from that side choose one of its points.
    4. Place that point in an array.
    5. Follow the current side and put the other point in the array.
    6. Delete the side you just followed.
    7. Then find the other side that has a point that is the same as the last point in the array. There will be only one such side. If there is none, you're done.
    8. Go back to step 5.

    You should now have an array of points that make up, in order, the shape you want.

    Just be aware that this won't handle holes. The shape must be defineable by a single path.