Technical choices

Hull finder for lateral paths

_images/hullfinder.png

Main loop of the hull finder algorithm

The function “Traite” builds the different paths from a source to a detector : the left path, the right path, and the top path.

Traite first divide every points into those on the left of the direct path and those on the right of the direct path. It then calls “PremierePasse”, which list every point of interest (intersection between the “source-receptor” line, and the corner of those obstacles). If there is no valid point around an obstacle, the algorithm stops and no path will be computed.

The list of points from “PremierePasse” is used in “SecondePasse”. SecondePasse will search the point P that goes around an obstacle that has the smallest angle between the vector SR and SP. It will then check if the line between P and the receptor encounters an obstacle, if there is an obstacle then a recursive loop will start. This loop will divide the points between those one the left of the direct path between P and the receptor, and those on the right. It will then call “PremierePasse” and “SecondePasse”, adding the new points P to the path, until :

  1. It reaches the receptor

  2. It cannot find a new point P, in which case there is no viable path

  3. It reaches the maximum amount of loops allowed (for now, the maximum is 2)

Since the recursion algorithm mess with the order of the points of the path, a last call to “SecondePasse” is performed to reorder the points.