Calculating Intersection Of Spherical Caps_part2-jr

3. Calculating the angle of the great arc of a spherical cap 3.1 Overview For each of the reader antennas, the power received by the tag can be obtained from the Friis equation:

PR = PT

GT (θ T , φT )G R (θ R , φR )λ2 2 2 (1 − ΓT )(1 − ΓR ) pˆ T • pˆ R 2 ( 4πr )

2

If the orientation and the position of the reader antenna plus along with the position of the tag antenna are known, it is easy to obtain the threshold value of the tag antenna gain below which that the specific tag will not be activated. To simplify the formula, we utilize make the same assumptions as made in Chapter 4, i.e. the reflection coefficient ΓT and ΓR are 0 and the polarization loss factor is 0.5. Then the threshold tag antenna gain can be represented as

G R (θ R , φR ) threshold =

2 PR _ min ( 4πr ) 2 PT GT (θ T , φT )λ2

,

where PR _ min is the minimum power required to activate the tag.

The antenna gain for a half-wave dipole antenna is only a function of only θ R , and which can be represented as

 π   cos 2 cosθ R     G R (θ R ,φR ) = 1.641 sin θ R    

2

Therefore, a threshold value of θ R can be obtained for each reader antenna, each of which

corresponds corresponding to the angle of the greatest arc of the spherical cap created by that antenna. To differentiate between different reader antennas, θ i is used to represent the angle of spherical cap cast by reader antenna i. The bigger the value of θ i is, the

larger the spherical cap is, and the more the number of unreadable orientations of the tag point there are with respect to the specific reader antenna i. ) It is important to notice that

θ i in the antenna gain function is the maximum angle between any two points on a spherical cap and the reader axis; in other words, it is only half of the value of the great arc angle of the spherical cap in Table 1. 3.2 Methodology A closed form formula to calculate θ i given the threshold value of the dipole antenna gain

π  has not been found in this research. The difficulty lies in the fact that cos cosθ i  is not 2  a typical trigonometric function. Although based on the plot of the antenna gain in Figure 6 below, it does appear to take a sine-likesinusoidal shape, it cannot be approximated byinto a simple trigonometric function. Figure 7 plots two functions. The first one is

2

 π   cos 2 cosθ i     , which is the transformed antenna gain function obtained by dropping   sin θ i     the coefficient. The second one is sin( 2θ i − π / 2) / 2 + 0.5 , which is constructed in such a way that it has the same period, and maximum and minimum values of as the first one. It can be seen clearly that the second trigonometric function shows a different curvature from the antenna gain function.

1.8 1.6 1.4 1.2 1 0.8 0.6 0.4 0.2 0

0

50

100

150

200

Figure 6 Dipole antenna gain against θ i 1.2 1 0.8

Transformed dipole antenna gain sin(2θ-π/2)/2+0.5

0.6 0.4 0.2 0 0

10

20

30

40

50

60

70

80

90

100

Figure 7 Comparison between transformed antenna gain and a trigonometric function Therefore, Iinstead of attempting a functional approximation, an off-line look-up table is used in this research to map the value of θ i and that of the corresponding GR . It is important to realize that the threshold value of θ i is unique only for the period of [0, π/2)

because a half-wave dipole antenna’s gain is a function of θi with a period of π and is symmetric at θi = π/2. Therefore such a look-up table only needs to store the values for θi from 0 to π/2. Such a look-up table has severalthe following benefits. First, it is fairly fast to extract information from because only a linear search is required once the value of antenna gain is given. Secondly, because of the symmetry characteristics of the dipole antenna gain, the range of the search is relatively small. All the values of the look-up table can be read directly into the memory without compromising the system performance. Lastly, the antenna gain is monotonic monotone increasing between 0 and π/2. Table 1 Part of the look-up table

θi (in degree)

GR

30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

0.286265 0.306028 0.326448 0.347517 0.369229 0.391574 0.414541 0.438118 0.462291 0.487044 0.51236 0.53822 0.564604 0.591487 0.618845 0.646652

Table 2 shows part of the look up table for θi between 30 degrees and 34 45 degrees angle. A onedimension array is used to store the value of GR with the index from 0 to 90. In particular,

2

 π   cos 2 cosθ R     = 0 . A linear interpolation is used to obtain GR [0] is 0 because Lim1.641  θ R →0 sin θ R     the value of θi given a specific value of for GR . As stated before, the angle of the great arc in

