home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / opendc12.zip / od124os2.exe / od12osr1.exe / src / LineOps.cpp < prev    next >
C/C++ Source or Header  |  1997-03-21  |  19KB  |  666 lines
  1. //====START_GENERATED_PROLOG======================================
  2. //
  3. //
  4. //   COMPONENT_NAME: odutils
  5. //
  6. //   CLASSES: none
  7. //
  8. //   ORIGINS: 82,27
  9. //
  10. //
  11. //   (C) COPYRIGHT International Business Machines Corp. 1995,1996
  12. //   All Rights Reserved
  13. //   Licensed Materials - Property of IBM
  14. //   US Government Users Restricted Rights - Use, duplication or
  15. //   disclosure restricted by GSA ADP Schedule Contract with IBM Corp.
  16. //       
  17. //   IBM DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  18. //   ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  19. //   PURPOSE. IN NO EVENT SHALL IBM BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  20. //   CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
  21. //   USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
  22. //   OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE
  23. //   OR PERFORMANCE OF THIS SOFTWARE.
  24. //
  25. //====END_GENERATED_PROLOG========================================
  26. //
  27. // @(#) 1.13 com/src/utils/LineOps.cpp, odutils, od96os2, odos29712d 10/10/96 15:59:55 [ 3/21/97 17:20:53 ]
  28. /*
  29.     File:        LineOps.cpp
  30.  
  31.     Contains:    Geometric operations on lines in 2-space.
  32.  
  33.     Written by:    Jens Alfke
  34.                 IntersectLines by Ken Turkowski, from Apple Technical Memorandum KT14.
  35.  
  36.     Copyright:    ⌐ 1993 - 1995 by Apple Computer, Inc., all rights reserved.
  37.  
  38. */
  39.  
  40. #define _OD_DONT_IMPORT_CPP_
  41.  
  42. #ifndef _ALTPOINT_
  43. #include "AltPoint.h"            // Use C++ savvy ODPoint and ODRect
  44. #endif
  45.  
  46. #include "LineOps.h"
  47.  
  48. #ifndef _ODEXCEPT_
  49. #include "ODExcept.h"
  50. #endif
  51.  
  52. #ifndef _ODDEBUG_
  53. #include "ODDebug.h"
  54. #endif
  55.  
  56. #ifndef _ODMATH_
  57. #include "ODMath.h"
  58. #endif
  59.  
  60. #include <stdlib.h>
  61.  
  62. #include <math.h>
  63.  
  64. #ifndef _ODDEBUG_
  65. #include "ODDebug.h"
  66. #endif
  67.  
  68.  
  69. #if defined(_PLATFORM_WIN32_) || defined(_PLATFORM_OS2_) || defined(_PLATFORM_UNIX_)
  70. enum eAnomaly {kNoAnomaly, kAnomalyVertical, kAnomalyPoint};
  71.  
  72. eAnomaly ProcessLine(const ODPoint &p0, const ODPoint &p1,
  73.                      double *slope, double *constant);
  74. #else // !defined(_PLATFORM_WIN32_) && defined(_PLATFORM_OS2_) && defined(_PLATFORM_UNIX_)
  75. enum{
  76.     A00, A01, A10, A11
  77. };
  78. #endif // defined(_PLATFORM_WIN32_) || defined(_PLATFORM_OS2_) || defined(_PLATFORM_UNIX_)
  79.  
  80.  
  81. #ifdef _PLATFORM_MACINTOSH_
  82. #pragma segment ODShape
  83. #endif
  84.  
  85.  
  86. //------------------------------------------------------------------------------
  87. // WithinEpsilon
  88. //
  89. // Returns true if the two numbers are within kEpsilon of each other.
  90. //------------------------------------------------------------------------------
  91.  
  92. WIN32_DLLEXPORT ODBoolean
  93. WithinEpsilon( ODCoordinate a, ODCoordinate b )
  94. {
  95.     ODCoordinate diff = a-b;
  96.     return diff<=kFixedEpsilon && diff>=-kFixedEpsilon;
  97. }
  98.  
  99.  
  100.  
  101. //------------------------------------------------------------------------------
  102. // InRange
  103. //
  104. // Determine whether n falls within the range [r0,r1].
  105. // The r's need not be given in order. Unline rects, endpoints are included.
  106. //------------------------------------------------------------------------------
  107.  
  108. WIN32_DLLEXPORT ODBoolean
  109. InRange( ODCoordinate n,  ODCoordinate r0, ODCoordinate r1 )
  110. {
  111.     if( r0<r1 )
  112.         return n>=r0 && n<=r1;
  113.     else
  114.         return n>=r1 && n<=r0;
  115. }
  116.  
  117.  
  118. //------------------------------------------------------------------------------
  119. // RangesDisjoint
  120. //
  121. // Determine whether two ranges do not overlap. They needn't be given in order.
  122. //------------------------------------------------------------------------------
  123.  
  124. WIN32_DLLEXPORT ODBoolean
  125. RangesDisjoint( ODCoordinate a0, ODCoordinate a1,
  126.                 ODCoordinate b0, ODCoordinate b1 )
  127. {
  128.     if( a0<a1 )
  129.         return Max(b0,b1) < a0  ||  a1 < Min(b0,b1);
  130.     else
  131.         return Max(b0,b1) < a1  ||  a0 < Min(b0,b1);
  132. }
  133.  
  134.  
  135. //------------------------------------------------------------------------------
  136. // IntersectLines                        by Ken Turkowski, tweaked by Jens Alfke
  137. //
  138. // Find the intersection of the two lines determined by two pairs of points.
  139. // Returns:    kIntersection if the two segments intersect;
  140. //            kOutsideIntersection if the lines intersect beyond the ends of the segments;
  141. //            kNoIntersection if the lines are parallel, coincident or degenerate.
  142. //                        (In this last case sect will not be valid.)
  143. //------------------------------------------------------------------------------
  144.  
  145. #if defined(_PLATFORM_WIN32_) || defined(_PLATFORM_OS2_) || defined(_PLATFORM_UNIX_)
  146. // History:
  147. //    The original version of this function, which uses ODFixedPoint arithmetic, was
  148. //    replaced by a version that uses floating point arithmetic for increased
  149. //    performance.  However, the floating point version introduced excessive
  150. //    round-off error.  (The failing scenario is two lines forming a very small angle,
  151. //    with one line being almost horizonal.)  The version immediately below is the newer
  152. //    floating point version.  This algorithm uses fewer multiply and divide
  153. //    operations, so there is less round-off error.  It's even 20-35% faster than
  154. //    the original floating point version.
  155. WIN32_DLLEXPORT IntersectionStatus
  156. IntersectLines(const ODPoint &p0, const ODPoint &p1,
  157.                const ODPoint &q0, const ODPoint &q1,
  158.                ODPoint *sect )
  159. {
  160.     enum eBoundsCheck {kBoundsCheckX, kBoundsCheckY};
  161.  
  162.     double slopeP, constantP, slopeQ, constantQ,
  163.            interX, interY;
  164.  
  165.     eAnomaly anomalyP, anomalyQ;
  166.     eBoundsCheck pBoundsCheck = kBoundsCheckX, qBoundsCheck = kBoundsCheckX;
  167.     ODBoolean inside;
  168.     
  169.     anomalyP = ProcessLine(p0, p1, &slopeP, &constantP);
  170.     anomalyQ = ProcessLine(q0, q1, &slopeQ, &constantQ);
  171.     
  172.     if (anomalyP == kNoAnomaly && anomalyQ == kNoAnomaly)
  173.     {
  174.         double a, b;
  175.  
  176.         a = slopeP - slopeQ;
  177.         if (a != 0.0)
  178.         {
  179.             b = constantQ - constantP;
  180.             interX = b / a; 
  181.             interY = slopeP * interX + constantP;
  182.         }
  183.         else
  184.             return kNoIntersection;
  185.     }
  186.     else
  187.     {
  188.         if (anomalyP != kNoAnomaly)
  189.         {
  190.             switch(anomalyP)
  191.             {
  192.                 case kAnomalyVertical:
  193.                     switch(anomalyQ)
  194.                     {
  195.                         case kNoAnomaly:
  196.                             // P is vertical, Q is normal
  197.                             pBoundsCheck = kBoundsCheckY;
  198.                             interX = ODFixedToFloat(p0.x);
  199.                             interY = interX * slopeQ + constantQ;
  200.                             break;
  201.                         case kAnomalyVertical:
  202.                         case kAnomalyPoint:
  203.                             return kNoIntersection;
  204.                             break;
  205.                     }
  206.                     break;
  207.                 case kAnomalyPoint:
  208.                     return kNoIntersection;
  209.                     break;
  210.             }
  211.         }
  212.         else
  213.         {
  214.             // Q is an anomaly
  215.             // P is a normal line
  216.             switch (anomalyQ)
  217.             {
  218.                 case kAnomalyVertical:
  219.                     // Q is vertical, P is normal
  220.                     qBoundsCheck = kBoundsCheckY;
  221.                     interX = ODFixedToFloat(q0.x);
  222.                     interY = interX * slopeP + constantP;
  223.                     break;
  224.                 case kAnomalyPoint:
  225.                     return kNoIntersection;
  226.                     break;
  227.             }
  228.                 
  229.         }
  230.     }
  231.  
  232.     // Must be an intersection at this point
  233.  
  234.     sect->x = ODFloatToFixed(interX);
  235.     sect->y = ODFloatToFixed(interY);
  236.  
  237.     if (pBoundsCheck == kBoundsCheckX)
  238.         inside = InRange(sect->x, p0.x, p1.x);
  239.     else
  240.         inside = InRange(sect->y, p0.y, p1.y);
  241.  
  242.     if (inside)
  243.     {
  244.         if (qBoundsCheck == kBoundsCheckX)
  245.             inside = InRange(sect->x, q0.x, q1.x);
  246.         else
  247.             inside = InRange(sect->y, q0.y, q1.y);
  248.     }
  249.  
  250.     if (inside)
  251.         return kIntersection;
  252.     else
  253.         return kOutsideIntersection;
  254. }
  255.  
  256. eAnomaly ProcessLine(const ODPoint &p0, const ODPoint &p1,
  257.                      double *slope, double *constant)
  258. {
  259.     double p0x = ODFixedToFloat(p0.x);
  260.     double p0y = ODFixedToFloat(p0.y);
  261.     double p1x = ODFixedToFloat(p1.x);
  262.     double p1y = ODFixedToFloat(p1.y);
  263.  
  264.     if (p0x == p1x)
  265.     {
  266.         if (p0y == p1y)
  267.             return kAnomalyPoint;
  268.         else
  269.             return kAnomalyVertical;
  270.     }
  271.     
  272.     *slope = (p1y - p0y) / (p1x - p0x);
  273.     *constant = p0y - (p0x * *slope);
  274.  
  275.     return kNoAnomaly;
  276. }
  277. #else // !defined(_PLATFORM_WIN32_) && defined(_PLATFORM_OS2_) && defined(_PLATFORM_UNIX_)
  278. // Matt's conversion to "double" data type.  Getting round-off error.
  279. WIN32_DLLEXPORT IntersectionStatus
  280. IntersectLines( const ODPoint &p0, const ODPoint &p1,
  281.                 const ODPoint &q0, const ODPoint &q1,
  282.                 ODPoint *sect )
  283. {
  284.     double_t temp;
  285.     double_t p0x = ODFixedToFloat(p0.x);
  286.     double_t p0y = ODFixedToFloat(p0.y);
  287.     double_t p1x = ODFixedToFloat(p1.x);
  288.     double_t p1y = ODFixedToFloat(p1.y);
  289.     double_t q0x = ODFixedToFloat(q0.x);
  290.     double_t q0y = ODFixedToFloat(q0.y);
  291.     double_t q1x = ODFixedToFloat(q1.x);
  292.     double_t q1y = ODFixedToFloat(q1.y);
  293.     
  294.     // Construct the augmented matrix:
  295.     
  296.     double_t AB[2][3];
  297.     AB[0][0] = p1y - p0y;
  298.     AB[0][1] = p0x - p1x;
  299.     AB[0][2] = AB[0][0]*p0x + AB[0][1]*p0y;
  300.     
  301.     AB[1][0] = q1y - q0y;
  302.     AB[1][1] = q0x - q1x;
  303.     AB[1][2] = AB[1][0]*q0x + AB[1][1]*q0y;
  304.     
  305.     // Find the largest element (in absolute value):
  306.  
  307.     double_t pmax = fabs(AB[0][0]);
  308.     char pwhich = A00;
  309.     temp = fabs(AB[0][1]);
  310.     if( temp>pmax ) {
  311.         pmax = temp;
  312.         pwhich = A01;
  313.     }
  314.  
  315.     double_t qmax = fabs(AB[1][0]);
  316.     char qwhich = A10;
  317.     temp = fabs(AB[1][1]);
  318.     if( temp>qmax ) {
  319.         qmax = temp;
  320.         qwhich = A11;
  321.     }
  322.     
  323.     double_t max;
  324.     char which;
  325.     if( pmax > qmax ) {
  326.         max = pmax;
  327.         which = pwhich;
  328.     } else {
  329.         max = qmax;
  330.         which = qwhich;
  331.     }
  332.     
  333.     // Give up if entire matrix is zero (we were given two degenerate line segments)
  334.     if( max==0 )
  335.         return kNoIntersection;
  336.     
  337.     // Pivot around the largest element and back-substitute. If we're about to divide
  338.     // by zero, this means the two lines are parallel (or one segment is degenerate.)
  339.     
  340.     double_t sectx, secty;
  341.     
  342.     switch( which ) {
  343.         case A00:                                        // p's ╞y is the greatest
  344.             temp = AB[1][0] / AB[0][0];
  345.             AB[1][1] -= temp * AB[0][1];
  346.             AB[1][2] -= temp * AB[0][2];
  347.             if( fabs(AB[1][1]) < 0.0001 )
  348.                 return kNoIntersection;
  349.             secty = AB[1][2] / AB[1][1];
  350.             sectx = (AB[0][2] - AB[0][1]*secty) / AB[0][0];
  351.             break;
  352.         case A01:                                        // p's ╞x is the greatest
  353.             temp = AB[1][1] / AB[0][1];
  354.             AB[1][0] -= temp * AB[0][0];
  355.             AB[1][2] -= temp * AB[0][2];
  356.             if( fabs(AB[1][0]) < 0.0001 )
  357.                 return kNoIntersection;
  358.             sectx = AB[1][2] / AB[1][0];
  359.             secty = (AB[0][2] - AB[0][0]*sectx) / AB[0][1];
  360.             break;
  361.         case A10:                                        // q's ╞y is the greatest
  362.             temp = AB[0][0] / AB[1][0];
  363.             AB[0][1] -= temp * AB[1][1];
  364.             AB[0][2] -= temp * AB[1][2];
  365.             if( fabs(AB[0][1]) < 0.0001 )
  366.                 return kNoIntersection;
  367.             secty =  AB[0][2] / AB[0][1];
  368.             sectx = (AB[1][2] - AB[1][1]*secty) / AB[1][0];
  369.             break;
  370.         case A11:                                        // q's ╞x is the greatest
  371.             temp = AB[0][1] / AB[1][1];
  372.             AB[0][0] -= temp * AB[1][0];
  373.             AB[0][2] -= temp * AB[1][2];
  374.             if( fabs(AB[0][0]) < 0.0001 )
  375.                 return kNoIntersection;
  376.             sectx = AB[0][2] / AB[0][0];
  377.             secty = (AB[1][2] - AB[1][0]*sectx) / AB[1][1];
  378.             break;
  379.     }
  380.     
  381.     if( fabs(sectx)>32767.0 || fabs(secty)>32767.0 )
  382.         return kNoIntersection;
  383.     sect->x = ODFloatToFixed(sectx);
  384.     sect->y = ODFloatToFixed(secty);
  385.     
  386.     // Check whether the intersection is between endpoints of p and q.
  387.     // Use max delta of p and q to test for inclusion:
  388.     ODBoolean inside;
  389.     if( pwhich==A00 )
  390.         inside = InRange(sect->y, p0.y,p1.y);
  391.     else
  392.         inside = InRange(sect->x, p0.x,p1.x);
  393.     if( inside )
  394.         if( qwhich==A11 )
  395.             inside = InRange(sect->x, q0.x,q1.x);
  396.         else
  397.             inside = InRange(sect->y, q0.y,q1.y);
  398.  
  399.     if( inside )
  400.         return kIntersection;
  401.     else
  402.         return kOutsideIntersection;
  403.     
  404. }
  405.  
  406.     // ORIGINAL FIXED-POINT VERSION:
  407.     IntersectionStatus
  408.     IntersectLines( const ODPoint &p0, const ODPoint &p1,
  409.                     const ODPoint &q0, const ODPoint &q1,
  410.                     ODPoint *sect )
  411.     {
  412.         ODCoordinate temp;
  413.         
  414.         // Construct the augmented matrix:
  415.         
  416.         ODCoordinate AB[2][3];
  417.         AB[0][0] = p1.y - p0.y;
  418.         AB[0][1] = p0.x - p1.x;
  419.         AB[0][2] = FixMul(AB[0][0],p0.x) + FixMul(AB[0][1],p0.y);
  420.         
  421.         AB[1][0] = q1.y - q0.y;
  422.         AB[1][1] = q0.x - q1.x;
  423.         AB[1][2] = FixMul(AB[1][0],q0.x) + FixMul(AB[1][1],q0.y);
  424.         
  425.         // Find the largest element (in absolute value):
  426.     
  427.         ODCoordinate pmax = Abs(AB[0][0]);
  428.         char pwhich = A00;
  429.         temp = Abs(AB[0][1]);
  430.         if( temp>pmax ) {
  431.             pmax = temp;
  432.             pwhich = A01;
  433.         }
  434.     
  435.         ODCoordinate qmax = Abs(AB[1][0]);
  436.         char qwhich = A10;
  437.         temp = Abs(AB[1][1]);
  438.         if( temp>qmax ) {
  439.             qmax = temp;
  440.             qwhich = A11;
  441.         }
  442.         
  443.         ODCoordinate max;
  444.         char which;
  445.         if( pmax > qmax ) {
  446.             max = pmax;
  447.             which = pwhich;
  448.         } else {
  449.             max = qmax;
  450.             which = qwhich;
  451.         }
  452.         
  453.         // Give up if entire matrix is zero (we were given two degenerate line segments)
  454.         if( max==0 )
  455.             return kNoIntersection;
  456.         
  457.         // Pivot around the largest element and back-substitute. If we're about to divide
  458.         // by zero, this means the two lines are parallel (or one segment is degenerate.)
  459.         
  460.         switch( which ) {
  461.             case A00:                                        // p's ╞y is the greatest
  462.                 temp = ODFractDivide(AB[1][0],AB[0][0]);
  463.                 AB[1][1] -= FracMul(temp, AB[0][1]);
  464.                 AB[1][2] -= FracMul(temp, AB[0][2]);
  465.                 if( AB[1][1]==0 )
  466.                     return kNoIntersection;
  467.                 sect->y = FixDiv(AB[1][2], AB[1][1]);
  468.                 sect->x = FixDiv(AB[0][2] - FixMul(AB[0][1],sect->y), AB[0][0]);
  469.                 break;
  470.             case A01:                                        // p's ╞x is the greatest
  471.                 temp = ODFractDivide(AB[1][1],AB[0][1]);
  472.                 AB[1][0] -= FracMul(temp, AB[0][0]);
  473.                 AB[1][2] -= FracMul(temp, AB[0][2]);
  474.                 if( AB[1][0]==0 )
  475.                     return kNoIntersection;
  476.                 sect->x = FixDiv(AB[1][2], AB[1][0]);
  477.                 sect->y = FixDiv(AB[0][2] - FixMul(AB[0][0],sect->x), AB[0][1]);
  478.                 break;
  479.             case A10:                                        // q's ╞y is the greatest
  480.                 temp = ODFractDivide(AB[0][0],AB[1][0]);
  481.                 AB[0][1] -= FracMul(temp, AB[1][1]);
  482.                 AB[0][2] -= FracMul(temp, AB[1][2]);
  483.                 if( AB[0][1]==0 )
  484.                     return kNoIntersection;
  485.                 sect->y = FixDiv(AB[0][2], AB[0][1]);
  486.                 sect->x = FixDiv(AB[1][2] - FixMul(AB[1][1],sect->y), AB[1][0]);
  487.                 break;
  488.             case A11:                                        // q's ╞x is the greatest
  489.                 temp = ODFractDivide(AB[0][1],AB[1][1]);
  490.                 AB[0][0] -= FracMul(temp, AB[1][0]);
  491.                 AB[0][2] -= FracMul(temp, AB[1][2]);
  492.                 if( AB[0][0]==0 )
  493.                     return kNoIntersection;
  494.                 sect->x = FixDiv(AB[0][2], AB[0][0]);
  495.                 sect->y = FixDiv(AB[1][2] - FixMul(AB[1][0],sect->x), AB[1][1]);
  496.                 break;
  497.         }
  498.         
  499.         // Check whether the intersection is between endpoints of p and q.
  500.         // Use max delta of p and q to test for inclusion:
  501.         ODBoolean inside;
  502.         if( pwhich==A00 )
  503.             inside = InRange(sect->x, p0.x,p1.x);
  504.         else
  505.             inside = InRange(sect->y, p0.y,p1.y);
  506.         if( inside )
  507.             if( qwhich==A11 )
  508.                 inside = InRange(sect->x, q0.x,q1.x);
  509.             else
  510.                 inside = InRange(sect->y, q0.y,q1.y);
  511.     
  512.         if( inside )
  513.             return kIntersection;
  514.         else
  515.             return kOutsideIntersection;
  516.         
  517.     }
  518. #endif // defined(_PLATFORM_WIN32_) || defined(_PLATFORM_OS2_) || defined(_PLATFORM_UNIX_)
  519.  
  520.  
  521. //------------------------------------------------------------------------------
  522. // IntersectSegments
  523. //
  524. // Find the intersection of the two line segments determined by two pairs of points.
  525. // This is often faster than IntersectLines in that it does not bother to compute the
  526. // outside intersection point if the two segments do not intersect. In other words:
  527. // ** sect will only be valid if the function returns true!
  528. //------------------------------------------------------------------------------
  529.  
  530. WIN32_DLLEXPORT ODBoolean
  531. IntersectSegments( const ODPoint &p0, const ODPoint &p1,
  532.                    const ODPoint &q0, const ODPoint &q1,
  533.                    ODPoint *sect )
  534. {
  535.     if( RangesDisjoint(p0.x,p1.x, q0.x,q1.x) || RangesDisjoint(p0.y,p1.y, q0.y,q1.y) )
  536.         return kODFalse;
  537.     else
  538.         return IntersectLines(p0,p1, q0,q1, sect) == kIntersection;
  539. }
  540.  
  541.  
  542. //------------------------------------------------------------------------------
  543. // GetIntersectionT
  544. //
  545. // Determines the "t" value (fractional distance) of a point on a segment.
  546. // This function assumes that sect is a point on the segment (p0,p1).
  547. // It returns 0.0 if sect=p0, 1.0 if sect=p1, and fractional values in between.
  548. //------------------------------------------------------------------------------
  549.  
  550. #ifdef _PLATFORM_MACINTOSH_
  551. Fract
  552. #else
  553. WIN32_DLLEXPORT ODFract
  554. #endif
  555. GetIntersectionT( const ODPoint &p0, const ODPoint &p1, const ODPoint § )
  556. {
  557.     ODCoordinate dx = p1.x - p0.x;
  558.     ODCoordinate dy = p1.y - p0.y;
  559.     
  560.     if( labs(dx) > labs(dy) )
  561.         return ODFractDivide( sect.x-p0.x, dx );            // fixed / fixed = fract
  562.     else
  563.         return ODFractDivide( sect.y-p0.y, dy );
  564. }
  565.  
  566.  
  567. //------------------------------------------------------------------------------
  568. // GetLineXAtY
  569. //
  570. // Determines the x position of a line at a given y position (i.e. the x coord
  571. // of the intersection of the line and an infinite horizontal line at y.)
  572. //------------------------------------------------------------------------------
  573.  
  574. WIN32_DLLEXPORT ODCoordinate
  575. GetLineXAtY( const ODPoint &p0, const ODPoint &p1, ODCoordinate y )
  576. {
  577.     if( p0.x==p1.x )
  578.         return p0.x;                            // Line is vertical
  579.     else if( y==p0.y )
  580.         return p0.x;                            // One endpoint is at y
  581.     else if( y==p1.y )
  582.         return p1.x;                            // Other endpoint is at y
  583.     else {                                        // General case:
  584.         WASSERTMSG_DEBUG(p0.y!=p1.y,"Can't get x intercept of horiz line");
  585.         ODPoint q0 (p0.x,y);
  586.         ODPoint q1 (p1.x,y);
  587.         ODPoint sect;
  588.         IntersectLines(p0,p1,q0,q1,§);
  589.         return sect.x;
  590.     }
  591. }
  592.  
  593.  
  594. //------------------------------------------------------------------------------
  595. // Distance
  596. //
  597. // Returns the distance between two points, or kODFixedInfinity on overflow.
  598. //------------------------------------------------------------------------------
  599.  
  600. WIN32_DLLEXPORT ODCoordinate
  601. Distance( const ODPoint &p0, const ODPoint &p1 )
  602. {
  603.     ODCoordinate dx = p1.x-p0.x;
  604.     ODCoordinate dy = p1.y-p0.y;
  605.     
  606.     // If dx or dy overflow a signed number, then so must the distance:
  607.     if( (p1.x<p0.x) != (dx<0)  ||  (p1.y<p0.y) != (dy<0) )
  608.         return kODFixedInfinity;
  609.     
  610.     if( dx==0 )
  611.         return Abs(dy);
  612.     else if( dy==0 )
  613.         return Abs(dx);
  614.     
  615.     ODWide dx2, dy2;
  616.     ODWideMultiply(dx,dx,&dx2);                        // (16.16)^2 is 32.32
  617.     ODWideMultiply(dy,dy,&dy2);
  618.     ODWideAdd(&dx2,&dy2);
  619.     
  620.     ODCoordinate result = ODWideSquareRoot(&dx2);    // sqrt(32.32) is 16.16!
  621.     if( result >= 0 )
  622.         return result;
  623.     else
  624.         return kODFixedInfinity;                    // Overflow!
  625. }
  626.  
  627.  
  628. //------------------------------------------------------------------------------
  629. // GetLineShift
  630. //
  631. // Return an offset by which to shift points on a line to move them a certain
  632. // distance to the left (in Mac coordinates) parallel to the line.
  633. //------------------------------------------------------------------------------
  634.  
  635. WIN32_DLLEXPORT void
  636. GetLineShift( ODPoint p0, ODPoint p1, ODCoordinate dist, ODPoint &delta )
  637. {
  638.     if( p0.x==p1.x ) {
  639.         if( p1.y<p0.y )
  640.             dist = -dist;
  641.         delta.x = dist;
  642.         delta.y = 0;
  643.         
  644.     } else if( p0.y==p1.y ) {
  645.         if( p1.x>p0.x )
  646.             dist = -dist;
  647.         delta.x = 0;
  648.         delta.y = dist;
  649.         
  650.     } else {
  651.         ODCoordinate len = Distance(p0,p1);
  652.         if( len==kODFixedInfinity ) {
  653.             // Distance overflows, so just scale things down
  654.             p0.x >>= 2;        p0.y >>= 2;
  655.             p1.x >>= 2;        p1.y >>= 2;
  656.             len = Distance(p0,p1);
  657.         }
  658.         ODWide w;
  659.         ODFixed rem;
  660.         ODWideMultiply(dist,p1.y-p0.y, &w);        // delta.x =  (dist*dy)/len
  661.         delta.x = ODWideDivide(&w,len, &rem);
  662.         ODWideMultiply(dist,p0.x-p1.x, &w);        // delta.y = -(dist*dx)/len
  663.         delta.y = ODWideDivide(&w,len, &rem);
  664.     }
  665. }
  666.