236
edits
Difference between revisions of "SCI/FreeSCI/Pathfinding/Specification"
Jump to navigation
Jump to search
SCI/FreeSCI/Pathfinding/Specification (view source)
Revision as of 00:42, 1 February 2009
, 00:42, 1 February 2009Added images. Page done
(More linkify) |
(Added images. Page done) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 2: | Line 2: | ||
In this section we give a formal specification of the AvoidPath kernel function. | In this section we give a formal specification of the AvoidPath kernel function. | ||
This function computes a path from a start point to an end point, avoiding a set of polygons. We start out by formalizing the main notions from [[ | This function computes a path from a start point to an end point, avoiding a set of polygons. We start out by formalizing the main notions from [[SCI/FreeSCI/Pathfinding/Patent#Sierra.27s_pathfinding_patent|Sierra's pathfinding patent]] section. | ||
A point v is a position in the plane. Let <i>x(v)</i> denote the x–coordinate of <i>v</i> and <i>y(v)</i> the y–coordinate of <i>v</i>. | A point v is a position in the plane. Let <i>x(v)</i> denote the x–coordinate of <i>v</i> and <i>y(v)</i> the y–coordinate of <i>v</i>. | ||
| Line 64: | Line 64: | ||
;Definition 8 : Let <i>S</i> be the polygon set. Let <i>s</i> be the start point and t be the end point. Let <i>I</i> be the set of intersection points of the line (<i>s</i>, <i>t</i>) and the polygons in <i>S</i>. The blocking point of <i>(s, t) wrt S</i> is the point <i>p ∈ I</i> closest to <i>s</i> for which the line (<i>t</i>, <i>p</i>) intersects the inside of the polygon at <i>p</i>. | ;Definition 8 : Let <i>S</i> be the polygon set. Let <i>s</i> be the start point and t be the end point. Let <i>I</i> be the set of intersection points of the line (<i>s</i>, <i>t</i>) and the polygons in <i>S</i>. The blocking point of <i>(s, t) wrt S</i> is the point <i>p ∈ I</i> closest to <i>s</i> for which the line (<i>t</i>, <i>p</i>) intersects the inside of the polygon at <i>p</i>. | ||
:[[Image:Pathfinding-figure11.png|frame|Figure 11: Path from <i>s</i> to <i>t</i> as computed by KeyboardPath.|center]] | |||
:Figure 11 shows an example of a path computed by this sub-function. The blocking point <i>s′</i> is determined and then <tt>ShortestPath</tt> is used to compute the portion of the path from <i>s′</i> to <i>t</i>. This leads to the following specification: | :Figure 11 shows an example of a path computed by this sub-function. The blocking point <i>s′</i> is determined and then <tt>ShortestPath</tt> is used to compute the portion of the path from <i>s′</i> to <i>t</i>. This leads to the following specification: | ||