outline around group of hexagons

Question

I have a group of hexagons in my hexagonal grid, which I'd like outline with a border.

This is how it looks like so far:

desired output:

I have stored all the cotrner points of each hexagon from that group. I suppose these points can be used to calculate the border around the group later on.

[[{"x":123.39745962155612,"y":260},{"x":101.74682452694516,"y":272.5},{"x":80.0961894323342,"y":260},{"x":80.0961894323342,"y":235},{"x":101.74682452694516,"y":222.5},{"x":123.39745962155612,"y":235}],[{"x":145.0480947161671,"y":222.5},{"x":123.39745962155614,"y":235},{"x":101.74682452694518,"y":222.5},{"x":101.74682452694518,"y":197.5},{"x":123.39745962155614,"y":185},{"x":145.0480947161671,"y":197.5}],[{"x":166.69872981077808,"y":260},{"x":145.0480947161671,"y":272.5},{"x":123.39745962155612,"y":260},{"x":123.39745962155612,"y":235},{"x":145.0480947161671,"y":222.5},{"x":166.69872981077805,"y":235}],[{"x":188.34936490538905,"y":297.5},{"x":166.69872981077808,"y":310},{"x":145.0480947161671,"y":297.5},{"x":145.0480947161671,"y":272.5},{"x":166.69872981077808,"y":260},{"x":188.34936490538902,"y":272.5}],[{"x":188.34936490538905,"y":222.5},{"x":166.69872981077808,"y":235},{"x":145.0480947161671,"y":222.5},{"x":145.0480947161671,"y":197.5},{"x":166.69872981077808,"y":185},{"x":188.34936490538902,"y":197.5}],[{"x":210,"y":260},{"x":188.34936490538902,"y":272.5},{"x":166.69872981077805,"y":260},{"x":166.69872981077805,"y":235},{"x":188.34936490538902,"y":222.5},{"x":209.99999999999997,"y":235}],[{"x":231.65063509461098,"y":297.5},{"x":210,"y":310},{"x":188.34936490538902,"y":297.5},{"x":188.34936490538902,"y":272.5},{"x":210,"y":260},{"x":231.65063509461095,"y":272.5}]]

Also added a live example to see how the grid works so far.

And now I'm trying to figure out how exactly do I determine how the border will be generated.

Now how do I exactly generate the border? Should I just find the center of this group, and then find all the points with the greater distance, and then connect them?

As advised by someone in discussion below, I tried sorting the points by their [X,Y] coordinates and also removed all duplicate coordinates, but it turned into this disaster :/.

Or is there any other technique to achieve this?

Answer 1

Here's a simple algorithm:

1. For each hex H in your brown region, iterate over each of the 6 directions 0 ≤ dir < 6, and set D to be hex_neighbor(H, dir).
2. If D is green then draw a border between the two.

Caveat: this does not connect the border edges into a single polyline.

I have a live demo with an algorithm that works on any number of regions, as well as an extension to draw curved lines.

Answer 2

Thanks Amit, for sharing your knowledge with us. Your algorithm is way more efficient and faster. I have had to make very little amendments to make it work in my example above.

• First one, if the hex didn't have a neighbor on one of its direction , mark the direction with null.

• The second, take the neighbors with null value to consideration while generating edges.

Otherwise it was leaving gaps if the hex didn't have neighbor on one of their sides.

This a modified function that I'm using to draw the edges:

generateEdges: function( ctx ){
    var edges = [];
    var self = this;
    var neighbor = null;
    self.obs_arr.forEach( function( hex ){
        for( var dir = 0, nb_l = hex.neighbors.length; dir < nb_l; dir++ ){
            neighbor = hex.neighbors[dir];
            if(neighbor == null ||  hex.content != neighbor.content ){
                var p1 = self.point_add( hex.center, self.hex_corner_offset( dir ) );
                var p2 = self.point_add( hex.center, self.hex_corner_offset( (dir+1)%6 ) );
                edges.push( p1, p2 );
            }
        }
    });
    return edges;
},

It all now works perfectly . Thanks a lot Amit for all your help!