Graphics Reference
In-Depth Information
The process is repeated, removing one variable for each iteration until just one
variable remains and the consistency test can be trivially performed. To help illustrate
the method, consider again the six inequalities for the two triangles of Figure 9.7.
Rewritten to expose the variable x , the six inequalities become:
x
1
+
y
x
y /4
x
1
4 y
x
4 y
x
(19
y )/4
x
5
y
Rearranging the order, these provide three lower bounds (left) and three upper
bounds (right) for x :
y /4
x
x
4 y
1
+
y
x
x
5
y
1
4 y
x
x
(19
y )/4
Because every lower bound on x must be less than or equal to every upper bound
on x , it is possible to completely eliminate x by forming the following nine constraints
from all pairwise combinations of lower and upper bounds for x .
y /4
4 y
1
+
y
4 y
1
4 y
4 y
y /4
5
y
1
+
y
5
y
1
4 y
5
y
y /4
(19
y )/4
1
+
y
(19
y )/4
1
4 y
(19
y )/4
When simplified, these give the following constraints on y :
≤−
4/3
1
0
1/8
1/3
y
2
3
4
19/2
From these it is clear that y is most tightly bounded by
1/3
y
2.
This is a feasible bound, and thus the original system is consistent and the two
triangles have one (or more) points in common. Note that the bound agrees with
the illustration in Figure 9.7, and in fact provides the interval of projection of the
Search WWH ::




Custom Search