Skip to content

Euclidean Distances on Hexagonal Grid #130

Open
@MattWenham

Description

@MattWenham

I believe there is an issue with the way the routines euclideanDistanceOnHexagonalPlanarMap and euclideanDistanceOnHexagonalToroidMap are calculating the Euclidean distance between cells on a hexagonal grid.

If we consider the standard indexing system for a hexagonal grid to be as Kohonen intended:

image

then the Euclidean distance between a node and any of its six neighbours is 1 by definition.

If calculating the distance between e.g. nodes (1,1) and (2,2) using euclideanDistanceOnHexagonalPlanarMap, as far as I can see, the result would be approximately 1.11803:

x1 = 1
y1 = 1
x2 = 2
y2 = 2
xdist = 1
ydist = 1
xdist += -0.5 /* so now xdist = 0.5 */
return sqrt(float(0.5 * 0.5 + 1 * 1)) /* Return value is 1.11803... */

This is of little consequence - though still some - when using a 'gaussian' neighbourhood. However, when using 'bubble', the conditional if (distance <= radius) { in getWeight will e.g. fail to connect a node with four of its six neighbours when 'radius' is 1.

The simplest fix I can see for this is to change the return expression to

return sqrt(float(xdist * xdist + ydist * ydist * 0.75));

The factor of 0.75 is the square of cos(30), which is the height of an equilateral triangle of base 1. Cos(30) is therefore the factor by which ydist needs to be scaled to correct the Euclidean distance calculation. This fix should also be applied to euclideanDistanceOnHexagonalToroidMap.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions