[C++]Riconoscimento di poligoni 2D

[Tommo]

Salve,
stiamo realizzando un piccolo gioco dove l'user può disegnare una forma a sua scelta per creare dei precisi oggetti... il programma quindi a partire da un array di punti 2D deve capire quale forma è stata disegnata e riferircelo, in modo da assegnargli il comportamento adatto.
Tuttavia non so proprio come fare

Inizialmente pensavo alla distanza punto-punto fra la forma disegnata e una forma reference, ma non è affatto preciso: la forma potrebbe essere comunque simile contenendo più punti e non sarebbero considerate le linee che li collegano.
Le forme sono particolarmente semplici, regolari e separate dal resto. Si va dal cerchio allo zigzag all'8... per questo vorrei proprio evitare i procedimenti complicati di cui abbonda Internet, come reti neurali e cell partitioning, anche per questioni di performance... il controllo andrebbe eseguito in real time su tutte le forme create...

Voi avete qualche idea? Grazie

EDIT: I poligoni cmq hanno un numero finito di segmenti compreso fra 3-4 e 100... quindi non è una linea continua.

[banryu79]

Originariamente inviato da Tommo

Inizialmente pensavo alla distanza punto-punto fra la forma disegnata e una forma reference, ma non è affatto preciso: la forma potrebbe essere comunque simile contenendo più punti e non sarebbero considerate le linee che li collegano.

Allora potreste usare come discriminante non la distanza punto-punto.

Prendete la lista di punti dell'utente, la considerate una lista di segmenti
e andate a valutare l'andamento degli angoli che si vengono a formare tra segmento e segmento.

Definendo per ogni forma "reference" il corretto pattern di attesi andamenti degli angoli potrebbe diventare possibile riconoscere le forme.

Sto usando la convenzione che il primo punto nella lista creata dall'utente corrisponde sempre al primo punto della forma "reference"
Ad esempio:

IL RETTANGOLO
variazione angoli: +90, +90, +90, +90


In questo modo se un utonto clicca varie volte invce che 4, con l'intento di generare un Rettangolo:



La "procedura di riconsocimento" capisce che la forma disegnata, tra quelle possibili, si avvicina di più al rettangolo perchè l'andamento degli angoli (come vedi alcune variazioni sono piccole ma ci sono 4 variazioni significative che superano una certa soglia e due segmenti vicini a 45° fanno il nostro spigolo a 90°) è, tra tutti quelli possibili e definiti in precedenza (per ogni forma che si vuole riconoscere) quello più simile al rettangolo.

Probabilmente l'osservazione dell'andamento degli angoli non basta, potrebbe essere utile affiancarlo all'osservazione di altri fattori, come appunto la distanza tra i punti, magari l'andamento di DeltaX e DeltaY tra i segmenti e altro ancora.

Dipende da quali e quante forme bisogna poter riconoscere e quanto tra loro queste forme sono "differenti" (più sono differenti e più è facile riconoscerle, meno lo sono e più la faccenda diventa complessa).

Cmq delle cose che vi possono servire sono delle buone conoscenze geometriche e trigonometriche di base.

Ad esempio sapere che la somma degli angoli interni di un poligono fa sempre 360°; che osservando l'andamento degli angoli interni di un poligono, se questi continuano a variare sempre con lo stesso segno significa che il poligono è convesso, altrimenti no; eccetera...

[k0nt3]

beh non è una cosa semplice, quindi non avrà una soluzione semplice. ho trovato questo articolo http://citeseer.ist.psu.edu/rd/0%2C1...f-d-shapes.pdf dacci un'occhiata.

[Tommo]

Grazie delle risposte

Il metodo di banryu sembra il più sensato, in quanto è vero che a me interessano i rapporti fra gli angoli.
Invece il paper penso sia fondamentalmente sbagliato perchè tenta di deformare la forma iniziale e poi misura un fattore di uguaglianza basandosi sulla differenza di lunghezze totali delle forme prima e dopo.
Il che è una gran ca**ta senza offesa, basta fare due forme diverse con lo stesso esatto perimetro e quello le considera uguali, qualunque esse siano...

cmq ho trovato un interessante metodo che semplifica significativamente quello di banryu e lo generalizza:
http://www.bytearray.org/?p=91
l'unica cosa che mi rende perplesso è la Distanza di Levenshtein che sembra un algoritmo molto pesante...

[k0nt3]

Originariamente inviato da Tommo

Grazie delle risposte

Il metodo di banryu sembra il più sensato, in quanto è vero che a me interessano i rapporti fra gli angoli.
Invece il paper penso sia fondamentalmente sbagliato perchè tenta di deformare la forma iniziale e poi misura un fattore di uguaglianza basandosi sulla differenza di lunghezze totali delle forme prima e dopo.
Il che è una gran ca**ta senza offesa, basta fare due forme diverse con lo stesso esatto perimetro e quello le considera uguali, qualunque esse siano...

mi sa che non l'hai capito bene il metodo del paper

[Tommo]

Può essere benissimo