d3.packSiblings overlaps, hangs.

[mbostock]

Reference: https://beta.observablehq.com/@jediwarpraptor/market-capitalization-by-segment

data = [
  {name: "a", value: 19492797890},
  {name: "b", value: 4196176},
  {name: "c", value: 14565064},
  {name: "d", value: 1243655681},
  {name: "e", value: 9756222871},
  {name: "f", value: 85483881441},
  {name: "g", value: 206472827707}
]

Dividing the data by ten should produce the same result, but apparently avoids the overlap:

data = [
  {name: "a", value: 1949279789.0},
  {name: "b", value: 419617.6},
  {name: "c", value: 1456506.4},
  {name: "d", value: 124365568.1},
  {name: "e", value: 975622287.1},
  {name: "f", value: 8548388144.1},
  {name: "g", value: 20647282770.7}
]

Dividing the data by two results in an infinite loop!

data = [
  {name: "a", value: 9746398945},
  {name: "b", value: 2098088},
  {name: "c", value: 7282532},
  {name: "d", value: 621827840.5},
  {name: "e", value: 4878111435.5},
  {name: "f", value: 42741940720.5},
  {name: "g", value: 103236413853.5}
]

Here’s a slightly reduced overlap case:

data = [
  {name: "a", value: 4873199472.5},
  {name: "b", value: 1049044},
  {name: "d", value: 310913920.25},
  {name: "e", value: 2439055717.75},
  {name: "f", value: 21370970360.25}
]

[mbostock]

Related #74.

[robinhouston]

I’m not entirely sure I know what I’m doing here, so I’m sorry if this is completely irrelevant.

Anyway, if I run this:

const data = [
  {name: "a", value: 19492797890},
  {name: "b", value: 4196176},
  {name: "c", value: 14565064},
  {name: "d", value: 1243655681},
  {name: "e", value: 9756222871},
  {name: "f", value: 85483881441},
  {name: "g", value: 206472827707}
];

const packed = d3.packSiblings(data.map(d => ({
  name: d.name,
  r: Math.sqrt(d.value)
})));

then the resulting e circle overlaps with b, c and d.

If I instrument the packSiblings method as follows:

--- a/src/pack/siblings.js
+++ b/src/pack/siblings.js
@@ -88,6 +88,7 @@ export function packEnclose(circles) {
     } while (j !== k.next);
 
     // Success! Insert the new circle c between a and b.
+    console.log(`Inserting ${c._.name} between ${a._.name} and ${b._.name}`);
     c.previous = a, c.next = b, a.next = b.previous = b = c;
 
     // Compute the new closest circle pair to the centroid.

then it says:

Inserting d between a and b
Inserting e between a and a
Inserting f between a and e
Inserting g between e and a

I am rather suspicious of the “between a and a” here!

[robinhouston]

The same thing happens with the data cut down to just these four:

    {name: "a", value: 19492797890},
    {name: "b", value: 4196176},
    {name: "d", value: 1243655681},
    {name: "e", value: 9756222871}

[robinhouston]

(I’ve deleted my previous comment, which was nonsense.)

With a bit more instrumentation, the failing run looks like this:

Placing d tangent to b and a
Placing e tangent to a and b
a = a, b = b, j = d, k = d
Intersection between d and e
Placing e tangent to a and d
a = a, b = d, j = a, k = d
Intersection between a and e
Placing e tangent to a and a
a = a, b = a, j = a, k = a
Inserting e between a and a

The Intersection between a and e ought to be impossible, since e was placed tangent to a.

So the following example illustrates the essential problem, with place and intersects defined as in siblings.js.

const a = { x: -2048.456980265878, y: 0, r: 139616.61036567247 },
      d = { x: 171813.78765611292, y: 18859.304384921452, r: 35265.50270448445 },
      e = { r: 98773.5939965738 };

place(a, d, e);
console.log(intersects(a, e)); // true

Nasty. I’m not sure what the answer is, other than making the intersects test more relaxed. Perhaps the error threshold should be proportional rather than constant (or both), e.g.:

  return dr * dr * (1 - 1e-9) - 1e-6 > dx * dx + dy * dy;

[robinhouston]

See discussion on #111. I’ve updated PR #112 with a (hopefully) improved place() function that seems to avoid this particular problem. It obviously needs more testing to make sure it doesn’t cause other problems.