236
edits
Difference between revisions of "SCI/FreeSCI/Pathfinding/Patent"
Jump to navigation
Jump to search
m
SCI/FreeSCI/Pathfinding/Patent (view source)
Revision as of 03:56, 30 January 2009
, 03:56, 30 January 2009Convert the number section to the name, linkify it
m (Deleting repeated reference, fixing broken link to pdf file to a newer location of the same file) |
m (Convert the number section to the name, linkify it) |
||
| Line 10: | Line 10: | ||
The AvoidPath input consists of a start point and an end point and a set of constraining polygons.<ref name="displaymove" /> The output is a path from start point to end point that does not violate any constraints. The patent states that polygons can be assumed not to be self-intersecting. The patent further implies that a point cannot be inside two or more polygons. From that we conclude that any two polygons can be assumed not to intersect. The patent describes three optimization levels. We label these from 0 (no optimization) to 2 (maximum optimization). The optimization levels determine how optimized (in terms of length) the returned path will be. | The AvoidPath input consists of a start point and an end point and a set of constraining polygons.<ref name="displaymove" /> The output is a path from start point to end point that does not violate any constraints. The patent states that polygons can be assumed not to be self-intersecting. The patent further implies that a point cannot be inside two or more polygons. From that we conclude that any two polygons can be assumed not to intersect. The patent describes three optimization levels. We label these from 0 (no optimization) to 2 (maximum optimization). The optimization levels determine how optimized (in terms of length) the returned path will be. | ||
The patent mentions three types of polygons. The first type is the <tt>barred access</tt> polygon that cannot be entered. The second type is the <tt>total access</tt> polygon that cannot be entered unless the start or end point is inside the polygon. The third type is the <tt>near-point access</tt> polygon. For a point <i>p</i> and a polygon <i>P</i> the <i>near point</i> is a point on the edges of <i>P</i> at minimal distance from <i>p</i>. A path may start in a near-point access polygon, but it must exit the polygon through the near-point. Similarly, a path may end in such a polygon, but it must enter the polygon through the near-point. The patent does not accurately describe the semantics of the different polygon types so we had to determine them in another way. We discuss this in Polygon types section. | The patent mentions three types of polygons. The first type is the <tt>barred access</tt> polygon that cannot be entered. The second type is the <tt>total access</tt> polygon that cannot be entered unless the start or end point is inside the polygon. The third type is the <tt>near-point access</tt> polygon. For a point <i>p</i> and a polygon <i>P</i> the <i>near point</i> is a point on the edges of <i>P</i> at minimal distance from <i>p</i>. A path may start in a near-point access polygon, but it must exit the polygon through the near-point. Similarly, a path may end in such a polygon, but it must enter the polygon through the near-point. The patent does not accurately describe the semantics of the different polygon types so we had to determine them in another way. We discuss this in [[SCI/FreeSCI/Pathfinding/Semantics#Polygon types|Polygon types]] section. | ||
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. | ||