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

[chur]

Видимость определяется по такому же примерно принципу.
Точка с координатами (X,Y).
Находим вершину для которой значение (yj-Y)/(xj-X) минимально. (Если таких несколько, берем ближнюю).
Это первая вершина, которая видна. Вычисленное значение запоминаем как 'K'. Начинаем обход многоугольника по часовой стрелке.
Для каждой следующе вершины вычисляем то же значение - (yj-Y)/(xj-X).
Если оно больше 'K', то вершина видна. 'K' делаем равным новому значению.
Если меньше - вершина не видна, ничего не делаем, идем дальше.
Вообщем все.
Важное примечание: вышенаписанное справедливо если точка лежит левее самой левой вершины многоугольника или правее самой правой - X < min(xj) | X > max(xj).
Если min(xj) < X < max(xj), но при этом Y < min(yj) | Y > max(yj), то делаем тоже самое, но с выражением: -(xj-X)/(yj-Y)
Случай когда min(xj) < X < max(xj) и min(yj) < Y < max(yj) додумай сам.

[BBB]

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

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

Код: Выделить всё

----
\  /
 \/
 /\
/  \
----

У менея получалось, что хоть бери тот, что больше 180, хоть тот, что меньше, в сумме никак 360 градусов ( т.е. 180* (4-2)) не получалось.

[somewhere]

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

[BBB]

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

Тем не менее, я не исключаю, что, может быть, существует и формула для суммы углов многоугольника с самопересечениями, в которую входит количество этих пересечений. И которая при (количество самопересечений = 0) вырождается в 180 * (N-2).
Увы, сам уже не помню Надо в справочниках искать.