grafok egyamasban...

[vajk fekete]

Kozben olvasom az okoskodast, Es PappZoli leveleben ott van a szukseges kiegeszites:

A ket alakzat osszes szakaszparjara megvizsgalod hogy metszoek-e. Ha talalsz metszot, akkor az alakzatok atfedik egymast, nincs ertelme a tartalmazasi kerdesnek. Ha nem talalsz, akkor jon a lenti tartalmazasvizsgalat.

vajk

----- Original Message ----
From: vajk fekete <halaloszto at yahoo.co.uk>
To: elektro at tesla.hu
Sent: Monday, 22 January, 2007 12:04:36 PM
Subject: Re: grafok egyamasban...

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
-----------------------------------------
          elektro[-flame|-etc]






		
___________________________________________________________ 
What kind of emailer are you? Find out today - get a free analysis of your email personality. Take the quiz at the Yahoo! Mail Championship. 
http://uk.rd.yahoo.com/evt=44106/*http://mail.yahoo.net/uk