Dzień dobry

Czy mógłby mi ktoś podpowiedzieć gdzie szukać algorytmu:
Mam dane wejściowe w postacie listy odcinków i łuków - mogą się dowolnie
przecinać, łączyć w łańcuchy itd. Chciałbym utworzyć listę zamkniętych
obszarów (oczek) tak aby po "kliknięciu" w jakiś obszar szybko wyznaczyć
jego obwiednię. Wstępnie zakładam że przy importowaniu danych wszystkie
elementy zostaną pocięte na skrzyżowaniach, posortowane w łańcuchy i
przekształcone w graf połączeń. Problemy zaczynają się przy próbach
posortowania łańcuchów w zamknięte pętle. Informacje zawarte w samym
grafie połączeń są (chyba) niewystarczające - np "przekreślone koło"
zawiera trzy pętle, z których mnie interesują tylko dwie wewnętrzne a z
listy połączeń nie da się wywnioskować o które chodzi. Długość ścieżek
też o niczym nie mówi - mogą być dowolnie pozaginane. Sensownym
kryterium jest pole powierzchni figury - ale jego obliczenie też wygląda
na niezły problem... Jak na razie jedyne w miarę praktyczne rozwiązanie
które mi przychodzi do głowy to wyrenderowanie całego tego bałaganu w
wysokiej rozdzielczości i "pokolorowanie" wszystkich obszarów. Niezbyt
mi się to podoba bo dane wejściowe mogą zawierać obiekty o dużej
rozpiętości rozmiarów.
Jakieś sugestie?
Pozdrawiam
Grzesiek

do góry

W dniu 2010-09-09 19:43, grg12 pisze:
> Dzień dobry
>
> Czy mógłby mi ktoś podpowiedzieć gdzie szukać algorytmu:
Hasło do google: Geometria obliczeniowa

> Mam dane wejściowe w postacie listy odcinków i łuków - mogą się dowolnie
> przecinać, łączyć w łańcuchy itd. Chciałbym utworzyć listę zamkniętych
> obszarów (oczek) tak aby po "kliknięciu" w jakiś obszar szybko wyznaczyć
> jego obwiednię.
Jaki warunek musi spełniać punkt w środku obszaru względem odcinków
będących brzegiem tego obszaru?
Jak na to odpowiesz to myślę, że uda Ci się znaleźć rozwiązanie Twojego
problemu.


Pozdrawiam,
Wit

do góry

W dniu 2010-09-09 20:44, Wit Jakuczun pisze:
> Jaki warunek musi spełniać punkt w środku obszaru względem odcinków
> będących brzegiem tego obszaru?
> Jak na to odpowiesz to myślę, że uda Ci się znaleźć rozwiązanie Twojego
> problemu.

Linia wyprowadzona z niego przetnie granice nieparzystą ilość razy? Chmm
- faktycznie - wystarczy sprawdzić czy dowolny punkt na linii granicznej
nie znajduje się w obszarze zamkniętym przez większą pętle.
Dzięki

do góry

On Thu, 09 Sep 2010 20:44:54 +0200, Wit Jakuczun
<w...@g...com> wrote:

>W dniu 2010-09-09 19:43, grg12 pisze:
>> Dzień dobry
>>
>> Czy mógłby mi ktoś podpowiedzieć gdzie szukać algorytmu:
>Hasło do google: Geometria obliczeniowa

Sprzedaje te ksiazke ;-) (mam 2 egzemplarze). Polecam.

milego dnia, hej
--
Moja wyprzedaz wszystkiego: ksiazki, plyty, filmy.
http://www.garaz.pol.pl/

do góry