Combine Arbitrary number of polygons together

Question

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

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?

Answer 1

For each hex you have a list of 6 vertices. Sort the list, if necessary, so that the the vertices are ordered in counter-clockwise order (that's the mathematical convention).

Now you have a set of polygons (initially hexagons). The idea is to combine polygons until there is only one (or as few as can be).

Pick an edge of a polygon, and look for that same edge (i.e. that same pair of vertices) among the other polygons. If there are two instances, combine the two polygons at that edge, e.g. (a, b, c, d, e, f) + (g, h, d, c, i, j) => (a, b, c, i, j, g, h, d, e, f). (If the two vertices are in the same order in both polygons, or if there are three or more instances of the edge, report an error and abort.) Iterate through all edges. If the hexes really formed a contiguous group, there will be only one polygon left.

The polygon may have duplicated edges. If an edge occurs more than once, eliminate it by splitting the list in two, e.g. (a, b, c, d, b, a, e, f, g) => (b, c, d) + (a, e, f, g). Or if the the edges are adjacent, remove them: (a, b, c, b, d, e) => (a, b, d, e). Or if that list has only that edge, remove the list: (a,b) => nothing.

Once you've eliminated duplicate edges, there'll be one list for the counter-clockwise outer edge of the polygon, and perhaps one or more lists for the clockwise interior edges of holes.

Answer 2

without keeping track of the coordinate pairs that make up the lines, it would be impossible to determine the outer border of the shape

if you know the coordinate pairs that make up the lines, THEN

1. Create 2 lists, one of vertexs (list 1), one of the lines (list 2)
2. Remove all duplicate vertexes from the vertex list
3. Make a new list (list 3) of all the vertexes that have 3 lines attached to them
4. Using list 3, remove all the lines that have 2 vertexes from list 3 as their two coordinate pairs
5. It's time to traverse the shape, the list of lines remaining should form the shape you want just start with an arbitrary coordinate and then for each coordinate for all lines if (x1,y1) = current coordinate then add (x2,y2) to stack and remove that line from list break elseif (x2,y2) = current coordinate then add (x1,y1) to stack and remove that line from list break

Answer 3

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.