Обнаружение нерегулярных фигур

Question

В начале этого вопроса Detecting mouse coordinates with precision, я узнал немало за последние несколько дней. Вот то, что я выбрал в качестве лучших учебных ресурсов по этой теме:

1. http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/
2. http://www.gamedev.net/page/resources/_/technical/graphics-programming-and-theory/quadtrees-r1303
3. http://jsfiddle.net/2dchA/2/

Код в (3) работает в JSFiddle, но перерывы в этом разделе в моей испытательная среда (VS2012):

var myTree = new Quadtree({ 
    x: 0, 
    y: 0, 
    width: 400, 
    height: 300 
}); 

с сообщением Quadtree is und в IE. FF & Chrome просто замаскирует его и отображает пустую страницу. Я не мог разобраться. Вопрос 1. Может ли кто-нибудь помочь в этом?

Мой главный вопрос: У меня есть регион (земельные участки, подобные карте) с примерно 1500 посылок, нарисованных в html5, а не в формате jpg или png. Это много строк кода, чтобы завершить это, но рендеринг велик, поэтому я держу его таким образом. Я намерен иметь событие mouseover, скажите мне, какой посылкой я стою, когда мышь останавливается. Как вы увидите в предыдущем вопросе, мои предыдущие попытки не впечатляют. Основываясь на обучении, которое я делал, и благодаря ответам/комментариям Кен Дж, я хотел бы пойти с этим новым подходом нарезать свой холст, чтобы сказать 15 квадратов по 100 объектов каждый. Тем не менее, я бы хотел, чтобы некоторые рекомендации, прежде чем я принимаю другое дикое погружение неправильно.

Вопрос 2: Должен ли я нарезать его при создании или если нарезка произойдет, когда мышь находится над областью, т. Е. Пройдем мышь? Последний звучит лучше для меня, но я думаю, что смогу сделать некоторые советы и, если возможно, начать код. Концепция quadtree для меня совершенно новая. Благодарю.

Answer 1

не может помочь с вопросом 1.

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

Храните дерево до тех пор, пока пользователь взаимодействует с областью 2d. Обновление квадрового дерева не должно быть слишком сложным, поэтому даже если область изменяет содержимое, вы должны иметь возможность повторно использовать существующее дерево (просто обновите его).

Answer 2

Учитывая тот факт, что ваша область рисования хорошо известна, я не вижу преимуществ в QuadTree над пространственной хэш-функцией. Эта функция даст вам целое число из (x, y) точки.

var blocWidth = 20; 
var blocHeight = 20; 
var blocsPerLine = (0 | (worldWidth/blocWidth)) + 1 ; 
function hashPoint(x,y) { 
    return (0 | (x/blocWidth)) + blocsPerLine*(0|(y/blocHeight)); 
} 

когда вы построили, что хэш все ваши посылки в пределах массива:

parcelHash = []; 

function addHash(i,p) { 
    if (!parcelHash[i]) { parcelHash[i]=[ p ]; return; } 
    if (parcelHash[i].indexOf(p) != -1) return; 
    parcelHash[i].push(p); 
} 

function hashParcel (p) { 
    var thisHash = hashPoint(p.x,p.y); // upper left 
    addHash(thisHash, p); 
    thisHash = hashPoint(p.x+width, p.y); // upper right 
    addHash(thisHash, p); 
    thisHash = hashPoint(p.x, p.y+p.height); // lower left 
    addHash(thisHash, p); 
    thisHash = hashPoint(p.x+width, p.y+p.height); // lower right 
    addHash(thisHash, p);   
}; 

for (var i=0; i<allParcels.length; i++) { hashParcel(allParcels[i]) }; 

теперь, если у вас есть положение мыши, вы можете получить все участки в одном блоке с:

function getParcels(x,y) { 
     var thisHash = hashPoint(x,y); 
     return parcelHash[thisHash]; 
    } 

Answer 3

Я просто дам вам несколько советов в дополнение к тому, что говорили другие.

... есть событие с указателем мыши, скажите мне, какая посылка я стою на ...

Из других сообщений я делаю вывод, что участки будут иметь неправильные формы. Quadtrees в целом работают с прямоугольниками, поэтому вам нужно будет вычислить ограничивающий прямоугольник вокруг формы посылки и вставить этот прямоугольник в квадранте. Затем, когда вы хотите определить, находится ли мышь над посылкой, вы будете запрашивать квадрант, который даст вам набор посылок, которые могут быть у под мышкой, но вам нужно будет сделать более точную проверку чтобы убедиться, что это действительно так.

... когда мышь останавливается.

Из ваших других вопросов я увидел, что вы пытаетесь обнаружить, когда мышь «остановилась». Возможно, вам стоит взглянуть на это так: курсор мыши никогда не перемещается, это телепортирует вокруг экрана с предыдущего пункта на следующий. Он всегда останавливается, никогда не двигается. Это может показаться немного философским, но это упростит ваш код. Вы наверняка сможете достичь того, что вы планировали, без каких-либо проверок setTimeout.

... нарезать мой холст, чтобы сказать 15 квадратов по 100 объектов каждый.
... Должен ли я разрезать его на создание или если разрезание происходит, когда мышь находится над областью

Вы не будете (и не может) сделать нарезка, реализация квадрантов делает это автоматически (это его цель), когда вы вставляете или удаляете из него элементы (обратите внимание, что перемещение элемента фактически удаляется, а затем снова вставляется).

Я не смотрел в реализации квадрадерево, который вы используете, но здесь две реализации MX-СИФ квадрадерево в случае, если один не работает для вас:

• https://github.com/pdehn/jsQuad
• https://github.com/bjornharrtell/jsts/tree/master/src/jsts/index/quadtree

проблема в вопросе 1, вероятно, происходит потому, что jsfiddle (HTTP) страница пытается quadtree.js доступа, который находится на HTTPS