handleOverweighted1 sometimes gets stuck in an infinite loop

[kornysietsma]

I don't fully understand what this function does! But I found while processing large trees, sometimes this function loops forever.

For a test case, I logged the following mapPoints data after 10,000 iterations:

[
  {
    index: 0,
    targetedArea: 6.63625453479814,
    data: {
      index: 0,
      weight: 15,
      initialPosition: [Array],
      initialWeight: 1.253514745461871,
      originalData: [Object]
    },
    x: 605.9975186232019,
    y: 328.2152273626913,
    weight: 4318.240094720243
  },
  {
    index: 1,
    targetedArea: 0.4424169689865427,
    data: {
      index: 1,
      weight: 1,
      initialPosition: [Array],
      initialWeight: 1.253514745461871,
      originalData: [Object]
    },
    x: 607.1700362606578,
    y: 329.4272560895722,
    weight: 4320.083905965173
  },
  {
    index: 2,
    targetedArea: 0.4424169689865427,
    data: {
      index: 2,
      weight: 1,
      initialPosition: [Array],
      initialWeight: 1.253514745461871,
      originalData: [Object]
    },
    x: 607.3920808696175,
    y: 329.9778254838309,
    weight: 4320.73147549891
  }
]

It seems to be endlessly increasing the weights without stopping.

Note if I switch to handleOverweightedVariant = 0 I don't have this problem (but I'm not sure what the implications of the two algorithms are)

[Kcnarf]

I finally get the issue you're facing with this code

const data = [
        {
          initialWeight: 1,
          initialPos: [0, 0],
        },
        {
          initialWeight: 4,
          initialPos: [0.43038567576932785, 0.5019115451839844],
        },
      ],
      initialPositioner = function (d) {
        return d.initialPos;
      },
      initialWeighter = function (d) {
        return d.initialWeight;
      },
      voronoiMapSimulation = d3VoronoiMap
        .voronoiMapSimulation(data)
        .initialPosition(initialPositioner)
        .initialWeight(initialWeighter)
        .stop();

    let res = voronoiMapSimulation.state();

As you mentioned, weights are indefinitely increasing.

The handleOverweighted1 has a while loop, where the purpose of one iteration is to increase 1 site's weight at a time in order to make it heavy enough (cf. 'P.S.' below). But the increase is too big for very close sites, so that the next iteration increases the other site ... in an infinite manner.
I suspect this is what is going on with your index: 1 and index: 2 data.

The increase of the weights is at least equal to epsilon. The problem is that epsilon is set to 1, which is NOT epsilon-esque at all !
Setting epsilon to its expected value 1E-10 (which is the value used in the underlying d3-weigthed-voronoi package) resolves the issue.

P.S.:
FYI, handleOverweigthedX functions are used when a site no longer produces any cell. This situation is not exceptional, and arises when surrounding sites have heavy weights. handleOverweighted0 tries to lower the weights of the surrounding sites so that the site which initially did not produce any cell will now produces one. On the other hnad, handleOverweighted1 tries to increase the weight of the site that didn't produce any cell.