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.