peterwittek / somoclu

Massively parallel self-organizing maps: accelerate training on multicore CPUs, GPUs, and clusters
https://peterwittek.github.io/somoclu/
MIT License
268 stars 70 forks source link

Euclidean Distances on Hexagonal Grid #130

Open MattWenham opened 6 years ago

MattWenham commented 6 years ago

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.

MattWenham commented 6 years ago

Pull Request created.

MattWenham commented 6 years ago

Thanks Peter. Is there any way I can incorporate this fix into the Python version before you do the next 'official' Python release?

peterwittek commented 6 years ago

Just rebuild it from git. I don't think there will be a new release this year. The code is very much in maintenance mode.