Unexpected results

[pedro]

Hi folks!

Not sure I'm doing something wrong, but getting a somewhat unexpected pole of inaccessibility for a U-like polygon. The red marker is what I got from polylabel():

I tried changing the precision but didn't notice any difference. On version 1.0.2 of the js library.

Polygon in GeoJSON below:

{
  "type":"Polygon",
  "coordinates":[
    [
      [
        -122.4018194,
        37.7909722
      ],
      [
        -122.400845,
        37.7910899
      ],
      [
        -122.4007716,
        37.7907104
      ],
      [
        -122.4009996,
        37.7906828
      ],
      [
        -122.4010399,
        37.7908913
      ],
      [
        -122.4011183,
        37.7908818
      ],
      [
        -122.4011134,
        37.7908568
      ],
      [
        -122.4011346,
        37.7908122
      ],
      [
        -122.4011967,
        37.7908047
      ],
      [
        -122.4012382,
        37.7908417
      ],
      [
        -122.401243,
        37.7908668
      ],
      [
        -122.4015202,
        37.7908333
      ],
      [
        -122.4014781,
        37.7906159
      ],
      [
        -122.4017442,
        37.7905837
      ],
      [
        -122.4018194,
        37.7909722
      ]
    ]
  ]
}

Any thoughts/feedback appreciated!

Thanks,

[mourner]

What precision value do you use?

[mourner]

It's likely that it's too big. Try using something like 0.000001. I'll reopen if this doesn't help.

[pedro]

Odd, with 0.000001 it went a bit further left:

Code:

const polylabel = require('polylabel');
const polygon = [[
  [-122.4018194, 37.7909722],
  [-122.4017442, 37.7905837],
  [-122.4014781, 37.7906159],
  [-122.4015202, 37.7908333],
  [-122.401243, 37.7908668],
  [-122.4012382, 37.7908417],
  [-122.4011967, 37.7908047],
  [-122.4011346, 37.7908122],
  [-122.4011134, 37.7908568],
  [-122.4011183, 37.7908818],
  [-122.4010399, 37.7908913],
  [-122.4009996, 37.7906828],
  [-122.4007716, 37.7907104],
  [-122.400845, 37.7910899],
  [-122.4018194, 37.7909722]
]];
polylabel(polygon, 0.000001);

Debugging it a bit 🤔

width= 0.0010477999999949361
height= 0.000506200000003787
h= 0.0002531000000018935
found best 0.000046232672421291344 after 3 probes
found best 0.00011096979515426172 after 11 probes
found best 0.00011874452457926416 after 27 probes
found best 0.0001235614097284447 after 43 probes
found best 0.00013126728972781408 after 67 probes
found best 0.00013359122621284432 after 91 probes
found best 0.00013571096367370105 after 119 probes
found best 0.0001364365261735361 after 139 probes
found best 0.0001372995011786261 after 155 probes
aborting loop
max= 0.0001382975787384559
best d= 0.0001372995011786261
precision= 0.000001
num probes: 187
best distance: 0.0001372995011786261
[ -122.40165626914062, 37.79085360742187 ]

Must be missing something but surprised the distance is increasing, gotta read the paper.

Also, unrelated, but on this line when there's no chance of a better solution, shouldn't it break the loop instead of going through everything that is still enqueued?

[pedro]

Ah! Nevermind about that last question, I see it still needs to see if there's a better cell in the queue / just doesn't want to add more split cells to look into.

[mourner]

@pedro the result in the screenshot is the most distant point inside a polygon, so it's the expected result. There's some discussion about changing the algorithm in #33 so that it leans more in the direction of the centroid, but it's another issue.

[pedro]

ooh, got it! Thank you!