IV. using non-overlap multi-area disposal to build TIN

1. Confirmation of the searching scope
We start from a given triangle, make one side as the extending side, search other points of the whole area scope, make the vertex angle which created by this point and the extending side is the biggest one. We can't consider the vertex angle created by near points is the biggest one. As the following figure, the side of AB is the starting side, points of M and C are the extending points, points M is nearer to AB than point C to AB, but ÐAMB < ÐACB Then, what's the relationship between distance and vertex angle?. In order to explain it, we will discuss it in two ways:


Figure 5

1. Vertex angle is an obtuse angle (<c >=900)
   Under this condition, the circle whose diameter is the extending side includes all points that can form obtuse angle. That is to say, if the vertex angle of the triangle composed of vertex point C and another two points A, B is no less than 900, the point c must locate inside the circle whose diameter is AB, on the contrary, if the vertex angle is less than 900, it must locate outside the circle (see Fig.6). Therefore, if we can find a vertex point C that makes the vertex angle larger than 900, then we can decide the circle to be the only searching area. The point makes the biggest vertex angle in this range is the extending point we're searching for Fig. 7 indicates a case in details. The circle whose diameter is segment AB intersects with block B3, B4, C3, C4, D3 and D4. Because D3, D4 locate on same side with point M, they don't need to be searched. So in this searching process the point whose vertex angle is the biggest obtuse angle that satisfy all searching conditions is the exact extending point within either block of B3, B4 C3 and C4. because the computation of deciding whether one point is locating in the circle or not is very difficult, we often calculate in the circumrectangle of circle. If we cannot find a point that can satisfy the searching condition, we continue to search other points according to the method of acute angle. During the process of building TIN, researching within areas of corresponding circumrectangle will greatly save the time of building TIN. The denser the points are, the better the effects is.
   
   
   Figure 6
   
   Figure 7
   
2. While vertex angle is acute angle (Ðc<900)
   As shown in Fig.8, a is acute angle, then on condition that the locations of point A and point B are known and a is a fixed angle, what's the maximum distance of point C to point A or point C to point B. in other words, while vertex angle is fixed, what's the maximum one between distances of point C to point A or point C to point B in all possible locations of point C? In practice, we can draw this conclusion that the maximum does exit. According to the figure, there is the following mathematical equation.
   
   
   Figure 8
   Cosa=(a²+b²-c²)/(2*a*b)
   Where a, c are fixed , a or b is what we want. Suppose a is the function of b, that is a = F(b). using the following function:
   
   a²+b²-c²-2abcosa=0
   Get derivative of b, and let F' (b)=0
   So 2aF' (b)+2b-2acosa -2bF' (b)cosa=0
   And we get Cosa=b/a.
   
   That is to say, while a is a fixed constant, and a and b satisfy the equation Cosa=b/a, we get the maximum of a, as shown in the following figure:
   
   
   Figure 9
   It is very easy to find that while AC^AB, we get the maximum of a (that is the maximum distance between C and B). Since A and B are points that could be interchanged, while BC^AB, we get the maximum of b(that is the maximum distance between C and A).
   
   Because a and c are fixed, we know that max(a)=max(b)=csina
   
   So when we are looking for extending points, if we find a point C, and compose a triangle whose vertex angle is less than 900 with point A and point B, then we can get two circles whose centers are points A and B, diameters are maximum of a and b respectively. The intersection of the two circles is the area that we want. Generally, the circumrectangle of the area is used as searching area in order to reduce computation (see fig.10).
   
   
   Figure 10
   DAMB is a given triangle, and has found an extending point C (a less than 900). A circle that takes point A as center and max(a) as radius covers:
   
   A2, A3, B1, B3, B3, C1, C2, C3, C4, D1, D2, D3, D4, E2, E3.
   
   The circle that takes point B as center and max(B) as radius covers:
   
   A2, A3, A4, B2, B3, B4, C2, C3, C4, D2, D3, D4, E2, E3, E4.
   
   The rectangle that overlays the two circles covers:
   
   A2, A3, A4, B2, B3, B4, C2, C3, C4, D2, D3, D4, E3, E4.
   
   According to the extending-point-different-side request (that is point C and point M distribute of different side of line AB), the searching region should be:
   
   B4, C2, C3, C4, D2, D3, D4, E2, E3, E4.
   
   The point that has the biggest angle in searching regions is the extending point generated by line AB. In general practical operation, first it will search obtuse angle region, then the acute region. Each time it completes a block searching, it calculates the searching region again to decrease it.

2. confirmation of blocks
The main purpose is to record which region to be searched and to make sure if the whole block satisfy the different-side request. The blocks substitute for points greatly reduce the computation. The shape of blocks could be rectangle or square in proper size. Generally speaking, there're approximately 100 points each block. Too many or too few points can't meet the purpose of dividing blocks. Though they won't affect the quality of the network, the efficiency of building TIN will be influenced. In general the data will be blocked in data pretreatment process.