236
edits
Difference between revisions of "SCI/FreeSCI/Pathfinding/Implementation"
SCI/FreeSCI/Pathfinding/Implementation (view source)
Revision as of 03:51, 30 January 2009
, 03:51, 30 January 2009Beautify links in reference, replace section numbers by their names and linkify them
m (Replaced numbers by section names. Not linked because being in the same page.) |
(Beautify links in reference, replace section numbers by their names and linkify them) |
||
| Line 25: | Line 25: | ||
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 <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 | 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 [[SCI/FreeSCI/Pathfinding/Implementation#Data types|Data types]]. | ||
As we described in | As we described in [[SCI/FreeSCI/Pathfinding/Specification|Specification]] chapter, 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). | ||
If the vertex at <i>p</i> is convex that implies that Inside(<i>p</i>, <i>t</i>) if Left(<i>p<sub>0</sub></i> , <i>p</i>, <i>t</i>) and Left(<i>p</i>, <i>p<sub>1</sub></i> , <i>t</i>). If the vertex at <i>p</i> is not convex that implies that Inside(<i>p</i>, <i>t</i>) if Left(<i>p<sub>0</sub></i> , <i>p</i>, <i>t</i>) or Left(<i>p</i>, <i>p<sub>1</sub></i>, <i>t</i>). | If the vertex at <i>p</i> is convex that implies that Inside(<i>p</i>, <i>t</i>) if Left(<i>p<sub>0</sub></i> , <i>p</i>, <i>t</i>) and Left(<i>p</i>, <i>p<sub>1</sub></i> , <i>t</i>). If the vertex at <i>p</i> is not convex that implies that Inside(<i>p</i>, <i>t</i>) if Left(<i>p<sub>0</sub></i> , <i>p</i>, <i>t</i>) or Left(<i>p</i>, <i>p<sub>1</sub></i>, <i>t</i>). | ||
| Line 33: | Line 33: | ||
One of the steps in the visibility graph algorithm is the ordering by angle of vertices around a specific point <i>p</i>. The angle is 0 for points on the ray extending right from <i>p</i>, and increases clockwise. Let <i>α(q, p)</i> denote the angle (in degrees) of point <i>q</i> relative to point <i>p</i>. We used the <tt>Qsort</tt> POSIX function to do the ordering. This function calls a callback function for comparing two elements (in our case points). The arctangent function could be used here to compute the two angles, but this function is generally very slow. We chose a different solution that is outlined below. | One of the steps in the visibility graph algorithm is the ordering by angle of vertices around a specific point <i>p</i>. The angle is 0 for points on the ray extending right from <i>p</i>, and increases clockwise. Let <i>α(q, p)</i> denote the angle (in degrees) of point <i>q</i> relative to point <i>p</i>. We used the <tt>Qsort</tt> POSIX function to do the ordering. This function calls a callback function for comparing two elements (in our case points). The arctangent function could be used here to compute the two angles, but this function is generally very slow. We chose a different solution that is outlined below. | ||
We partition the plane around p into two parts (we ignore the trivial partition <i>{p}</i> for which no angle can be determined). Partition A = <i>{(x, y) ∈ ℤ<sup>2</sup>|y < y(p)∨(y = y(p)∧x > x(p))}</i>, being the set of all points q for which <i>0 ≤ α(q,p) < 180</i>. Partition B <i>={(x,y) ∈ ℤ<sup>2</sup>|y > y(p)∨(y = y(p)∧x < x(p))}</i>, being the set of all points <i>q</i> for which <i>180 ≤ α(q, p) < 360</i>. | We partition the plane around <i>p</i> into two parts (we ignore the trivial partition <i>{p}</i> for which no angle can be determined). Partition A = <i>{(x, y) ∈ ℤ<sup>2</sup>|y < y(p)∨(y = y(p)∧x > x(p))}</i>, being the set of all points q for which <i>0 ≤ α(q,p) < 180</i>. Partition B <i>={(x,y) ∈ ℤ<sup>2</sup>|y > y(p)∨(y = y(p)∧x < x(p))}</i>, being the set of all points <i>q</i> for which <i>180 ≤ α(q, p) < 360</i>. | ||
If the two points <i>p<sub>0</sub></i> and <i>p<sub>1</sub></i> that are to be compared are not in the same partition the one in partition A is trivially at a smaller angle. Otherwise, <i>p<sub>0</sub></i> and <i>p<sub>1</sub></i> are in the same partition. Two things have been accomplished by partitioning the plane in this way. The first is that Collinear(<i>p</i>, <i>p<sub>0</sub></i>, <i>p<sub>1</sub></i>) holds if <i>α(p<sub>0</sub>, p) = α(p<sub>1</sub>, p)</i> (distance from <i>p</i> is the comparison criteria in this case). The second is that Left(<i>p</i>, <i>p<sub>0</sub></i> , <i>p<sub>1</sub> ) holds if <i>α(p<sub>1</sub>, p) < α(p<sub>0</sub> , p)</i>. We implemented the sorting by angle using Left and Collinear in this manner, thus avoiding the use of expensive trigonometry functions. | If the two points <i>p<sub>0</sub></i> and <i>p<sub>1</sub></i> that are to be compared are not in the same partition the one in partition A is trivially at a smaller angle. Otherwise, <i>p<sub>0</sub></i> and <i>p<sub>1</sub></i> are in the same partition. Two things have been accomplished by partitioning the plane in this way. The first is that Collinear(<i>p</i>, <i>p<sub>0</sub></i>, <i>p<sub>1</sub></i>) holds if <i>α(p<sub>0</sub>, p) = α(p<sub>1</sub>, p)</i> (distance from <i>p</i> is the comparison criteria in this case). The second is that Left(<i>p</i>, <i>p<sub>0</sub></i> , <i>p<sub>1</sub> ) holds if <i>α(p<sub>1</sub>, p) < α(p<sub>0</sub> , p)</i>. We implemented the sorting by angle using Left and Collinear in this manner, thus avoiding the use of expensive trigonometry functions. | ||
| Line 40: | Line 40: | ||
The first step of <i>ShortestPath</i> is to check for both the start and end point whether it is contained in the barred area of any polygon in the polygon set <i>P</i>. If necessary, we then deal with this situation according to the specification in Chapter 4. If a start or end point <i>p</i> is contained in a total access polygon we remove that polygon from <i>P</i>. For other polygon types we compute the near point of <i>p</i> and use that for pathfinding instead. We add the original point <i>p</i> to the path during the post-processing phase. The only exception is the case where the end point is contained in the barred area of a barred or contained access polygon. In that case the path ends at the near point of <i>p</i>, rather than <i>p</i>. | The first step of <i>ShortestPath</i> is to check for both the start and end point whether it is contained in the barred area of any polygon in the polygon set <i>P</i>. If necessary, we then deal with this situation according to the specification in Chapter 4. If a start or end point <i>p</i> is contained in a total access polygon we remove that polygon from <i>P</i>. For other polygon types we compute the near point of <i>p</i> and use that for pathfinding instead. We add the original point <i>p</i> to the path during the post-processing phase. The only exception is the case where the end point is contained in the barred area of a barred or contained access polygon. In that case the path ends at the near point of <i>p</i>, rather than <i>p</i>. | ||
We find the near point of <i>p</i> by first computing, for each edge e of <i>P</i>, the point on <i>e</i> that is closest to <i>p</i>. This is straightforward <ref> | We find the near point of <i>p</i> by first computing, for each edge e of <i>P</i>, the point on <i>e</i> that is closest to <i>p</i>. This is straightforward <ref>[http://astronomy.swin.edu.au/~pbourke/geometry/pointline/ P. Bourke. Minimum Distance between a Point and a Line], 1988.</ref>. If <i>P</i> has <i>n</i> vertices this gives us <i>n</i> candidates. Out of all the candidates at minimal distance from <i>p</i> we randomly pick one as the near point. | ||
After the pre-processing step the start and end points are not strictly contained in the barred area of any of the polygons. | After the pre-processing step the start and end points are not strictly contained in the barred area of any of the polygons. | ||