D3js обнаружение столкновения маркера карты

Question

Есть ли пример плавающего вокруг обнаружения столкновения, который позволяет избежать столкновения, манипулируя радиусом, а не координатами x, y? Я знаю примеры, которые Майк Босток и другие собрали вместе, но я не использую график силы, и мои точки географические и не могут управлять их координатами.

Моей наилучшей предпосылкой было бы начать с кругов радиуса 0, перебрать их и увеличить их отдельные радиусы, пока они не сталкиваются с другим кругом. Я думаю, что это создаст фантастическую визуализацию, но я не уверен, как эффективно определять, сталкивается ли один круг с другим.

---

JSBin моей карты с инлайн D3js (вкладке JavaScript просто держит 600KB GeoJSON набор данные): http://jsbin.com/tapuhefamu/1/edit?html,output

Обратите внимание, как маркеры перекрываются при увеличении, это не кажется большим дело в fiddle (просто увеличьте масштаб дальше, правильно?), но карта, с которой я работаю, имеет ~ 2000 контактов, сгруппированных только в нескольких округах, которые должны отображать информативный DIV при нажатии. Некоторые контакты практически полностью закрыты и не могут взаимодействовать из-за перекрытия.

Answer 1

Я что-то закодировал для вас. Обнаружение столкновения довольно просто, в основном вычислить расстояние между двумя центральными точками, и если расстояние меньше, чем два смещенных вместе радиуса, то они должны были столкнуться.

У меня были некоторые проблемы с jsbin, поэтому я включил его в сущность, которую вы можете просмотреть на http://bl.ocks.org/benlyall/6a81499abf7a0e2ad304

Интересных бит:

1. Добавить параметр radiusStep - используйте чтобы сбалансировать компромисс между количеством итераций и количеством возможных совпадений между узлами.

   radiusStep = 0.01, 
   

2. Удалить радиус масштабирования из обработчика масштабирования:

   zoom = d3.behavior.zoom().on("zoom",function() { 
        g.attr("transform","translate("+ d3.event.translate.join(",")+")scale("+d3.event.scale+")"); 
        //g.selectAll("circle") 
        //.attr("r", nodeRadius/d3.event.scale); 
        g.selectAll("path") 
         .style('stroke-width', countyBorderWidth/d3.event.scale) 
         .attr("d", path.projection(projection)); 
   }), 
   

3. Создать новую структуру, чтобы отслеживать, был ли узел столкнулась с другой, радиус, а также х и у позиции (предварительно вычислены с помощью проекции)

   nodes = nodeGeoData.map(function(n) { 
       var pos = projection(n); 
       return { 
        collided: false, 
        x: pos[0], 
        y: pos[1], 
        r: 0 
       }; 
   }); 
   

4. Две новых функций для работы с обнаружением столкновения и расширения радиуса ипа пока не обнаружено столкновение.

   function tick() { 
       nodes.forEach(collided); 
   
       nodes.forEach(function(n) { 
        if (!n.collided) { 
         n.r += radiusStep; 
         if (n.r > nodeRadius) { 
          n.r = nodeRadius; 
          n.collided = true; 
         } 
        } 
       }); 
   } 
   

   Эта функция tick первые вызовы сталкиваются на каждом узле, чтобы определить, если он столкнулся с какой-либо другой. Затем он увеличивает радиус на radiusStep любого узла, который не столкнулся. Если радиус становится больше, чем параметр nodeRadius, тогда он устанавливает радиус в это значение и отмечает его как столкнутый, чтобы остановить его увеличение.

   function collided(node, i) { 
       if (node.collided) return; 
   
       nodes.forEach(function(n, j) { 
        if (n !== node) { 
         var dx = node.x - n.x, dy = node.y - n.y, 
          l = Math.sqrt(dx*dx+dy*dy); 
   
         if (l < node.r + n.r) { 
          node.collided = true; 
          n.collided = true; 
         } 
        } 
       }); 
   } 
   

   столкнувшаяся функция проверяет каждый узел, чтобы увидеть, если столкнулись с каким-либо другим (кроме себя, по понятным причинам). Если он обнаруживает столкновение, то оба узла в сравнении помечены как столкнутые.Для определения фактического столкновения вычисляются разности по положению x и y, а затем с использованием Pythagoras вычисляется расстояние между ними. Если это расстояние меньше радиусов двух узлов, объединенных вместе, то происходит столкновение.

5. Функция drawMap обновляется, чтобы рассчитать радиусы перед рисованием узлов.

   while (nodes.filter(function(n) { return n.collided; }).length < nodes.length) { 
       tick(); 
   } 
   

   Это в основном только вызвать функцию tick, пока все узлы не будут помечены как столкновение.

6. drawNodes функция обновляется, чтобы использовать новую структуру nodes данных:

   function drawNodes(nodes) { 
       g.selectAll('circle').data(nodes).enter().append("circle") 
        .attr("cx", function (d) { return d.x; }) 
        .attr("cy", function (d) { return d.y; }) 
        .attr("r", function(d, i) { return d.r; }) 
        .attr("class", "map-marker"); 
   } 
   

   Изменения здесь просто ссылаться на x, y и r атрибуты каждого объекта узла, созданного ранее.

Хотя это работает, и, кажется, довольно эффективным, наивно и быстро увязнуть, так как сочетание функций tick и collided является O(n^2).