Podręcznik Grafika komputerowa i wizualizacja

Rozdział 3. ELEMENTY GEOMETRII OBLICZENIOWEJ

Rozdział trzeci zawiera podstawowe informacje dotyczące geometrii obliczeniowej – narzędzi niezbędnych do rozwiązywania problemów geometrycznych. Zostały omówione takie zagadnienia jak badanie zorientowania punktów na płaszczyźnie i sprawdzenie przynależności punktu do wielokąta. Prezentowane rozwiązania pokazują także sposób podejścia do problemów geometrycznych w grafice komputerowej.

Złożone operacje na prymitywach, zaawansowane algorytmy graficzne wymagają często rozwiązania problemów, które są na tyle złożone, że stanowią odrębne zadania algorytmiczne. Takie problemy jak np. sprawdzenie przynależności punktu do wielokąta (lub dowolnego obszaru), podział dowolnego wielokąta na trójkąty, wyznaczenie wypukłej otoczki (wypukłej skorupki), wyznaczenie przecięć w zbiorze odcinków są domeną dziedziny zwanej geometrią obliczeniową (ang. computational geometry). Jest to stosunkowo nowa dziedzina informatyki. Z jednej strony jest często traktowana jako narzędzie niezbędne do realizacji algorytmów w grafice komputerowej, z drugiej pozwoliła również wprowadzić do grafiki nowe struktury danych lub je usystematyzować. Wiele zagadnień stanowi samodzielne problemy geometrii obliczeniowej, a jednocześnie rozwiązania problemów tego typu są niezbędne w różnych zastosowaniach, niekoniecznie związanych z grafiką komputerową.