Си - Решение задачи про многоугольник и точку.

2fed · 27 май 2008, 02:03

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

un4-funeral · 27 май 2008, 08:26

эм...соединяешь эту точку с вершинами
если какая-то прямая пересекает сторону(до этой вершины) многоугольника, то не видна точка

Хыиуду · 27 май 2008, 11:31

un4-funeral писал(а):эм...соединяешь эту точку с вершинами
если какая-то прямая пересекает сторону(до этой вершины) многоугольника, то не видна точка

Тут весь вопрос, как определить пересечение. Можно, конечно, по формулам аналитической геометрии, но, думается, есть какой-то способ поизящнее

2fed · 27 май 2008, 15:34

А как задать многоугольник без самопересечения?

Хыиуду · 28 май 2008, 11:34

Тривиальный пример - любой треугольник

2fed · 28 май 2008, 12:09

нет, это слишком просто. в своей проге я делаю запрос на количество вершин. затем у меня рандомно генерируются вершины. Для начала мне нужно, чтобы эти вершины образовали многоугольник без самопересечений. может быть это как-нибудь через площадь можно сделать?

Albor · 28 май 2008, 13:17

2fed писал(а):нет, это слишком просто. в своей проге я делаю запрос на количество вершин. затем у меня рандомно генерируются вершины. Для начала мне нужно, чтобы эти вершины образовали многоугольник без самопересечений. может быть это как-нибудь через площадь можно сделать?

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

BBB · 28 май 2008, 13:19

2fed писал(а):Для начала мне нужно, чтобы эти вершины образовали многоугольник без самопересечений. может быть это как-нибудь через площадь можно сделать?

Смутно всплывает из подсознания, что можно через подсчет суммы величин внутренних углов.
Сумма величин внутренних углов N-угольника равна 180°(N-2).
Видимо, в многоугольнике, где стороны пересекаются, эта формула не работает.

somewhere · 28 май 2008, 14:29

Ну почему же, в этом случае внутренний угол получается больше 180, берется внешний

chur · 28 май 2008, 15:30

Многоугольник строим так.
Вершины заданы их координатами (x,y). Соответсвенно, имеем массив M[j]=(xj, yj).
Находим нижнюю точку - min(y) (если их несколько, то берем любую)
Её координаты - (x0,y0)
Остальной массив сортируем по возрастанию значения (xj-x0)/(yj-y0). Геометрически, это выглядит как обход лучом из точки (x0,y0) слева направо. Всё. В отсортированном массиве точки расположены по порядку по часовой стрелке начиная с нулевой.
(Возможные нюансы: вырождения какого-либо угла в 180 градусов и проверка деления на ноль)

По видимости - ща додумаю