



Chapter: 1. Source code download, 2. Processing method( Newton Raphson ), 3. Test results, 4. Test code, => NormalLinesBetweenShapesBasic.zip, NormalLinesBetweenShapes.zip 2. Processing methodreturns=>page top 2.1 Processing steps(Figure 2.1, 2.2) Step1. Test for possible existence of a common normal lines First, divides the curve1 to small segments as shown in Figure 2.1 so as not to have inflection points. Next, creates the normal lines which are line1, line2 at the end points of the small segment. At the same time, divides the curve2 to small segments and cover each small segment by a rectangle (bounding box). Here, if the all or part of the bounding box which covers the small segment of the curve2 exists in the sandwiched area by the line1 and line2 (light blue area in Figure 2.1), then there is a possibility that the small segment of curve2 and the segment of the curve1 delimitted by p1 and p2 has a common normal line. Moreover exchanges the standpoint of curve1 and the curve2 and executes the same test as shown in Figure 2.2, the more accurate possibility for the existence of common normal lines will be given. Step2. Bisection method to get the higher possibility for the existence of common normal lines Bisects the couple of segments of the curve1 and curve2 which may have common normal lines and executes the same test described in Step1. Repeats this process by recursive call until the divided segments become enough small. Step3. High accurate computation by Newton Raphson method Sets the center points of the enough small segments of the curve1 and curve2 as the initial points and executes the Newton Raphson method.
2.2 Formulasreturns=>page top 2.2.1 Formulas for Step1 (Figure 2.3(a)(e)) To test that the all or part of the bounding box exists in the sandwiched area (light blue area in Figure 2.1), it is enough to test whether each of the vertexes of the bounding box is exist in the sandwiched area or not. The following (a)(d) describes the case that line1 and line2 are not parallel, and the (e) describes the case that they are parallel. Let e_{1} and e_{2} be the unit normal vectors of the line1 and line2 directions, and let e_{p} be the unit vector headed from the point Q to the point p shown as Figure 2.3(a). Here the point Q is the intersection point between the line1 and line2. We find the condition that the point p exists in the "Region A". The the outer product between two 2D vectors can be defined in the similar way of that of 3D vectors as follows; e_{1}×e_{2} =e_{1x} * e_{2y}  e_{1y} * e_{2x}(1) Here, the e_{1}×e_{2} corresponds to zvalue of the outer product between two 3D vectors and the e_{1}×e_{2} represents the signed area of the parallelogram spanned by e_{1} and e_{2}. Additionally we assume e_{1}×e_{2}≧0 (if not, exchanges e_{1} and e_{2}). : In the normal cordinate, e_{1}×e_{2}≧0 is satisfied if the rotation from e_{1} to e_{2} is counter clockwise, however in the graphic coordinate, the outer product≧0 is satisfied if the rotation is clockwise, because the yaxis is downward. (a) The condition that the point p exists in the Region A (Figure 2.3(a)). 0≦e_{1}×e_{p} ≦e_{1}×e_{2} and 0≦e_{p}×e_{2} ≦e_{1}×e_{2}(2) (b) The condition that the point p exists in the Region B (Figure 2.3(b)). 0≦(e_{1})×e_{p}≦(e_{1})×(e_{2}) and 0≦e_{p}×(e_{2})≦(e_{1})×(e_{2}) => (e_{1}×e_{2})≦e_{1}×e_{p}≦0 and (e_{1}×e_{2})≦e_{p}×e_{2}≦0(3) (c) The condition that the point p exists in the Region C (Figure 2.3(c)). 0≦e_{p}×(e_{1})≦e_{2}×(e_{1}) and 0≦e_{2}×e_{p}≦e_{2}×(e_{1}) => 0≦e_{1}×e_{p}≦e_{1}×e2 and 0≦(e_{p}×e_{2})≦e_{1}×e_{2} => 0≦e_{1}×e_{p}≦e_{1}×e_{2} and (e_{1}×e_{2})≦e_{p}×e_{2}≦0(4) (d) The condition that the point p exists in the Region D (Figure 2.3(d)). 0≦e_{p}×e_{1}≦(e_{2})×e_{1} and 0≦(e_{2})×e_{p}≦(e_{2})×e_{1} => 0≦(e_{1}×e_{p})≦e_{1}×e_{2} and 0≦e_{p}×e_{2}≦e_{1}×e_{2} => (e_{1}×e_{2})≦e_{1}×e_{p}≦0 and 0 ≦e_{p}×e_{2}≦e_{1}×e_{2}(5) (e) The condition that the point p exists in the sandwitched area between line1 and line2 (Figure 2.3(e)). Let define the unit vectors: e_{p1}, e_{p2} and e_{p} shown as Figure 2.3(e), then the condition is following. 0≦e_{n}×e_{p1}≦Q2Q1 (6) Here, Q2Q1 is the distance between line1 and line2. => The test resuls are shown in Figure 3.1, 3.2.
2.2.2 Newton Raphson method and the formulas for Step3returns=>page top Let t_{1} and t_{2} be the parameters of C_{1} and C_{2} curves and represents these curves by their x, y components as follows: Here, bold types represent vectors. (1) To get a common normal line between two curves, we have to find the t_{1}, t_{2} which achieve the local minimum of the distance between two curves. The following f_{1}(t_{1}, t_{2}) is the square of the distance bwtween C_{1} and C_{2}. (2) The following conditon is required to minimize the f_{1}(t_{1}, t_{2}) (<a, b> is inner product of vector a and vector b). (3) Let f_{1}(t_{1}, t_{2}), f_{2}(t_{1}, t_{2}) be the right side of the abve (3) (ignoring coefficient). then, (4) Let dt_{1}, dt_{2} be very small values or infinitesimals(dt_{1}, dt_{2} are written as Δt_{1}, Δt_{2} in a textbook), then the following formulas are derived from the relatons between total differential and partial differential for the f_{1}(t_{1}), t_{2}, f_{2}(t_{1},t_{2}). (5) Here, the right sides of (5) are represented as follows: (6) The approximation formula of the NewTonRaphson method is given by setting parts of the left sides of (5) equal 0(zero) as follows. (7) (5) can be written as follows: (8) The matrix representation of (8) is followings: (9) Let D be the matrix of the left side of (9): (10) The dt_{1}, dt_{2} are given by solving (9) as follows (det means determinant): (11) 3. test Resultsreturns=>page top 3.1 Test code: NormalLinesBetweenShapesBasic
3.2 Test code: NormalLinesBetweenShapes
4. Test codereturns=>page top The code of the NormalLinesBetweenShapes is same as that of NormalLinesBetweenShapesBasic. Only difference is the contents of the Testcases. 4.1 Classes Overview
4.2 Specifications return=>page top 4.2.1 public class NormalLinesBetweenShapesPanel extends JPanel


Copyright (c) 20092013 All other trademarks are property of their respective owners. 