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?

do góry

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.

do góry

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

do góry

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

do góry