grafok egyamasban...

[vajk fekete]

Ez nem igaz!!!

Vegyel egy C betut, aminek a hasaban van egy haromszog. Siman lehet ugy, hogy mind a harom sarka belul van a C-n, de az egyik oldala megis kilep majd visszalep.

Ha ez nem szamit, akkor jo a modszered.

Arra hogy egy bonyi alakzat tartalmaz-e egy pontot az a modszer, hogy az alakzatot haromszogekre bontod. Hogy egy pont benne van-e egy haromszogben az egyszeru. 

A haromszogre bontas ha konvex akkor trivialis, ha nem akkor kicsit bonyolutabb, de vannak ra std algoritmusok.

vajk

----- Original Message ----
From: Famulus Számítástechnika <hwsw at famulus.hu>
To: elektro at tesla.hu
Sent: Sunday, 21 January, 2007 11:27:22 AM
Subject: Re: grafok egyamasban...

> Ja, ertem, igy tenyleg mukodik.
> Mondjuk ez se az az eroforras takarekos verzio, sokezer graf eseten
> azert eleg huzos lehet.

Nem kell feltétlenül raszteresen érteni a kitöltést. Úgy is fel lehet fogni,
hogy az egész ábrát vízszintes vonalakkal szétszeleteled minden "érdekes"
pontnál: ott ahol törés van a körvonalakban, illetve ahol két vonal metszi
egymást. Két ilyen "érdekes" Y koordináta között nem változik a kitöltési
szabály, úgyhogy egyszerűen mondjuk balról jobbra haladva össze lehet
számolni, hogy melyik vonal végül is mi lesz: határoló vonal, vagy belső
vonal, illetve azt, hogy mi min van belül. Ez működik akár sokezer gráfra
is, és elég gyors. Pl. a Bentley-Ottman algoritmus időbeni bonyolultsága
O(N*LOG(N)). Sokezer gráfra ez sokezer*LOG(sokezer) ami nem gond a mostani
processzoroknak.

Palasik Sándor

-----------------------------------------

Igen ...mostanra ide jutottam magam is.
egy egyenessel vegig kell pasztazni
a belso graf pontjait es
egyenkent eldonteni, hogy
az  pont eppen
belul van-e a kulsoben...

HA mind belul van akkro ez egesz is belul van.

KJ


-----------------------------------------
          elektro[-flame|-etc]







		
___________________________________________________________ 
All New Yahoo! Mail – Tired of unwanted email come-ons? Let our SpamGuard protect you. http://uk.docs.yahoo.com/nowyoucan.html