This problem is faced in computer graphics in relation to ray-tracing
[24]. The solution is to represent a node??™s position as a vector from the origin
and then decompose the vector into two directions with an o?®set. The first
direction is taken as the vector V1 going from N1 to T2, the other direction is
the vector V2 going from T2 to T3. The important terms of the decomposition
are the multiplying factors of the two direction vectors, p1 and p2 respectively.
If p1 or p2 is greater than 1 or less than 0, then the point lies outside of the
triangle. The other discriminating condition is if p2 is greater than p1. Let X
be the node that is being tested, then:
[X] = [N1] + p1[(T2 ??’ N1)] + p2[(T3 ??’ T2)], (3)
??(T3 ??’ T2) (T2 ??’ N1)?¤??’1 ??(X ??’ N1)?¤ = ?·p1
p2??. (4)
The matrix ??(T3 ??’ T2) (T2 ??’ N1)?¤??’1
is a function of the triangle and only
needs to be calculated once. Once a neighboring node is found to be within
the search window, the next hop can be chosen according to their distance
from the current checkpoint.
The triangle can be counterproductive if the current checkpoint is close
to the current node. At this point, the triangle area will be very small and
the chances to find a node decreases significantly. A similar situation occurs
when the angle ?µ is too small. To address these cases, the nodes will resize
their search window in two ways. First the node will increase the angle ?µ,
and if this also fails, it will select the checkpoint after the next checkpoint as
C2.
Pages:
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600