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?

do góry

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?

do góry

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

do góry

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ą?

do góry

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

do góry

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.

do góry