Локализация точки в выпуклом многоугольнике26.05.2012 10:08

Листая страницы хаба «Алгоритмы», наткнулся на
топик, посвященный решению задачи локализации точки в многоугольнике: задан многоугольник (замкнутая ломаная линия без самопересечений), требуется определить — находится ли заданная точка
A внутри этого многоугольника или нет. В
одном из последних комментариев к топику было высказано недоумение, какое отношение такая
чисто математическая задача имеет к теории алгоритмов. Имеет-имеет, причем самое непосредственное. Задача локализации является классической задачей вычислительной геометрии (не путать с компьютерной графикой). В качестве разминки предлагается взглянуть на картинку справа, на которой изображен многоугольник типа кривой Пеано (источник [
1]), и попытаться ответить на вопрос — красная точка
ты видишь суслика? и я не вижу, а он есть! находится внутри или снаружи многоугольника? А ниже мы (исключительно в образовательных целях) рассмотрим простую вариацию данной задачи, когда заданный многоугольник является выпуклым.
Читать дальше →
© Habrahabr.ru