3.3 Spreading Algorithm for Piecewise Linear Regions
The problem of spreading of robots over any region boils down to the mathematical
paradigm whether a point is inside a curve or not. The solution for this problem can be
very complex depending of the arbitrary shape of the curve and a general analytic
solution is not known. But if it can be assumed that any curve can be sufficiently
approximated with a piece-wise linear curve, then the solution is given by a very simple
theorem called Jordan curve theorem [Fra02].
Unlike the spreading algorithm for circular region, the above solution warrants the
robots to know their own absolute position as well as the position of the vertices of the
curve to spread themselves inside the given region. Since this is the simplest way to
implement spreading over any piecewise linear region, the increase in cost due to the
above requirement may be compromised.
3.3.1 Jordan Curve Theorem
A semi-infinite ray going out in any direction from the testing point (figure 3.10)
will cross the edges of the curve odd number of times if the point is inside the curve and
even number of times if the point is outside the curve. At each crossing, the ray switches
between inside and outside. This theorem is true for any closed curve, whether it is
convex or concave.
Figure 3.10 Jordan curve theorem