245
edits
Difference between revisions of "SCI/FreeSCI/Pathfinding/Patent"
SCI/FreeSCI/Pathfinding/Patent (view source)
Revision as of 17:27, 24 January 2009
, 17:27, 24 January 2009Typo
(Merging of the FreeSCI documentation. Work in progress.) |
m (Typo) |
||
| Line 14: | Line 14: | ||
The patent describes AvoidPath as consisting of three phases, namely a pre-processing phase, a pathfinding phase and a post-processing phase. Even though the pre- and post-processing phases are briefly explained in the patent specification, they are not mentioned in the claims and are therefore not patented. During the pre-processing phase the input is transformed in such a way that the start and end points are not inside any polygon, and that all polygons in the set may not be entered. For example, if the start point is inside a total access polygon that polygon is removed from the polygon set. If the end point is inside a near-point access polygon the end point is moved to the near-point and the original end point will be appended to the previously computed path in the post-processing phase. | The patent describes AvoidPath as consisting of three phases, namely a pre-processing phase, a pathfinding phase and a post-processing phase. Even though the pre- and post-processing phases are briefly explained in the patent specification, they are not mentioned in the claims and are therefore not patented. During the pre-processing phase the input is transformed in such a way that the start and end points are not inside any polygon, and that all polygons in the set may not be entered. For example, if the start point is inside a total access polygon that polygon is removed from the polygon set. If the end point is inside a near-point access polygon the end point is moved to the near-point and the original end point will be appended to the previously computed path in the post-processing phase. | ||
We now proceed with describing the pathfinding phase, limiting ourselves to the most important aspects. The basic idea behind the algorithm is to construct a path that follows the direct trajectory from start point to end point, except where the trajectory properly intersects a polygon (this is covered by claim 6 of the patent). If the direct trajectory properly intersects a polygon <i>P</i>, then there must be more than one intersection point. Let <i>p</i>be the intersection point closest to the start point, and <i>q</i> be the intersection point closest to the end point. The computed path reaches <i>p</i> on the direct trajectory, then goes from <i>p</i> to <i>q</i> along the edges of the polygon and then resumes the direct trajectory. There are two ways to walk from <i>p</i> to <i>q</i>; the algorithm takes the shortest one. Optimization level 0 returns such a path, as illustrated in the following figure. | We now proceed with describing the pathfinding phase, limiting ourselves to the most important aspects. The basic idea behind the algorithm is to construct a path that follows the direct trajectory from start point to end point, except where the trajectory properly intersects a polygon (this is covered by claim 6 of the patent). If the direct trajectory properly intersects a polygon <i>P</i>, then there must be more than one intersection point. Let <i>p</i> be the intersection point closest to the start point, and <i>q</i> be the intersection point closest to the end point. The computed path reaches <i>p</i> on the direct trajectory, then goes from <i>p</i> to <i>q</i> along the edges of the polygon and then resumes the direct trajectory. There are two ways to walk from <i>p</i> to <i>q</i>; the algorithm takes the shortest one. Optimization level 0 returns such a path, as illustrated in the following figure. | ||