[Algorytmy] Obliczanie pola powierzchni figury płaskiej

[Peter Zof]

Witam, mam do rozwiązania pewien problem. Mianowicie użytkownik podaje współrzędne dwóch punktów płaszczyzny. Punkty te reprezentują jakąś figurę (dajmy na to, że użytkownik jest dla nas wyrozumiały i zawsze dobiera punkty tak iż reprezentują one figurę płaską wypukłą). Naszym (moim ) zadaniem jest znaleźć algorytm, który policzy pole powierzchni tej figury. Otóż rozpisałem sobie kilka konkretnych przykładów i doszedłem do wniosku że otrzymam całkiem przyzwoitą złożoność obliczeniową jeżeli podzielę wielokąt na trójkąty. I tu jest problem, bo nie mam za bardzo pomysłu jak logicznie podzielić ten wielokąt na trójkąty. Czytałem pewien artykuł o sortowaniu biegunowym punktów (sortowanie kątowe), jednak nie miałem jeszcze nigdy wcześniej styczności z zagadnieniami geometrii obliczeniowej Będę wdzięczny za pomoc!

[norwimaj]

Jeśli wielokąt jest wypukły, to wystarczy poprowadzić wszystkie przekątne z ustalonego wierzchołka.

Jeśli nie, to też można tak zrobić, tylko że pola niektórych trójkątów należy liczyć z ujemnym znakiem.