grafok egyamasban...

[Famulus Számítástechnika]

> 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