Lokalizacja punktu w przestrzeni dwuwymiarowej

Metoda separatorów

Projekt zrealizowany w ramach przedmiotu Algorytmy Geometryczne
Akademia Górniczo-Hutnicza w Krakowie (rok akademicki 2025/2026)

Autorzy:

• Maria Szarata  
• Patrycja Piasecka  

---

Opis projektu 📌

Projekt przedstawia pełną implementację metody separatorów służącej do efektywnej lokalizacji punktu w podziale płaszczyzny.

Celem algorytmu jest szybkie określenie, w którym obszarze (wielokącie) znajduje się zadany punkt o współrzędnych $(x, y)$, przy wykorzystaniu specjalnej struktury danych pozwalającej osiągnąć złożoność wyszukiwania rzędu:

$$ O(\log n) $$

zamiast klasycznego podejścia liniowego $O(n)$.

---

Zakres implementacji ⚙️

Projekt obejmuje wszystkie etapy metody separatorów:

1. Budowa struktury danych grafu 🧩

• reprezentacja podziału płaszczyzny jako skierowanego grafu acyklicznego (DAG),
• przechowywanie wierzchołków wraz z:
  • współrzędnymi $(x, y)$,
  • listami krawędzi wchodzących (IN) i wychodzących (OUT),
  • sumarycznymi wagami krawędzi,
• uporządkowanie wierzchołków względem osi $Y$,
• sortowanie krawędzi kątowo przy każdym wierzchołku.

Graf posiada jedno źródło (najniższy wierzchołek) oraz jedno ujście (najwyższy wierzchołek).

---

2. Interaktywne tworzenie grafu 🖱️

Projekt umożliwia:

• dodawanie wierzchołków myszką,
• łączenie ich w krawędzie,
• automatyczne wygenerowanie struktur coords, adjacency oraz name_map.

Dzięki temu możliwe jest testowanie algorytmu na dowolnych, samodzielnie tworzonych przykładach.

---

3. Sprawdzenie regularności grafu 🔍

Wierzchołek jest regularny, jeżeli posiada:

• co najmniej jedną krawędź wchodzącą,
• co najmniej jedną krawędź wychodzącą
  (z wyjątkiem źródła i ujścia).

W projekcie:

• wykrywane są wierzchołki nieregularne,
• dostępna jest wizualizacja grafu z oznaczeniem regularności.

---

4. Regularyzacja grafu 🛠️

Jeżeli graf nie spełnia warunku regularności, wykonywana jest jego regularyzacja poprzez:

• zastosowanie algorytmu „miotły” (sweep line),
• dodanie brakujących krawędzi (oznaczonych jako fake=True),
• zapewnienie y-monotoniczności obszarów.

Etap ten nie zmienia istniejącej geometrii, a jedynie uzupełnia strukturę tak, aby możliwe było poprawne przeprowadzenie separatorów.

---

5. Wyrównanie wag krawędzi ⚖️

Po regularyzacji następuje wyrównanie wag tak, aby dla każdego wierzchołka (poza skrajnymi):

$$ IN_weight = OUT_weight $$

Proces odbywa się w dwóch przejściach:

• od dołu do góry,
• od góry do dołu.

Wagi określają liczbę separatorów przechodzących przez daną krawędź.

---

6. Konstrukcja drzewa separatorów 🌳

Budowana jest struktura SeparatorTree, która:

• przypisuje każdej krawędzi przedział separatorów,
• generuje ścieżki separatorów od źródła do ujścia,
• buduje zrównoważone drzewo BST na indeksach separatorów.

Drzewo to umożliwia logarytmiczne wyszukiwanie obszaru dla danego punktu.

---

7. Lokalizacja punktu 📍

Funkcja find_point(x, y):

1. Przechodzi po drzewie separatorów (wyszukiwanie binarne),
2. Znajduje lewy i prawy separator ograniczający punkt,
3. Odtwarza wielokąt (obszar), w którym znajduje się punkt.

---

Zastosowania 🚀

Metoda znajduje zastosowanie m.in. w:

• Systemach Informacji Geograficznej (GIS),
• grafice komputerowej,
• silnikach gier (wykrywanie obszaru postaci),
• systemach nawigacyjnych,
• przetwarzaniu danych przestrzennych.

---

Charakter projektu 🎓

Projekt obejmuje:

• implementację algorytmu od podstaw,
• wizualizację grafu,
• obsługę przypadków brzegowych,
• analizę poprawności struktury danych,
• interaktywne testowanie.

Największym wyzwaniem było zapewnienie poprawności regularyzacji oraz konstrukcji drzewa separatorów przy zachowaniu spójności geometrycznej grafu.