grafok egyamasban...

[Palasik Sandor]

> 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