eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingŁączenie wielokątów
Ilość wypowiedzi w tym wątku: 4

  • 1. Data: 2014-10-27 16:42:17
    Temat: Łączenie wielokątów
    Od: Borneq <b...@a...hidden.pl>

    Pierwsza rzecz to szybka detekcja, czy wielokąty dotykają się czy też
    przecinają. Można dość szybko odrzucić gdy nie przecinają się prostokąty
    ograniczające wielokąty (niekoniecznie wypukłe)
    Druga sprawa - gdy mamy dwa wielokąty, które się przecinają lub dotykają
    to jak je połączyć w jeden?


  • 2. Data: 2014-10-27 18:07:04
    Temat: Re: Łączenie wielokątów
    Od: Wojciech Muła <w...@g...com>

    On Monday, October 27, 2014 4:42:45 PM UTC+1, Borneq wrote:
    > Pierwsza rzecz to szybka detekcja, czy wielokąty dotykają się czy też
    > przecinają. Można dość szybko odrzucić gdy nie przecinają się prostokąty
    > ograniczające wielokąty (niekoniecznie wypukłe)

    Zamiast prostokątów możesz użyć wielokątów-otoczek wypukłych zbudowanych
    w oparciu o wierzchołki wielokąta. Testy przecięcia wielokątów wypukłych
    są całkiem proste, a masz dużo większą precyzję niż dla prostokątów.
    Ale to tylko propozycja.

    > Druga sprawa - gdy mamy dwa wielokąty, które się przecinają lub dotykają
    > to jak je połączyć w jeden?

    Chodzi Ci o sumę boolowską, tak? Potrzebujesz tak naprawdę policzyć
    wszystkie przecięcia krawędzi obu wielokątów i je podzielić
    w tych punktach na "pododcinki". W tym momencie każdy odcinek może
    być jednoznacznie zakwalifikowany, czy leży wewnątrz wielokąta 1 lub 2
    (albo jest krawędzią) - te, które leżą wewnątrz któregokolwiek
    wielokąta kasujesz. Klasyfikację "pododcinków" możesz sprowadzić do
    stwierdzenia, czy którykolwiek jego punkt (np. środkowy) należy do
    wielokąta.

    Policzenie wszystkich przecięć możesz zrobić metodą zamiatania,
    tu masz opis: http://wazniak.mimuw.edu.pl/index.php?title=Zaawanso
    wane_algorytmy_i_struktury_danych/Wyk%C5%82ad_12#prz
    ecinanie_sie_zbioru_odcinkow
    Chociaż, jeśli nie masz wielokątów o dużej liczbie krawędzi możesz
    na początek zrobić naiwną metodą każdy-z-każdym.

    Natomiast stwierdzenie, czy punkt należy do wielokąta można zrobić
    na wiele sposobów: http://erich.realtimerendering.com/ptinpoly/
    Prosty do zaprogramowania jest "Crossing test".

    Generalnie nie jest to bardzo trudne, ale trzeba uważać w przypadkach
    skrajnych. Rozważ użycie gotowca, np. http://www.cgal.org/.

    w.


  • 3. Data: 2014-10-27 18:50:28
    Temat: Re: Łączenie wielokątów
    Od: Borneq <b...@a...hidden.pl>

    W dniu 2014-10-27 o 18:07, Wojciech Muła pisze:
    > Natomiast stwierdzenie, czy punkt należy do wielokąta można zrobić
    > na wiele sposobów: http://erich.realtimerendering.com/ptinpoly/
    > Prosty do zaprogramowania jest "Crossing test".
    >
    > Generalnie nie jest to bardzo trudne, ale trzeba uważać w przypadkach
    > skrajnych. Rozważ użycie gotowca, np. http://www.cgal.org/.

    Sprawdzanie czy punkt leży w środku : bardzo dobry obejmujący wszystkie
    przypadki to http://arxiv.org/pdf/1207.3502.pdf, jeszcze poprawiłem na
    dokładnie wszystkie przypadki


  • 4. Data: 2014-10-28 11:09:02
    Temat: Re: Łączenie wielokątów
    Od: Borneq <b...@a...hidden.pl>

    W dniu 2014-10-27 o 18:50, Borneq pisze:
    > W dniu 2014-10-27 o 18:07, Wojciech Muła pisze:
    >> Natomiast stwierdzenie, czy punkt należy do wielokąta można zrobić
    >> na wiele sposobów: http://erich.realtimerendering.com/ptinpoly/
    >> Prosty do zaprogramowania jest "Crossing test".

    Skupię się na Algorytmie Weilera-Athertona
    http://mst.mimuw.edu.pl/lecture.php?lecture=gk1&part
    =Ch3
    w celu przyśpieszenia wymaga on algorytmu zamiatania


strony : [ 1 ]


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: