title: C++, point and line position in 2D robust to rounding errors and position
body: <p>A line is defined by two end points P1[x1, y1], P2[x2, y2]. Let Q [xq, yq] be a tested point. Both coordinates are double.</p>
  
  <p>Differencies:</p>
  
  <pre><code>dx1 = x2 - x1
  dy1 = y2 - y1
  dx2 = xq - x1
  dy2 = yq - y1
  </code></pre>
  
  <p>Norms</p>
  
  <pre><code>double n1_sq = sqrt(dx1 * dx1 + dy1 * dy1);
  double n2_sq = sqrt(dx2 * dx2 + dy2 * dy2);
  </code></pre>
  
  <p>My assumption: test with normalized vectors is less sensitive to rounding errors</p>
  
  <pre><code>double test = (dx1 / n1_sq  )  * (dy2 / n2_sq) - ( dx2 / n2_sq ) * ( dy1 / n1_sq );
  </code></pre>
  
  <p>than</p>
  
  <pre><code>double test = dx1 * dy2 - dx2 * dy1;
  </code></pre>
  
  <p>The problem arises in the following cases:</p>
  
  <p>A) A tested point is Q is on the line</p>
  
  <pre><code>Q = [0.5(x1 + x2), 0.5(y1 + y2)]
  </code></pre>
  
  <p>In many cases, the result is not zero, but</p>
  
  <pre><code>test &gt;&gt; 0
  </code></pre>
  
  <p>B) Inappropriate configuration of the line/ tested point</p>
  
  <p><strong>Case 1) long segment:</strong></p>
  
  <p>Let us move the tested point to the start point, dist (Q, |p1, p2|) = 7e-4</p>
  
  <pre><code>P1 = [0, 0]
  P2 = [1000000000.00001, 1000000000.00001]
  Q = [0.0,0.001] 
  </code></pre>
  
  <p>Normalized test: 0.7
  Unnormalized test: 1.0e+6</p>
  
  <p><strong>Case 2) long segment:</strong></p>
  
  <p>Let us move the tested point to the end point dist (Q, |p1, p2|) = 7e-4</p>
  
  <pre><code>P1 = [0, 0]
  P2 = [1000000000.00001, 1000000000.00001]
  Q = [1000000000.0, 1000000000.001] 
  </code></pre>
  
  <p>Normalized test: 5.0e-13
  Unnormalized testt: 1.1 e+6</p>
  
  <p><strong>Case 3) short segment:</strong></p>
  
  <p>Let us move the tested point to the start point, dist (Q, |p1, p2|) = 7e-4</p>
  
  <pre><code>P1 = [0, 0]
  P2 = [0.00001, 0.00001]
  Q = [0.0,0.001] 
  </code></pre>
  
  <p>Normalized test: 0.7
  Unnormalized test: 1.0e-8</p>
  
  <p><strong>Results:</strong></p>
  
  <p>A) The normalized test for long segments is less reliable. The Case 2 could be considered as machinery zero with the following decision: Q is on |p1, p2|... </p>
  
  <p>B) For short segments, the situation is reversed, an unnormalized test gives a machinery zero.</p>
  
  <p>But result of both tests are not constant and the resulted value does not bring any information about real distance of the point Q from the line |p1, p2|. Using a threshold in both tests does not bring a correct result... And the value of the threshold can not be determined before..</p>
  
  <p>What should I do? </p>
  
  <p>My solution is to replace both test with the new test: test the distance of point Q and line P1, p2 and using some threshold eps. Point Q with </p>
  
  <pre><code>dist (Q,|P1,P2|) &lt; eps,  (for example 1e-10) 
  </code></pre>
  
  <p>will be placed on the line P1, P2... The result of the test does not depend on configuration of points (ie if we move the test point Q along the segment P1, P2)</p>
  
  <p>Is anyone using a better test or have a different solution of this problem?</p>