> + - re: Konkav, lapokbol allo test felbontas konvex testekr VÁLASZ 
> Feladó: Hollosi "HIX" Jozsi, Internetist
> 
> Ez tenyleg eleg koltseges. Itt van egy egyszeru:
> 
> Egy konvex test minden lapjara igaz, hogy a tobbi (tehat nem ahhoz a laphoz
> tartozo) csucs a lap altal meghatarozott sik azonos oldalan van.
> 
> Leforditva szamolasra:
> 
> vegyuk az elso lapot, amit az A B C csucsok hataroznak meg (ha tobbszog, az
> nem lenyeges, hiszen tetszoleges harom meghatarozza a sikot). Keszitsunk egy
> sikra meroleges vektort az A pontban:
> T = (B-A) X (C-A), ahol X a vektorszorzat jele.
> A sorrend mindegy, a (C-A) X (B-A) csak elojelben kulonbozik. Ez megad egy
> sikra meroleges vektort az A pontban.
> 
> Utana az osszes tobbi csucsra (d e f g h ... z) kiszamolando az A-ba eltolt
> skalarszorzat:
> T * (d-A)
> T * (e-A)
>  ...
> T * (z-A)
> Ha ezek elojele egymassal megegyezik (nem nulla), akkor azonos oldalon
> vannak.
> 
> Majd ugyanez az osszes lapra. Ha mindegyik lapra stimmel, akkor konvex.
> 
> Egy N lapu test kb. 10*N^2 szorzassal elintezheto.

Koszonom. Amit en mondtam, az is N^2-es bar nagyobb konstanssal. Az egyik
felbonto algoritmus egyebkent igy dolgozik. Ugyanis ha nem a sik egyik
oldalara esik minden csucs, akkor az adott lap belevag a testbe, es a test
igy felbonthato tobb reszre. Ezt rekurzivan folytathatjuk, amig konvex
testeket nem kapunk.

Azonban ez az algoritmus minden bizonnyal nagyon nem optimalis. Masik
lehetoseg, hogy veszunk egy csucsot, es ahhoz sorban kezdunk hozzavenni
szomszedos csucsokat (illetve azok szomszedait, s.i.t.). Ezt addig
folytatjuk, ameddig az igy kiadodo test konvex, es az eredeti test resze.
A leallasi feltetel persze mas is lehet, igy az algoritmust iranyithatjuk
valamennyire. Pl. csucsok szamat probalja maximalizalni, vagyterfogatot.
Vagy eppen minimalizaljon, ha minel kisebb testekre van szukseg.

Beszeltem olyan emberrel, aki ilyen temabol irta a szakdolgozatat. Az o
tapasztalata az, hogy sajnos ezek az algoritmusok nehezen iranyithatoak,
nem nagyon tudjuk szabalyozni a vegeredmenyt. Debuggolni oket remalom :),
gondoljunk csak bele.
Ezen kivul teljesen altalanos esetre lassuak. Megtalaltam a
neten, hogy bizonyitott, hogy optimalis megoldas megtalalasa NP-nehez!
Es akkor meg nem foglalkoztunk az elfajult testek problemajaval, marpedig
jo, ha egy ilyen algoritmus robosztus.

Igy vegulis ugy dontottem, hogy felreteszem ezt a problemat. Ezt azert
tehetem meg ilyen konnyen, mert az egeszet szerencsere meg tudom
kozeliteni egy masik oldalrol: nem en fogadok egy 3D-s modellt, amit meg
fel kell dolgoznom, hanem a 2D-s modell adatokbol sajat magamnak generalom
le a 3D-s modellet, es ezt mar ugy tudom csinalni, hogy nekem tetszen.

Udv!

--

tocsa

 ---
| email:                        |
| homepage:  http://www.inf.bme.hu/~tocsa       |
 ---