Вялые почеркушки о расчете видимости на плоскости

gistfile1.txt

Дана бесконечная плоскость с бесконечно мощным источником света в (0,0) и случайно расставленными на плоскости препятствиями. Требуется рассчитать тени, отбрасываемые препятствиями, при условии, что свет распространяется равномерно, прямолинейно и не отражается.

На практике оперировать бесконечностями неудобно, поэтому следует либо ограничить мощность источника света и считать все точки, находящиеся снаружи некоего радиуса R затененными, либо ограничить плоскость какими-то границами. Так или иначе, далее рассматривается случай с конечным набором точек. Разумно сосредоточиться на препятствиях, так как их меньше, чем точек на плоскости.

Для случая с нулем препятствий очевидно, что все точки освещены и никаких расчетов не требуется.

Для одиночного препятствия в виде точки (x,y) тень есть просто отрезок прямой, соединяющей источник света и препятствие-точку. Очевидно, что все точки (a,b) с a<x или b<y освещены и не требуют расчетов.

Для одиночного препятствия в форме отрезка (x1,y1)->(x2,y2) тень есть выпуклый многоугольник, ограниченного препятствием с одной стороны и двумя тенями, отбрасываемыми точками (x1,y1) и (x2,y2) с другой (и границами плоскости). При x1<=x2 и y1<=y2 очевидно, что все точки (a,b) с a<x1 или b<y1 освещены и не требуют расчетов.

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

Дальнейшие рассуждения зависят от конкретной имплементации. Например, для отрисовки картины освещения комнаты при виде сверху нам потребуются:
1. способ задать прямую двумя точками на ней
2. способ расчета точки пересечения двух прямых
3. способ задать многоугольник через список его углов
4. способ узнать, находится ли точка внутри сложного многоугольника
5. способ сложить два многоугольника и получить новый многоугольник
6. способ нарисовать многоугольник на экране и залить его цветом