The following program is meant to create a primitive that will travel within a specified polygon (or, in civil engineering, a specified perimeter). This program works differently from other wanderer point generators because the polygon itself is strictly defined in the code - that is, the example below uses the following points that define a two-dimensional concave polygon:
57.59832, 36.773457, 1004.033325 57.642971, 35.974648, 1004.033325 57.065857, 36.585957, 1004.033325 57.065857, 37.845955, 1004.033325 58.10437, 37.301346, 1004.033325
Different uses come to mind:
The algorithm is an accept-reject data sampling algorithm that first generates points within a circle circumscribing a polygon and then accepts all the points that fall within the polygon.
The elegance of this algorithm is given by the fact that only the polygon points have to be known and that everything else is computed at run-time.
For very nasty polygons with very acute angles, the circle circumscribing them will have a very large area compared to the area of the polygon. If this happens, then the algorithm slows down because the points generated within the encompassing circle will stand a low chance to also fall within the polygon.
A second ray-cast has to be performed to check whether the wanderer collides with a boundary. This is because the LSL code only generates points within a polygon which the wanderer then takes as the next destination. In doing so, the generated points using our algorithm do fall within the polygon but the movement of the wanderer may collide with the boundaries along the path between the current position and the next generated point. At first, we generate a point within the polygon:
which makes sure to move the wanderer within the polygon and when the point is reached, then we generate the next point while also checking whether the path would intersect the boundaries:
The centroid of a polygon - or rather, any set of points, is defined as a point that is placed within that data-set so that the distances from that point to all other points is minimal. You can visualize this the following way:
Suppose you have a scattering of houses on a field. You want to place a hospital (marked with
H in the image) so that the hospital is placed at the minimal distance to all points. That means that some of the houses will reach the hospital faster, but that overall the distances from the houses to the hospital are minimal. This is illustrated by Marc van Kreveld in his computational geometry slides along with similar other problems.
The most common way of finding the centroid from a data set of points, reduces to the smallest circle problem. The solution to the smallest circle problem is quite difficult (albeit clever) because it involves a lot of complication in drawing and moving circles. It is also not a definite algorithm - in the sense that it involves looping around until some condition is smaller than a calculated threshold which guarantees termination. Jacob Eliosoff and Richard Unger give a proof for this algorithm, demonstrating that the algorithm works and indicate that it is an algorithm.
We have chosen to create our own algorithm (see Zenos paradox on the race between Achilles and the Tortoise for inspiration) for finding the centroid, and we will illustrate it here:
Series used for approximation: where (absolutely convergent geometric series).
Similar to the Jacob Eliosoff and Richard Unger method the algorithm requires a threshold for termination. In our case, the threshold given by the user represents the distance between the ideal centroid and the centroid approximated by this algorithm.
Compared to the Jacob Eliosoff and Richard Unger method, our algorithm is "much much"™ simpler to implement since it just requires … division and addition.
Our algorithm performs an iterative refinement / approximation of the centroid such that upon every iteration, the position of the centroid is better estimated. In other words, iteration of our algorithm will provide a better estimation of the centroid than at iteration . Given a desired precision (the upper threshold) our algorithm should have the same quadratic complexity .
select any point p = p1 from p1,p2,...,pn for i = 2 to m where m is a desired approximation // compute largest distance d from p to all other points p2,...,pn let d = 0 let pm = p1 for j=2 to n k = distance from p to pj if d < k set d = k set pm = pj // move point p move p towards pm by d / i let i = i * 2
The first complexity represents the algorithm runtime from to whilst the second is a repetitive complexity to determine the largest distance from the current point position to all other points thereby yielding time complexity in total. Perhaps there is a way to eliminate the inner loop based on what is already known to achieve time complexity.
Hypothesis: when then the centroid will be found.
Perhaps a proof could be constructed inductively over the number of points.
For one point , the distance from to itself is such that all terms of the Zeno series , , reduce to zero and the centroid coincides with point .
For two points in space (defining a line):
A (x1, y) ----------------------- B (x2, y)
Such that the centroid (midpoint, in 2D) is to be found at :
A (x1, y) ------------x---------- B (x2, y) C (x1+x2/2, y)
Note that the distance from to is equal to the distance from to such that any path can be chosen as a starting point (follows by applying the distance formula and substituting such that and resulting that ).
Picking one of the two segments from to or to , say , the first step is to move point (and rename to ) by towards where represents the length of the segment :
Z ((3*x1+x2)/4, y) A (x1, y) ------x-----x---------- B (x2, y) C (x1+x2/2, y)
will thus have the coordinates . From the next iteration on, the algorithm will always pick the segment since the segment will always be larger than segment until (in other words, when point will coincide with point ; at which point ).
As we move the point along the segment from to , we have to show that by applying the algorithm at every step we will eventually reach point .
First step, for going from to , we compute and knowing that is at we obtain that:
In the previous section we circumscribed the polygon into a minimal circle and then we would generate points within that circle later checking if the points also reside within the polygon. However, if we were to determine the minimal enclosing ellipse then the reject points could be further reduced.
Notice for example, in the image above how the circle around the polygon allows for more rejection points than an ellipse.
In order to optimise the algorithm, the problem will shift to determining the minimal enclosing ellipse and then generating points within that ellipse and checking whether those points are within the polygon as well.
A polygon-point generator that uses an ellipse generator described in this section is now available on the ellipse polygon point generator page.
Measuring number distributions by observing where the wanderer tends to go?
+------+ +------+ / \ / \ / -> +-------------+ \ + w + \ +-------------+ / \ / \ / +------+ +------+