eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingStruktury w metodzie zamiatania
Ilość wypowiedzi w tym wątku: 6

  • 1. Data: 2014-10-29 11:47:07
    Temat: Struktury w metodzie zamiatania
    Od: Borneq <b...@a...hidden.pl>

    Metoda zamiatania
    http://wazniak.mimuw.edu.pl/index.php?title=Zaawanso
    wane_algorytmy_i_struktury_danych/Wyk%C5%82ad_12
    Jest trochę niejasna: wiadomo że P jest posortowaną listą punktów, które
    mogą być początkowe lub końcowe.
    Ale co z T?
    Implementuję w C++ na std::set
    #include <set>
    std::set<struktura> T;
    gdzie struktura będzie opisywała dla odmiany odcinki
    Jednak teraz trzeba zdefiniować metodę sortowania. Punkty sortowałem po
    x, a jak sortować odcinki?
    Sprawdzanie przecinania odbywa się z poprzednim i następnym odcinkiem,
    jednak co to znaczy?


  • 2. Data: 2014-10-29 13:05:20
    Temat: Re: Struktury w metodzie zamiatania
    Od: Borneq <b...@a...hidden.pl>

    W dniu 2014-10-29 o 11:47, Borneq pisze:
    > Metoda zamiatania
    > http://wazniak.mimuw.edu.pl/index.php?title=Zaawanso
    wane_algorytmy_i_struktury_danych/Wyk%C5%82ad_12

    To jest zły algorytm bo sprawdza tylko do pierwszego przecięcia
    odcinków, myślałem że mogę go przerobić do znajdowania wszystkich, ale
    po każdym przecięciu trzeba by zamieniać kolejność w strukturze T.
    Czy da się zrobić to na std::set?


  • 3. Data: 2014-10-29 13:22:58
    Temat: Re: Struktury w metodzie zamiatania
    Od: bartekltg <b...@g...com>

    On 29.10.2014 13:05, Borneq wrote:
    > W dniu 2014-10-29 o 11:47, Borneq pisze:
    >> Metoda zamiatania
    >> http://wazniak.mimuw.edu.pl/index.php?title=Zaawanso
    wane_algorytmy_i_struktury_danych/Wyk%C5%82ad_12
    >>
    >
    > To jest zły algorytm bo sprawdza tylko do pierwszego przecięcia
    > odcinków, myślałem że mogę go przerobić do znajdowania wszystkich, ale

    http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann
    _algorithm


    > Czy da się zrobić to na std::set?

    Da się.

    pzdr
    bartekltg





  • 4. Data: 2014-10-29 15:32:05
    Temat: Re: Struktury w metodzie zamiatania
    Od: Borneq <b...@a...hidden.pl>

    W dniu 2014-10-29 o 13:22, bartekltg pisze:
    > http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann
    _algorithm
    >
    >
    >> Czy da się zrobić to na std::set?
    >
    > Da się.

    "If p is the crossing point of two segments s and t (with s below t to
    the left of the crossing), swap the positions of s and t in T"

    Chodzi zwłaszcza o "swap the positions", jak to się da zrobić na
    std::set jeśli jest posortowane i mamy podaną funkcję sortującą?


  • 5. Data: 2014-10-29 21:16:05
    Temat: Re: Struktury w metodzie zamiatania
    Od: bartekltg <b...@g...com>

    On 29.10.2014 15:32, Borneq wrote:
    > W dniu 2014-10-29 o 13:22, bartekltg pisze:
    >> http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann
    _algorithm
    >>
    >>
    >>> Czy da się zrobić to na std::set?
    >>
    >> Da się.
    >
    > "If p is the crossing point of two segments s and t (with s below t to
    > the left of the crossing), swap the positions of s and t in T"
    >
    > Chodzi zwłaszcza o "swap the positions", jak to się da zrobić na
    > std::set jeśli jest posortowane i mamy podaną funkcję sortującą?

    Bez wczytywania się dokładnie: zamień im współrzędne y.
    Usuń elementy, zmodyfikuj, i wstawić je na nowo (usuwając
    dosjajesz iterator, który można użyć jako hint przy wstawianiu).

    Większy problem będzie z wyszukaniem miejsca na wstawienie,
    bo wynik porównania powinien mieć 'kontekst' - pozycję x.
    Ponieważ zmiana x w czasie algorytmu nie zmienia kolejnosci
    (bo robimy to ręcznie) powinno się jakoś dać to sprytnie napisać,
    ale jednak nie jest to dla mnie od razu oczywiste - jak.

    Może rzeczywiście wygodniej będzie sięgnąć po boosta.

    pzdr
    bartekltg






  • 6. Data: 2014-10-30 08:04:04
    Temat: Re: Struktury w metodzie zamiatania
    Od: Borneq <b...@a...hidden.pl>

    W dniu 2014-10-29 o 21:16, bartekltg pisze:
    > Bez wczytywania się dokładnie: zamień im współrzędne y.
    > Usuń elementy, zmodyfikuj, i wstawić je na nowo (usuwając
    > dosjajesz iterator, który można użyć jako hint przy wstawianiu).

    I zobaczyłem, że współrzędne x to nie tylko końce odcinków, ale do nich
    dodaje się także punkty przecięcia, a współrzędnych x jest więcej. Czyli
    struktura vector też się chyba nie nadaje.

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: