Algorithme pour implémenter un outil de sélection au lasso?

Question

Je développe une application Mac OS X qui, dans le cadre de son interface utilisateur, affichera de nombreux éléments visuels dans sa vue principale qui peuvent être sélectionnés. Ces éléments peuvent être positionnés vraiment n'importe où dans la vue. L'interface utilisateur prendra en charge différentes manières de sélectionner les éléments: sélection rectangulaire du chapiteau, sélection elliptique du chapiteau et sélection du lasso «libre».

J'ai déjà une sélection rectangulaire et elliptique. L'algorithme est assez simple. un élément est considéré comme 'sélectionné' si la zone de l'élément intersecte la zone du rectangle/ellipse.

La sélection au lasso fonctionnera comme dans les applications modernes de manipulation d'images comme Photoshop; l'utilisateur peut cliquer et faire glisser un chemin qui se fermera et les éléments contenus dans le chemin tracé seront sélectionnés.

Cet algorithme sera probablement beaucoup plus complexe que la sélection rectangulaire/elliptique, puisque la forme de la sélection n'est pas restreinte. Je me demande si quelqu'un a de l'expérience dans l'écriture de quelque chose comme ceci, ou si vous pouvez me diriger dans la bonne direction quant au type de techniques de programmation nécessaires, et quelle est la manière la plus efficace dont cet algorithme peut fonctionner.

Merci d'avance.

Answer 1

La seule façon dont je peux penser est de traiter le contour du lasso comme un polygone. Vous pouvez ensuite utiliser n'importe quelle norme point-inside-polygon test pour vérifier les éléments à sélectionner.

Vous devrez prendre une décision sur ce que vous devez faire lorsque le polygone se croise (par exemple, figure 8). Lors de la construction du polygone, pour éviter d'avoir trop de points, vous pouvez peut-être sauter des points trop proches du point précédent (peut-être 3 pixels environ, selon votre application).

Answer 2

Vous cherchez un point dans un problème de polygone: http://en.wikipedia.org/wiki/Point_in_polygon Si vous pouvez garantir que le polygone est convexe (peu probable), l'algorithme devient plus simple.

Answer 3

Pour l'outil lasso à main levée, vous pouvez prendre cette solution très simple: Enregistrer tous les points de la bordure de sélection dans un dictionnaire. Avec x comme clé et (y1, y2) comme valeur, où y1 <= y2. Puis bouclez sur tous les x' et voyez s'il y a une entrée dans le dict. Si oui, tous les points, où x' = x et y >= y1 and y <= y2, sont dans la sélection. Peut ne pas être la meilleure solution, mais cela devrait fonctionner.