План забора

[Alpaka]

На местности, представляющей собой идеально ровную поверхность, стоит высокий забор. План забора представляет собой замкнутую ломаную без самопересечений. Эта ломаная задается N парами координат своих вершин в порядке обхода ограничиваемой забором области против часовой стрелки. Вершины пронумерованы от 1 до N, N<100.
В точке (x,y) стоит человек ((x,y) не может лежать на ломаной). Считая, что каждому звену ломаной становится в соответствие пара номеров концевых вершин, указать, какие звенья человек увидит полностью или частично в качестве невырожденного отрезка, а какие - вообще нет. Если при взгляде звено видно как точка или как пара, точек, то полагаем, что оно не видно.

[Romeo]

Задача не из самых простых для реализации, но одна из ключевых в компьютерной графике. Как следствие, у задачи весьма глубоко проработана методология решений и существуют десятки оптимизаций как для общих случаев, так и для частных. То, что забор располагается на плоскости лишь, упрощает все расчёты, так как оригинальная задача поставлена для трёхмерного пространства. Собственно, она имеет название "удаление невидимых граней и линий". Предлагаю загуглить какую-нибудь статейку с готовой теоретической базой, разобрать её и приступить к реализации. Я с удовольствием помогу с непонятными местами, так как в университете баловался такими вещами и многое помню.

[Alpaka]

Задача не из самых простых для реализации, но одна из ключевых в компьютерной графике. Как следствие, у задачи весьма глубоко проработана методология решений и существуют десятки оптимизаций как для общих случаев, так и для частных. То, что забор располагается на плоскости лишь, упрощает все расчёты, так как оригинальная задача поставлена для трёхмерного пространства. Собственно, она имеет название "удаление невидимых граней и линий". Предлагаю загуглить какую-нибудь статейку с готовой теоретической базой, разобрать её и приступить к реализации. Я с удовольствием помогу с непонятными местами, так как в университете баловался такими вещами и многое помню.

Я нашел реализацию (Пусть точка z - центр координат (если это не так, сделаем параллельный перенос). Для того, чтобы звено забора было полностью видно, необходимо и достаточно, чтобы из точки z, где стоит человек, были видны обе вершины этого звена, и еще какая-нибудь его внутренняя точка. Будем считать, что вершина l звена видна, если интервал (z,l) не пересекает никаких звеньев забора, или же если обе концевые вершины пересекаемого звена k лежат на [z,l], т.е. человек смотрит вдоль звена k. Отсортируем по неубыванию углы, образуемые с осью OX отрезками, одна концевая точка которых z, а вторая пробегает все вершины звеньев (углы отсчитываются от точки z в положительном направлении, т.е. против часовой стрелки). Получаем последовательность углов a1,a2, ,,, ,an. Добавляем в эту последовательность угол an+1=a1. Из точки z в направлении между прямыми, идущими под углами Li и Li+1 может быть виден кусок только одного единственного звена. Из точки z под углами (ai+ai+1)/2, i=1, ... ,n, проводим лучи и для каждого луча смотрим, какое звено k этот луч пересекает первым (если первое пересечение происходит по вершине, то оно не рассматривается). В том случае, если у звена k видны обе вершины, то звено видно полностью, если хотя бы одна вершина не видна, то k видно частично. После анализа точек пересечения всех n лучей те звенья, которые не видны ни полностью, ни частично, получают пометку невидимых.), но вот с написанием кода беда, поэтому обратился к ВАМ с помощью (написанием) кода. Спасибо

[Romeo]

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