Elément point map pour l'élément de canvas html5, besoin d'algorithme

Question

Je travaille actuellement sur une implémentation de canvas pur html 5 de la "sphère cloud cloud", que beaucoup d'entre vous ont sans aucun doute vu comme un objet flash dans certaines pages. Les balises sont bien dessinées et les performances sont satisfaisantes, mais il y a une chose dans l'élément canevas qui casse cette idée: vous ne pouvez pas identifier les objets que vous avez dessinés sur une toile, car c'est juste une simple "image" plate ..

Ce que je dois faire dans ce cas est d'attraper l'événement click, et essayer de "deviner" quel élément a été cliqué. Je dois donc avoir une sorte de matrice, qui stocke un lien vers un objet tag pour chaque pixel sur la toile, ET je dois mettre à jour cette matrice à chaque redessin. Maintenant, cela semble incroyablement inefficace, et avant même que je commence à essayer de mettre en œuvre cela, je veux demander à la communauté - y a-t-il un algorithme «bien connu» qui m'aiderait dans ce cas? Ou peut-être que je manque juste quelque chose, et la réponse est juste derrière le coin? :)

Answer 1

Ceci est appelé le point location problem, et c'est l'un des sujets de base en géométrie de calcul. Il y a beaucoup de méthodes que vous pourriez utiliser qui seraient beaucoup plus rapides que l'approche que vous envisagez, mais les détails dépendent de ce que vous voulez accomplir exactement.

Par exemple, chaque chaîne de texte est contenue dans un cadre de sélection. Voulez-vous juste tester si l'utilisateur a cliqué quelque part dans cette boîte? Ensuite, stockez simplement les coordonnées minimum et maximum de chaque chaîne rendue, et testez le point par rapport à chaque boîte englobante pour voir si elle est contenue dans cette plage. Si vous avez un grand nombre de points à tester, vous pouvez créer un nombre illimité de structures de données pour l'accélérer (par exemple, R-trees), mais pour un seul point, le coût de construction d'une telle structure ne vaut probablement pas la peine.

Si vous vous souciez de savoir si le point se situe réellement dans la zone opaque des caractères traits, le problème est légèrement plus délicat. Une solution consisterait à utiliser l'approche de la boîte englobante pour éliminer d'abord la plupart des possibilités, puis restituer les chaînes restantes une à la fois dans un tampon hors écran, en vérifiant chaque fois si le point cible a été touché.