Algoritmo per implementare uno strumento di selezione lazo?

Question

Sto sviluppando un'applicazione per Mac OS X che, come parte della sua interfaccia utente, mostrerà molti elementi visivi nella sua vista principale che può essere selezionata. Questi elementi possono essere posizionati davvero ovunque all'interno della vista. L'interfaccia utente supporterà vari modi di selezionare gli elementi: selezione di selezione rettangolare, selezione di selezione ellittica e selezione lasso 'libera'.

Ho già selezionato la selezione di selezione rettangolare ed ellittica. L'algoritmo è piuttosto semplice; un elemento è considerato 'selezionato' se l'area dell'elemento si interseca con l'area del rettangolo/ellisse.

La selezione del lazo funzionerà esattamente come nelle moderne applicazioni di manipolazione delle immagini come Photoshop; l'utente può fare clic e trascinare un tracciato che si chiuderà e verranno selezionati gli elementi contenuti nel percorso disegnato.

Questo algoritmo sarà probabilmente molto più complesso della selezione rettangolare/ellittica, poiché la forma della selezione è illimitata. Mi chiedo se qualcuno abbia esperienza nello scrivere qualcosa del genere, o se riesci a indicarmi la giusta direzione su quale tipo di tecniche di programmazione siano necessarie, e qual è il modo più efficiente in cui questo algoritmo può funzionare.

Grazie in anticipo.

Answer 1

L'unico modo che posso pensare è di trattare il contorno del laccio come un poligono. Quindi è possibile utilizzare qualsiasi standard point-inside-polygon test per verificare quali elementi selezionare.

Dovrai decidere cosa fare quando il poligono si interseca (ad esempio figura-8).

Quando si costruisce il poligono, per evitare che ottenga troppi punti, è possibile saltare i punti troppo vicini al punto precedente (forse 3 pixel circa, a seconda dell'applicazione).

Answer 2

Stai osservando un punto nel problema del poligono: http://en.wikipedia.org/wiki/Point_in_polygon Se è possibile garantire che il poligono sia convesso (non probabile), l'algoritmo diventa più semplice.

Answer 3

Per lo strumento Lazo a mano libera si può prendere questa soluzione molto semplice: salvare tutti i punti del bordo di selezione in un dizionario. Con x come chiave e (y1, y2) come valore, dove y1 <= y2. Quindi esegui un ciclo su tutto il x' e verifica se è presente una voce nel dett. In tal caso, tutti i punti, dove x' = x e y >= y1 and y <= y2, sono nella selezione.

non può essere la soluzione migliore, ma dovrebbe funzionare.