Время поиска ближайшего соседа с помощью d3 voronoi - PullRequest
Новая
       23

Время поиска ближайшего соседа с помощью d3 voronoi

0 голосов
/ 06 января 2019

Какова сложность времени выполнения метода d3.voronoi.find?

Здесь https://visionscarto.net/the-state-of-d3-voronoi, написано, что его необработанная скорость равна O (sqrt (n)), но что является доказательством этого?

Кроме того, есть ли способ найти ближайшего соседа, просто используя вычисленную диаграмму Вороного за O (logn) времени?

1 Ответ

0 голосов
/ 06 января 2019

Как видите, следующий код - это find функция, о которой говорится: 

find: function(x, y, radius) {
    var that = this, i0, i1 = that._found || 0, n = that.cells.length, cell;

    // Use the previously-found cell, or start with an arbitrary one.
    while (!(cell = that.cells[i1])) if (++i1 >= n) return null;
    var dx = x - cell.site[0], dy = y - cell.site[1], d2 = dx * dx + dy * dy;

    // Traverse the half-edges to find a closer cell, if any.
    do {
      cell = that.cells[i0 = i1], i1 = null;
      cell.halfedges.forEach(function(e) {
        var edge = that.edges[e], v = edge.left;
        if ((v === cell.site || !v) && !(v = edge.right)) return;
        var vx = x - v[0], vy = y - v[1], v2 = vx * vx + vy * vy;
        if (v2 < d2) d2 = v2, i1 = v.index;
      });
    } while (i1 !== null);

    that._found = i0;

    return radius == null || d2 <= radius * radius ? cell.site : null;
}

Зависит от указанного радиуса для поиска по точке данных. Любым образом, как вы можете видеть, он перебирает все пол ребра (следовательно, в худшем случае это может быть O (n)).

Так или иначе, найти ближайшего соседа в журнале (n) можно с помощью хорошей структуры данных. Вы можете увидеть этот ответ , чтобы узнать больше.

...