Каморка

Как?

Слишком общий вопрос. Какого контура? Чем он описывается? Откуда известно, что замкнутый? В каком виде ты его имеешь? Уравнение? Набор точек? Границы?

Подробности, короче.

Zy писал(а):Слишком общий вопрос. Какого контура? Чем он описывается? Откуда известно, что замкнутый? В каком виде ты его имеешь? Уравнение? Набор точек? Границы?

Подробности, короче.

Имеем плоский полигон. Замкнутый. Невыпуклый. Без дыр. Имеем набор точек P (вершин) с координатами x,y. Вершины хранятся в массиве. P, P[i+1] - ребро многоугольника.

А на каком языке пишем? Мат.библиотеки есть?

Что невыпуклый - это фигово. Вот тут посмотри, может, что подойдет:

http://program.rin.ru/razdel/html/905.html

Очень просто. Любая из вершин - однозначно принадлежит контуру. Если нужна произвольная точка, можно взять вершину.

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

Получается O(n). Можно построить r-index по горизонтальным проекциям и искать пересечения по нему. Тогда O(lg(n)).

Если нужна произвольная точка, можно взять вершину.

Вершина не внутри контура.

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

Насколько я понял, нужно найти точку внутри, а не определить, является ли данная точка внутри.

Насколько я понял, нужно найти точку внутри, а не определить, является ли данная точка внутри

Ну так, это примерно то же самое.
Например, берем первые две вершины. Проводим произвольную вертикальную прямую между ними. Считаем количество пересечений, как описано ранее. Ставим произвольную между самым верхним(нижним) и следующим сверху (снизу) пересечением. Она заведомо принадлежит.
Причем, не важно, выпуклая фигура, вогнутая, с дырками, без дырок..

...Ставим произвольную между самым верхним...

Читать: ...Ставим произвольную точку между самым верхним...

Да, точно. Как ты теперь с него пузырь будешь получать?

vg писал(а):Как?

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

Если нечетное -- мы внутри. Если четное -- мы снаружи.

И откуда вы такие умные? А! Из России...

Старина Зотин писал(а):

Насколько я понял, нужно найти точку внутри, а не определить, является ли данная точка внутри

Ну так, это примерно то же самое.
Например, берем первые две вершины. Проводим произвольную вертикальную прямую между ними. Считаем количество пересечений, как описано ранее. Ставим произвольную между самым верхним(нижним) и следующим сверху (снизу) пересечением. Она заведомо принадлежит.
Причем, не важно, выпуклая фигура, вогнутая, с дырками, без дырок..

Спасибо за ответ. Похоже будет работать. Контр-пример не находится.
Маленькое уточнение по вашему алгоритму. Здесь (как описано выше) число пересечений всегда будет чётным. Так, что считать число пересечений нет необходимости. (Это делают в алгоритмах определения принадлежности точки к внутренней области многоугольника, только используют не прямую, а луч.)

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

ПС. Куда бутылку нести?

ПС. Куда бутылку нести?

Вот и общественность в моем лице это волнует: ты в Тороно, а он в Ванкувере.

Старина Зотин писал(а):Если пересекает вершину - то особый случай.

если совпадает с ребром - тоже