245
edits
Difference between revisions of "SCI/FreeSCI/Pathfinding/Implementation"
SCI/FreeSCI/Pathfinding/Implementation (view source)
Revision as of 16:17, 29 January 2009
, 16:17, 29 January 2009Some small formatting fixes here and there, added ISBN for a book
(Merging of the FreeSCI Pathfinding documentation. Work in progress.) |
m (Some small formatting fixes here and there, added ISBN for a book) |
||
| Line 19: | Line 19: | ||
==Basic geometry== | ==Basic geometry== | ||
We implemented basic geometry functions such as those in | We implemented basic geometry functions such as those in <ref>J. O’Rourke. Computational geometry in C, second edition, Cambridge University Press, Cambridge, 1998, ISBN 0521640105.</ref>. Some examples of those functions are: | ||
* Left, which takes three points <i>p<sub>0</sub></i>, <i>p<sub>1</sub></i> and <i>p<sub>2</sub></i> and returns '''true''' if <i>p<sub>2</sub></i> lies left of the directed line (<i>p<sub>0</sub></i>, <i>p<sub>1</sub></i>). | * Left, which takes three points <i>p<sub>0</sub></i>, <i>p<sub>1</sub></i> and <i>p<sub>2</sub></i> and returns '''true''' if <i>p<sub>2</sub></i> lies left of the directed line (<i>p<sub>0</sub></i>, <i>p<sub>1</sub></i>). | ||
* Collinear, which takes three points <i>p<sub>0</sub></i> , <i>p<sub>1</sub></i> and <i>p<sub>2</sub></i> and returns true if <i>p<sub>0</sub></i>, <i>p<sub>1</sub></i> and <i>p<sub>2</sub></i> are collinear. | * Collinear, which takes three points <i>p<sub>0</sub></i> , <i>p<sub>1</sub></i> and <i>p<sub>2</sub></i> and returns '''true''' if <i>p<sub>0</sub></i>, <i>p<sub>1</sub></i> and <i>p<sub>2</sub></i> are collinear. | ||
These functions are the foundation for implementing some of the more complex functions. We give several examples in the remainder of this section. | These functions are the foundation for implementing some of the more complex functions. We give several examples in the remainder of this section. | ||
Given two edges (<i>p<sub>0</sub></i>, <i>p<sub>1</sub></i>) and (<i>p<sub>1</sub></i>, <i>p<sub>2</sub></i>) we use Left to detect the convexity of the vertex at <i>p<sub>1</sub></i>. Namely, the vertex at | Given two edges (<i>p<sub>0</sub></i>, <i>p<sub>1</sub></i>) and (<i>p<sub>1</sub></i>, <i>p<sub>2</sub></i>) we use Left to detect the convexity of the vertex at <i>p<sub>1</sub></i>. Namely, the vertex at <i>p<sub>1</sub></i> is convex if Left(<i>p<sub>0</sub></i>, <i>p<sub>1</sub></i> , <i>p<sub>2</sub></i>). This relies on a fixed vertex ordering as described in Section 6.1. | ||
As we described in Chapter 4, we need to compute the blocking point for keyboard support. The blocking point is the first intersection point <i>p</i> that is encountered when traveling the direct trajectory from start point <i>s</i> to end point <i>t</i> that has the property that the line (<i>t</i>, <i>p</i>) intersects the inside of the polygon that contains <i>p</i>, locally at <i>p</i>. We refer to this property as Inside(<i>p</i>, <i>t</i>). We make a case distinction on whether or not <i>p</i> lies exactly on a vertex. If <i>p</i> does not lie on a vertex it lies on exactly one edge (<i>p<sub>0</sub></i> , <i>p<sub>1</sub></i>). Because of the vertex ordering we know that the inside of the polygon is left of that edge. This implies that Inside(<i>p</i>, <i>t</i>) if Left(<i>p<sub>0</sub></i> , <i>p<sub>1</sub>, <i>t</i>). If <i>p</i> lies on a vertex there are two neighbouring vertices at <i>p<sub>0</sub></i> and <i>p<sub>1</sub></i>. We now need to make another case distinction on the convexity of the vertex at <i>p</i> (using Left as demonstrated earlier in this section). | As we described in Chapter 4, we need to compute the blocking point for keyboard support. The blocking point is the first intersection point <i>p</i> that is encountered when traveling the direct trajectory from start point <i>s</i> to end point <i>t</i> that has the property that the line (<i>t</i>, <i>p</i>) intersects the inside of the polygon that contains <i>p</i>, locally at <i>p</i>. We refer to this property as Inside(<i>p</i>, <i>t</i>). We make a case distinction on whether or not <i>p</i> lies exactly on a vertex. If <i>p</i> does not lie on a vertex it lies on exactly one edge (<i>p<sub>0</sub></i> , <i>p<sub>1</sub></i>). Because of the vertex ordering we know that the inside of the polygon is left of that edge. This implies that Inside(<i>p</i>, <i>t</i>) if Left(<i>p<sub>0</sub></i> , <i>p<sub>1</sub>, <i>t</i>). If <i>p</i> lies on a vertex there are two neighbouring vertices at <i>p<sub>0</sub></i> and <i>p<sub>1</sub></i>. We now need to make another case distinction on the convexity of the vertex at <i>p</i> (using Left as demonstrated earlier in this section). | ||