the spherical cap is actually 2θi.

4. Calculating αi αi is the angle between the plane of the great arc and the reader axis. After θi is obtained, all the rest of the parameters in Table 1 will be calculated based on the methodology discussed in this section. Instead of focusing on the 3-D space, a linear search along 1-D space is used [ Huang, Tseng and Lo]. In this section, we first examine the relationship between different parameters in the Table 1, i.e. how to calculate the values of the rest of the parametersm given the value of one of the parameters and θi . This is important because in fact αi cannot be obtained directly in this methodology. We tThen we introduce the algorithm in its simplified geometric form. Lastly, we deal with issues of implemeantation such as spherical coordinate rotation, etc.

4.1 Relationship between different parameters For conveniencet, part of the Table 1 is shown below in Table 3.

Table 2 Partial list of notation

li

The arc of the intersection area that

Li

lies in SCiri The great arc that passes the end points of li and falls into the

Φi

intersection region The arc angle of li

γi Φi αi

The arc angle of Li

γi The angle between the great circle

hi

plane that contains Li and OPi bi The distance between the center of Si

SCiri and the center of the unit ball The distance between the center of SCiri and intersection line of Li and SCiri The lune-shape area that is formed

Li

Si

Pi li bi

αi O

If we assume Φi is known, then

hi

SCi

by Li and li

θi Φi 2

•

li = sin

•

sin

•

bi = sin

•

hi = cos

•

b θ Φ α i = arctan( i ) = arctan(tan i cos i ) hi 2 2

γi θ Φ θ Φ = sin i sin i ⇒ γ i = Li = arcsin( 2 sin i sin i ) 2 2 2 2 2 θi Φ cos i 2 2 θi 2

Therefore, once we can getobtain Φi , the values of the rest of the parameters are a functions of both Φi and θi. In the next sub section, we will show thathow to obtaining the area of Si is also a function of the set of above set of parameters. However, Tthe rest of this section will be devoted to the calculation of Φi since the calculation of θi is explained in the previous section.

4.2 Calculating Φi 4.2.1 Dot product test Φi is the angle for the arc of the intersection area that lies in the spherical circle SCiri. To simplify the calculation, we assume that the reader axis OPi is the z- axis and the tag point O is the origin, so that each point q on the spherical circle SCiri can be represented as

θi   x = sin 2 cos φ  θi  y = sin sin φ where φ ∈ [0,2π ) 2   z = cos θ i 2  Here Φi corresponds to the arc of SCiri which lies within another spherical cap SCj.

Lemma1: Let OPj be the reader axis for the jth reader with its angle of the great arc of a spherical

cap θj. Then point q is within the SCj if, and only if v q • vOPj >= cos

θj where v q and vOPj is 2

are the points q and OPj expressed as unit vectors format of point q and OPj. Proof: The dot product of two units vectors v q and vOPj is the cosine angle of the two vectors. If such an angle is smaller than the half of the great arc angle, then point q is within the spherical cap SCj based on its definition.

q Pj θj/2

Figure 8 An example of a point q within SCj

Therefore, for each of each point q on the spherical circle SCiri, a dot product can be compared

against the value of cos

spherical cap SCj. 4.2.2 Algorithm

θj can be used to determine whether or not such a point is within 2

A linear search method is used to obtain the value of Φi which and is stated below.

φ = 0; 2 φmin _found = false; 3 φmax _found = false; 4 while ( φmin _found = true and φmax _found = true) 5 { 6 get xq, yq, zq; 7 θ if ( v q • vOPj >= cos j ) and ( φmin _found = false ) 2 8 φmin = φ ; 9 end if 1 θj if ( ) and ( φmin _found = true) and ( φmax _found = false) v • v <= cos q OP 0 j 2 11 φmax = φ ; 1 end if 2 φ = φ +1; 1 3 1 } loop 4 15 φ = φmax − φmin ; 1 if ( φmin = 0) 6 1 { 7 1 φ = 360 ; 8 1 φmin _found = false; 9 2 φmax _found = false; 0 2 while ( φmin _found = true and φmax _found = true) 1 2 { 2 2 get xq, yq, zq; 3 2 θj if ( ) and ( φmin _found = false ) v • v >= cos q OP 4 j 2 2 φmin = φ ; 5 2 end if 1

6 2 7

if ( v q • vOPj <= cos

2 φmax = φ ; 8 2 end if 9 φ = φ -1; 3 0 3 } loop 1 32 φ = φ + (φmin − φmax ) ; 33 } 34 return φ ;

θj ) and ( φmin _found = true) and ( φmax _found = false) 2

