Algorithm‧ICPC‧Programming: 2月 2008

The main problem is to ask the total illumination $I$ illuminated to a polygon shaped fence from a point light.

It is given that the intensity of certain point is given by $I_0 = \frac{k}{r}$ where $k$ is a constant and $r$ is the point-point distance.

As the fence has height $h$ , assume that we are going to illuminate certain slice with area $h \times \mbox{d}l$ , the illumination is given by $\mbox{d}I = I_0 |\cos \alpha | h \mbox{d}l$ . The question asks about $\int^{\mathcal{A}}\mbox{d}I$ where $\mathcal{A}$ is the area illuminated by the lamp.

The problem is not difficult to solve but, you need to deal with calculus.
Imagine a lamp point $K$ shines on a fence segment $AB$ with height $h$ .

Case I: $K$ 's projection, $P$ is on $AB$
Let the point to segment distance be $s$ . Now that we are going to calculate the intensity of $PB$ .

By trigonometry,

$\cos \alpha = \frac{s}{r}$

By Pythagors' Theorem,

$r^2 = s^2 + l^2$

Therefore,

$\mbox{d}I_{\mbox{left}} = \frac{ksh}{s^2+l^2}\mbox{d}l$

By integration,

$I_{\mbox{left}} = \int^{PB}_{0}\frac{ksh}{s^2+l^2}\mbox{d}l$

$=ksh\int^{PB}_{0}\frac{\mbox{d}l}{s^2+l^2}$
$=ksh[\frac{1}{s}\tan ^{-1} \frac{l}{s}]^{\theta_{\mbox{left}}}_{0}$
$=ksh[\frac{1}{s}\tan ^{-1} (\tan \theta)]^{\theta_{\mbox{left}}}_{0}$
$=kh\theta_{\mbox{left}}$

Note that $\theta_{left} = \angle PKB$ .

You can get the similar result of the side $AP$ by the following expression

$I_{\mbox{right}} = kh\theta_{\mbox{right}}$

where $\theta_{\mbox{right}} = \angle PKA$
Therefore the total intensity of $K$ shines on $AB$ is given by

$I = I_{\mbox{left}}+I_{\mbox{right}} = kh\theta$

where $\theta = \angle AKB$

You may see that the result is simply dealing with the included angle between the light source and the fence segment.

Case 2: $K$ 's projection, $P$ is not on $AB$
By case 1, the result still holds (Just complement angle only).

Since the inclination of the fence to the lamp does not matter, the final conclusion is that: from the point of view of the lamp, how much angle the polygon is inclined to it, the result is simply by using the above equation.

Be careful:

Use acos(-1) instead of pasting constant from wiki as $\pi$
Determine if a point is inside a general polygon
Even though the point is outside the polygon, the view angle can still be $2\pi$