Найти ближайшую грань многоугольника

?

Перебрать все стороны и найти наименьшее расстояние

а вот и не угадали. Я тоже так в первый раз подумал.Представте себе прямоугольник, у которого a >> b, Там начинаются проблемы.

А точка где при этом? Это как-то мешает опустить перпендикуляры на каждую из сторон?

И в чем проблемы? Или в аналитической геометрии в последние 10 лет произошла революция?

Перебирать есть смысл лишь если задача — одноразовая. А если таких точек внутри многоугольника дофига, то лучше триангулировать, а для упрощения выбора нужных треугольников, зону интереса определять графически: залить на изображении каждый треугольник своим номером интенсивности, потом примерно по координатам точки определить, в какие треугольники она может попасть, и уже потом точно вычислить, где она. Примерно так в опенгле работают с буфером выбора.

Здесь ты, конечно, прав, просто перебор — простейшая штука, а дальше пусть оптимизирует.

А точка внутри?

Перпендикуляр будет проведен к самой стороне, а к её продолжению. И мы соответственно посчитаем расстояние не до стороны, а до прямой, на которой эта сторона лежит, и если оно окажется маленьким относительно других (более близких) сторон - будет печаль-беда.

Да , собственно точка может быть снаружи, хотя для невыпуклых многоугольников описанная мною проблема может наблюдаться и для точек внутри.

Точно, ты прав. Тогда стоит посмотреть на алгоритмы заливки и триангуляции, как советует Эдик.

А что делать, если точка снаружи, пока не могу предположить.

Может быть, считать расстояние до вершин? И та сторона, у которой сумма (двух) расстояний до вершин будет наименьшим — ближайшая.

Была такая идея. Представь себе трапецию,с ооочень маленькой высотой. Притом одно основание трапеции сиильно больше другого. Мы ставим точку со стороны большего основания. На такой фигуре алгоритм глюкнет.

Ну так предложите вариант. Не то что бы у меня совсем идей не было, просто у всех из них есть изъяны. Только прежде почитайте тред, чтоб не предлагать то, что уже было отвергнуто.

не предлагать то, что уже было отвергнуто.

От тебя смердит гуманитарщиной. Что ты называешь «ближайшей гранью»?

А в чем проблема?

Зная координаты точки и концов отрезка, легко найти расстояние до отрезка. Будет 2 случая: перпендикуляр попадает на отрезок или нет. В первом случае ищешь длину перпендикуляра, во втором берешь расстояние до ближайшего конца.

Да, верно

Вот, да. Стоит разве что добавить, что в удобном частном случае выпуклого многоугольника алгоритм можно сделать логарифмичной сложности по количеству вершин.

Перпендикуляр будет проведен к самой стороне, а к её продолжению. И мы соответственно посчитаем расстояние не до стороны, а до прямой, на которой эта сторона лежит, и если оно окажется маленьким относительно других (более близких) сторон - будет печаль-беда.

Проверить, что перпендикуляр опущен между двумя вершинами, если он за вершиной, то для определения расстояния брать ближайшую к нему вершину.