From lLines 4 to line 15 represent, an iteration is used to search for the range of for φ . However, there is a special case that the ranger of φ may go across the arbitrary start/end point which is 0 degreeHowever, it should be noted that in fact, x degrees is the same as (360+x) degrees, and since we arbitrarily select 0/360 as the start/end point for the linear search, we need to account for the case where 0 and 360 both lie within the range for φ . To solve this special scenario as shown in Figure 9, lines 16 to line 33 repeat the linear search from 360 downward if in the previous search the value of φmin is 0.

0

φ1

φ2

3

Figure 9 An example of two intervals for calculating Φi Although the search does not stop until both ends of the interval for Φi is are found, the iteration will stop before φ reaches 360. This is because all the degeneracy degenerate scenarios will be eliminated beforehand. A bisection search can could be used effectively to speed up the process section. if If there were no special scenarios such as the above wheren the value of Φi should be is

obtained from two intervals instead of one intervals, bisection search can be convenient and fast. In practice, the author it was found that such special scenarios are very common while the interval length is seldom very long; therefore a simple linear search is used in the algorithm. 4.3 Coordination transformation: translation and rotation AtIn the beginning of Sectionthe 4.2, to simply the descriptionelaboration of the algorithm, we assumed that the reader axis OPi is is the z z-axis and the tag point O is the origin. However the value of vq which is the vector form of point q will be used to obtain the dot product with OPj (the reader axis of antenna j) in order to test whether q is within the spherical cap SCj. All vectors should be using the same coordinate system in order to obtain the correct values. This subsection gives the details of such the required coordinate transformation processes. 4.3.1 Coordinate translation Overall, all calculation will be based on the translated coordinate system where the tag point is the origin while overall there will be no rotation process involved except in the second step. Therefore, all vectors and points should be translated into the tag-point-origin system. Let Suppose the current tag point in the global coordinate system has the coordinates ( x0 , y 0 , z 0 ) , and let the reader antenna is be at ( a, b, c ) ., then Then the unit vector vOP should be

( a − x0 , b − y 0 , c − z0 ) / r where r is the length of vOP . 4.3.2 Coordinate rotation In the previous subsection, we assume that the z- axis will be aligned with OPi. Therefore, each point q on the spherical circle SCiri can be represented as

θi   x = sin 2 cos φ  θi  y = sin sin φ where 2   z = cos θ i  2

However, this coordinate is based on the rotated coordinate system., in In order to obtain the dot product v q • vOPj , the vector vq should be “rotated back” to the translated system where there is no axis rotation and the origin rests on the tag point. In order to rotate axis z back to OPi, the rotation axis and the rotation angle should be found. The axis of the rotation is defined as a line around which the spinning is donerotation occurs. If a vector v1 becomes v2 after rotation, the axis of the rotation is perpendicular to the plane which contains both vectors. Figure 10 shows an example of axis rotation.

Figure 10 Example of rotation Let vOPj = ( a, b, c ) , then the axis of the rotation will be (-b, -a, 0). This can be proved

easily since both the dot product of (-b, -a, 0) and vOPj and the dot product ofat between (-b, -a, 0) and (0, 0, 1) is are 0, which means the angle between each pair of the vectors is 90 degrees.

The rotation angle α can be represented as arccos(a × 0 + b × 0 + c × 1) = arccos(c ) . Based on geometric calculations, for a given point q(x,y,z) in the rotated local coordinate, its original global coordinates areis x ' = x cos α + (1 − cos α )(b × b × x + a × b × y ) + ( −a × z ) sin α y ' = y cos α + (1 − cos α )( a × b × x + a × a × y ) + (b × z ) sin α z ' = z cos α + ( − a × y + a × x ) sin α From these this set of equations, all points on the spherical circle will be converted into the coordinate system where the tag point is as it was the originally, without any rotation. The dot product tests with coherent coordinate system will be valid in order to obtain the value of Φi.