Обчислювальна геометрія
Обчислювальна геометрія— розділ інформатики, у якому розглядаються алгоритми на вирішення геометричних завдань.
У ній розглядаються такі завдання як тріангуляція, побудова опуклої оболонки, визначення приналежності одного об'єкта до іншого, пошук їхнього перетину тощо. Оперують з такими геометричними об'єктами як: точка, відрізок, багатокутник, коло…
Обчислювальна геометрія використовується у розпізнаванні образів, машинної графіці, інженерному проектуванні тощо.
Зміст
Часто використовуються для чисельних маніпуляцій координати точки та вектора.
Тут розглянемо випадок нормальної декартової системи координат.
x_y_-y_x_\right\>> . Це єдина операція, де зменшення розмірності простору не зводиться до простого відкидання третьої координати (заміни її нулем). Зазвичай для двовимірних векторів значенням векторного твору беруть третю координату відповідних тривимірних векторів: x 1 y 2 - x 2 y 1 y_-x_y_> .
Багатокутник - замкнута крива на площині, що складається з відрізків прямих ліній. Відрізки називаються сторонами багатокутника, які кінці — вершинами багатокутника.
Багатокутник називається простим, якщо він не перетинається сам із собою.
Багатокутник називається опуклим, якщо всі його внутрішні кути менші або дорівнюють 180 градусам.
Ланцюжок вершин називається монотонним, якщо будь-яка вертикальна лінія перетинає її не більше одного разу. Багатокутник, складений із двох таких ланцюжків називається монотонним.