Civil Engineering Reference
In-Depth Information
p
3
Triangle T
∆1
∆2
p
∆3
p
1
p
2
Figure 3.27
Area co-ordinates of
p
.
3. If L
1
, L
2
and L
3
are all positive or zero, then the triangle T contains point
p
; otherwise,
determine how to update the triangle T. Check how many area co-ordinates are negative.
a. One negative value, say, Li,
i
, i = 1, 2 or 3. Then update T ↦ T
i
, where T
i
is the i
th
neighbour of T opposite to the i
th
vertex.
b. Two negative values, say, Li
i
and L
j
, i, j = 1, 2 or 3. Then, randomly select between
i and j, and update T in the same way as step 3a.
In case the scheme of changing the starting triangle is employed, then choose the
most negative value between Li
i
and L
j
, and update T in the same way as step 3a.
4. Go back to step 2. For the scheme of changing the starting triangle, check the number
of triangles visited to see whether the search has to be started with a new triangle.
3.5.4.6 Circumcentre and circumcircle
Starting from the BASE, the CORE can be easily established by applying the empty-circle
test to the neighbouring triangles. Continue applying the test to more adjacent triangles
until all non-Delaunay triangles are determined. Following the lemma of Delaunay, a valid
insertion CORE consists of non-Delaunay triangles in a connected piece whose boundary is
made up of edges shared by two triangles that give a positive and negative response to the
circle inclusion test.
The circum-radius of a triangle is given in Appendix A.3. However, the circumcentre is
also required in the empty-circle test; the circum-radius and the circumcentre are deter-
mined directly using vector algebra from the co-ordinates of a triangle ABC, as shown
in Figure 3.28. Let AD be the diameter of the circumcircle passing through point A, and
denote vectors AB, AC and AD, respectively, by
C
D
c
O
d
A
b
B
Figure 3.28
Circumcentre and circum-radius of a triangle.
