Взаимодействие с пятью миллионами точек на экране

Question

Нам нужно отображать 5 миллионов точек (или очень простых графических объектов) на экране одновременно, и мы хотим взаимодействовать с каждой из точек (например, изменить их цвета или перетащить их).
Для достижения этого мы обычно запускаем цикл for через 5 миллионов элементов в наихудшем случае O (N) для доступа и изменения состояний точки в соответствии с координатами мыши (x, y). Из-за огромного количества объектов этот подход вызывает много накладных расходов (мы должны запускать for-loop из пяти миллионов, когда пользователь выбирает точку). Я уже тестировал этот подход, но сделать интерактивный инструмент практически невозможно. Есть ли способ быстро и эффективно получить доступ к точкам, не запуская миллион for-loop и вызывая эту проблему с производительностью?

Answer 1

Вы действительно не дали много деталей

Эти вопросы быстро приходят на ум:

• Являются ли точки одного размера?
• Являются ли точки равномерно распределены на холсте?
• Если одна точка выбрана, то только одна точка перекрашивается или перемещается?
• Почему вы нарушаете правила визуализации данных, подавляя пользователя? :)

При этом отсутствие специфичности в виду ...

... Разделяй и властвуй:

• Разделите ваш дот массив на несколько частей.
• Разделите свои точки на несколько накладываемых холстов.

Разделите точечную массив на несколько частей

Это позволит вам изучить гораздо меньше элементов массива при поиске 1 вам нужно.

Создайте контейнерный объект с элементами 1980 года, представляющими координаты «x» 1980 года на экране.

var container={}; 

for(var x=1;x<=1980;x++){ 
    container[x]=[]; 
} 

Каждый элемент контейнера представляет собой массив точечных объектов с центрами точек на этой координате x.

У каждого объекта-точки достаточно информации, чтобы найти и перерисовать.

Точка в точке х-координата == 125 может быть определена следующим образом:

{x:125,y:100,r:2,color:"red",canvas:1}; 

Если вы хотите добавить точку, нажмите объект точки на соответствующий элемент «х» объект контейнера.

// add a dot with x screen coordinate == 952 
container[952].push({x:952,y:100,r:2,color:"red",canvas:1}); 

Точки могут быть сделаны на основе точечных объектов:

function drawDot(dot,context){ 
    context.beginPath(); 
    context.fillStyle=dot.color; 
    context.arc(dot.x,dot.y,dot.r,0,PI2,false); 
    context.closePath(); 
    context.fill(); 
} 

Когда пользователь выбирает точку, вы можете найти его быстро, потянув несколько контейнеров элементы вокруг X, где пользователь нажал:

function getDotsNearX(x,radius){ 

    // pull arrays from "x" plus/minus "radius" 
    var dotArrays=[] 
    for(var i=x-radius;i<=x+radius;i++){ 
     dotArrays.push(container[i]); 
    } 
    return(dotArray); 
} 

Теперь вы можете обрабатывать точки в этих целевых массивах, а не все 5 миллионов элементов массива.

Когда пользователь перемещает точку в новую позицию, просто вытащите объект точки из текущего элемента контейнера и вставьте его в соответствующий новый элемент контейнера «x».

Разделите свои точки на несколько накладываниях полотен

Чтобы улучшить производительность рисования, вы хотите проплачивать свои точки по несколько холсту накладываемого друг на друг.

Элемент dot содержит свойство canvas для определения, на каком холсте будет отображаться эта точка.

Answer 2

Вы уже ознакомились с каркасом KineticJS? Существует very impressive stress-test с точно такой же функцией перетаскивания, которую вы ищете. Если вы используете KineticJS, вы можете получить доступ каждую точку со следующей eventlistener, и, конечно, изменить его цвет, размер и т.п .:

 stage.on('mousedown', function(evt) { 
     var circle = evt.targetNode; 
     });