javascript - Detectando forma irregular

html5-canvas quadtree

Question

A la luz de esta pregunta Detectando las coordenadas del mouse con precisión , he aprendido bastante en los últimos días. Estos son los elementos que elegí como mejores recursos de aprendizaje sobre este tema:

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/

El código en (3) funciona en JSFiddle pero se rompe en esta sección en mi entorno de prueba (VS2012):

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

con el mensaje Quadtree no está definido en IE. FF y Chrome simplemente lo pasan por alto y muestran una página vacía. No pude resolverlo. Pregunta 1: ¿Alguien puede ayudar con eso?

Mi pregunta principal: tengo una región (parcelas de tierra como un mapa) con aproximadamente 1500 paquetes dibujados en html5, no en imágenes jpg o png. Son muchas líneas de código para completar eso, pero la representación es excelente, así que lo mantengo de esa manera. Pretendo tener un evento mouseover dime en qué paquete estoy parado cuando el mouse se detiene. Como verá en la pregunta anterior, mis intentos anteriores no fueron impresionantes. Basado en el aprendizaje que he estado haciendo, y gracias a las respuestas / comentarios de Ken J, me gustaría ir con este nuevo enfoque de dividir mi lienzo en, por ejemplo, 15 quads de 100 objetos cada uno. Sin embargo, me gustaría obtener alguna guía antes de tomar otra inmersión salvaje de la manera incorrecta.

Pregunta 2: ¿Debería cortarlo en la creación o debería cortarlo cuando el mouse está sobre una región, es decir, arrastrar el mouse? Esto último me suena mejor, pero creo que puedo seguir con algunos consejos y, si es posible, un código de inicio. El concepto de quadtree es completamente nuevo para mí. Gracias.

Answer 1

Dado que tu área de sorteo es bien conocida, no veo ninguna ventaja en un QuadTree sobre una función hash espacial. Esta función te dará un entero de un punto (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));
}

una vez que construiste eso, hash todas tus parcelas dentro de una matriz:

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]) };

ahora si tiene una posición de mouse, puede recuperar todas las parcelas en el mismo bloque con:

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

Answer 2

Le daré algunos consejos además de lo que otros han dicho.

... tener un evento mouseover decirme en qué paquete estoy parado ...

De sus otros mensajes concluyo que las parcelas tendrán formas irregulares. En general, los cuadrantes funcionan con rectángulos, por lo que debe calcular el rectángulo delimitador alrededor de la forma del paquete e insertar ese rectángulo en el árbol cuadriculado. Luego, cuando desee determinar si el mouse está sobre un paquete, consultará el árbol cuádruple que le proporcionará un conjunto de paquetes que podrían estar debajo del mouse, pero deberá hacer un control más preciso por su cuenta. para ver si realmente es así

... cuando el mouse se detiene.

De tus otras preguntas, vi que intentas detectar cuando el mouse se "detuvo". Tal vez deberías verlo de esta manera: el cursor del mouse nunca se mueve, se está teletransportando alrededor de la pantalla desde el punto anterior al siguiente. Siempre se detiene, nunca se mueve. Esto puede parecer un poco filosófico, pero mantendrá su código más simple. Definitivamente debería ser capaz de lograr lo que pretendía sin ningún control de setTimeout.

... cortando mi lienzo en, digamos, 15 quads de 100 objetos cada uno.
... ¿Debería cortarlo en la creación o debería rebanar cuando el mouse está sobre una región?

No hará (y no puede) cortar, la implementación de quadtree lo hace automáticamente (ese es su propósito) cuando inserta o quita elementos de él (tenga en cuenta que mover el elemento en realidad lo está quitando y luego volver a insertarlo).

No analicé la implementación de quadtree que está utilizando, pero aquí hay dos implementaciones de quadtree MX-CIF en caso de que no funcionen para usted:

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

El problema en la pregunta 1 probablemente sucede porque la página jsfiddle (http) está intentando acceder a quadtree.js que está en https

Answer 3

No puedo ayudar con la pregunta 1.

Definitivamente debe construir el árbol lo antes posible, dado que el objetivo es que la página responda lo más rápido posible una vez que el usuario haga clic en algún lugar.

Mantenga el árbol todo el tiempo que el usuario interactúe con el área 2d. La actualización de un árbol cuádruple no debería ser demasiado difícil, por lo que incluso si el área cambia de contenido, debería poder reutilizar el árbol existente (simplemente actualícelo).