Newsgroup: it.comp.lang.c++
Titolo: Aiuto computer grafica

Ho bisogno di un aiuto su come si possa generare una superfice di triangoli
da una nuvola di punti sparsi.

da una nuvola di punti sparsi.
Se non ho capito male, vuoi ottenere un poligono (a proposito, sei in 2D  o in 3D? io
assumo che tu sia in 2D, ma il discorso non cambia granché) che racchiuda tutti i punti e
che sia totalmente composto da triangoli, giusto? Beh, allora basta un qualsiasi algoritmo
di triangolazione. Se poi il poligono deve avere caratteristiche particolari (es se deve
essere convesso e deve essere anche il minimo poligono che contiene tutti i punti), allora
un algoritmo di convex hull potrebbe fare al caso tuo. Prima di indicarti dei riferimenti
piů precisi, confermami che sono nella strada giusta con le mie assunzioni...
Ciao
Andrea

piů precisi, confermami che sono nella strada giusta con le mie
assunzioni...
Salve.
Potresti indicarmi un riferimento per l'algoritmo? Interessa moltissimo
anche a me.
Sai se il problema e' NP completo?
E nel caso di punti appartenenti ai vertici dell'ipercubo di R^n ci sono
scorciatoie computazionalmente valide?
Scusa per le troppe domande, e' un argomento che mi interessa.
Marco

Marco
In 2D ci sono un mucchio di algoritmi che risolvono il convex hull a seconda dello schema
di input/output che adotti (inserzione incrementale, selezione incrementale, plane-sweep,
divide & conquer etc.). Potresti trovare dei riferimenti on-line riguardo Insertion Hull,
Merge Hull, Quick Hull, oppure sull'algoritmo di Graham (Graham Scan Algorithm), su quello
di Jarvis (Jarvis March). Importanti, infine, anche gli algoritmi beneath-beyond e
gift-wrapping, specialmente per le loro estensioni al caso n-dimensionale.
Un altro criterio di valutazione è quello di stabilire se si vuole una creazione del
convex hull dinamica (diventa quindi un problema di real time da risolvere mediante l'uso
di algoritmi e di strutture dati adeguate) oppure statica (i punti vengono acquisiti
all'inizio e il "mondo" non cambierà più per tutta l'esecuzione del programma).
La complessità computazionale ottima del problema per il caso 2D è dell'ordine di
O(N logN), dove N è il numero di punti che conpongono il set iniziale del quale si vuole
calcolare l'inviluppo convesso. Tale algoritmo è stato sviluppato per la prima volta da
Kirkpatrick e Seidel.
Il caso n-dimensonale è più delicato.
Il caso 3D è ovviamente il più semplice e qui si può dimostrare che è possibile
calcolare il convex hull di N punti in O(N logN). Più in generale, invece, ci sono dei
risultati che, però, partono da alcune assunzioni. In [2] ad esempio, si arriva a
dimostrare che il convex hull di un set di N punti in d-dimensioni può essere costruito
mediante la tecnica del gift-wrapping in
    T(d, N)= O( N^( floor(d/2)+1 ) ) + O( N^( floor(d/2) )*logN )
    dove il simbolo ^ identifica il consueto elevamento a potenza x^y
Un analogo risultato sempre in [2] mostra che usando la tecnica beneath-beyond si arriva
a:
    T(d, N)= O( N^( floor(d/2)+1 ) )
In entrambi i casi l'assunzione è quella di avere sempre a che fare con politopi semplici,
ovvero politopi composti da facce semplici. Se rimuoviamo questa ipotesi, non saprei quali
altri risultati siano disponibili, nè se il problema divenga NP-completo. Il testo in
questione si limita a dire che, se non abbiamo il vincolo del politopo semplice l'analisi
dell'algoritmo diventa molto più difficile. :-)
Due testi di riferimento che posso consigliarti sono:
[1] "Computational Geometry and Computer Graphics in C++", di Michael J. Laszlo, Prentice
Hall per una trattazione teorica di base e una serie di algoritmi implementati,
limitatamente al convex hull in due dimensioni. Ci sono anche alcuni buoni algoritmi di
triangolazione, come la triangolazione di Delaunay oppure la triangolazione di poligoni
monotoni in tempo lineare dovuta a Chazelle (questo è un
risultato abbastanza recente della ricerca, visto che è datato 1991).
[2] "Computational Geometry" di Franco P. Preparata e Michael Ian Shamos, Springer-Verlag.
Questo testo è decisamente più teorico e tratta anche il caso n-dimensionale. Gli
algoritmi sono tutti in pseudo-codice, ma la trattazione è approfondita, sia nel caso
On-Line, sia in quello Off-Line, sia èper il 2D, sia per il 3D.
Personalmente, mi sono occupato del convex hull in 3 dimensioni implementando l'algoritmo
di gift-wrapping e usando come supporto la struttura dati DCEL (doubly connected edge
list) inventata dallo stesso Preparata. La piattaforma è stata Windows95/NT, il linguaggio
il C++ e per la parte dedicata al rendering ho usato DirectX. L'argomento, come del resto
la CG in generale, interessa moltissimo anche me, quindi se vorrai continuare la
discussione, io sono disponibilissimo, magari in privato, visto che ciò non ha molta
attinenza con il C++ di per sé, se non come linguaggio implementativo.
Ciao
Andrea

Finora avete parlato di algoritmi
Ma come faccio in Visual C++6.0 con MFC ad accedere ai punti dell'immagine
di un controllo CPicture???

di un controllo CPicture???
Dove viene documentato un controllo CPicture in MFC?
Andrea