home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / odtlktv4.zip / ODTLKT / TOOLKIT / BETA / SAMPLES / OPENDOC / PUBUTILS / LINEOPS.CPP < prev    next >
Text File  |  1995-09-27  |  15KB  |  493 lines
  1. /********************************************************************/
  2. /*  Licensed Materials - Property of IBM                            */
  3. /*                                                                  */
  4. /*                                                                  */
  5. /* Copyright (C) International Business Machines Corp., 1994.       */
  6. /* Copyright (C) Apple Computer, Inc., 1994                         */
  7. /*                                                                  */
  8. /*  US Government Users Restricted Rights -                         */
  9. /*  Use, duplication, or disclosure restricted                      */
  10. /*  by GSA ADP Schedule Contract with IBM Corp.                     */
  11. /*                                                                  */
  12. /*  File:    LineOps.cpp                                            */
  13. /*                                                                  */
  14. /*  Contains:  Geometric operations on lines in 2-space.            */
  15. /*                                                                  */
  16. /********************************************************************/
  17.  
  18. #define INCL_GPITRANSFORMS
  19. #include <os2.h>
  20.  
  21. #ifndef _ALTPOINT_
  22. #include "AltPoint.h"      // Use C++ savvy ODPoint and ODRect
  23. #endif
  24.  
  25. #include "LineOps.h"
  26.  
  27. #ifndef _EXCEPT_
  28. #include "Except.h"
  29. #endif
  30.  
  31. #ifndef _ODDEBUG_
  32. #include "ODDebug.h"
  33. #endif
  34.  
  35. #ifndef _ODMATH_
  36. #include "ODMath.h"
  37. #endif
  38.  
  39. #include <stdlib.h>
  40.  
  41. #include <math.h>
  42.  
  43.  
  44. enum{
  45.   A00, A01, A10, A11
  46. };
  47. #define double_t  double
  48.  
  49. //------------------------------------------------------------------------------
  50. // WithinEpsilon
  51. //
  52. // Returns true if the two numbers are within kEpsilon of each other.
  53. //------------------------------------------------------------------------------
  54.  
  55. ODBoolean
  56. WithinEpsilon( ODCoordinate a, ODCoordinate b )
  57. {
  58.   ODCoordinate diff = a-b;
  59.   return diff<=kFixedEpsilon && diff>=-kFixedEpsilon;
  60. }
  61.  
  62.  
  63.  
  64. //------------------------------------------------------------------------------
  65. // InRange
  66. //
  67. // Determine whether n falls within the range [r0,r1].
  68. // The r's need not be given in order. Unline rects, endpoints are included.
  69. //------------------------------------------------------------------------------
  70.  
  71. ODBoolean
  72. InRange( ODCoordinate n,  ODCoordinate r0, ODCoordinate r1 )
  73. {
  74.   if( r0<r1 )
  75.     return n>=r0 && n<=r1;
  76.   else
  77.     return n>=r1 && n<=r0;
  78. }
  79.  
  80.  
  81. //------------------------------------------------------------------------------
  82. // RangesDisjoint
  83. //
  84. // Determine whether two ranges do not overlap. They needn't be given in order.
  85. //------------------------------------------------------------------------------
  86.  
  87. ODBoolean
  88. RangesDisjoint( ODCoordinate a0, ODCoordinate a1,
  89.         ODCoordinate b0, ODCoordinate b1 )
  90. {
  91.   if( a0<a1 )
  92.     return Max(b0,b1) < a0  ||  a1 < Min(b0,b1);
  93.   else
  94.     return Max(b0,b1) < a1  ||  a0 < Min(b0,b1);
  95. }
  96.  
  97.  
  98. //------------------------------------------------------------------------------
  99. // IntersectLines            by Ken Turkowski, tweaked by Jens Alfke
  100. //
  101. // Find the intersection of the two lines determined by two pairs of points.
  102. // Returns:  kIntersection if the two segments intersect;
  103. //      kOutsideIntersection if the lines intersect beyond the ends of the segments;
  104. //      kNoIntersection if the lines are parallel, coincident or degenerate.
  105. //            (In this last case sect will not be valid.)
  106. //------------------------------------------------------------------------------
  107.  
  108. IntersectionStatus
  109. IntersectLines( const ODPoint &p0, const ODPoint &p1,
  110.           const ODPoint &q0, const ODPoint &q1,
  111.           ODPoint *sect )
  112. {
  113.   double_t temp;
  114.   double_t p0x = ODFixedToFloat(p0.x);
  115.   double_t p0y = ODFixedToFloat(p0.y);
  116.   double_t p1x = ODFixedToFloat(p1.x);
  117.   double_t p1y = ODFixedToFloat(p1.y);
  118.   double_t q0x = ODFixedToFloat(q0.x);
  119.   double_t q0y = ODFixedToFloat(q0.y);
  120.   double_t q1x = ODFixedToFloat(q1.x);
  121.   double_t q1y = ODFixedToFloat(q1.y);
  122.  
  123.   // Construct the augmented matrix:
  124.  
  125.   double_t AB[2][3];
  126.   AB[0][0] = p1y - p0y;
  127.   AB[0][1] = p0x - p1x;
  128.   AB[0][2] = AB[0][0]*p0x + AB[0][1]*p0y;
  129.  
  130.   AB[1][0] = q1y - q0y;
  131.   AB[1][1] = q0x - q1x;
  132.   AB[1][2] = AB[1][0]*q0x + AB[1][1]*q0y;
  133.  
  134.   // Find the largest element (in absolute value):
  135.  
  136.   double_t pmax = fabs(AB[0][0]);
  137.   char pwhich = A00;
  138.   temp = fabs(AB[0][1]);
  139.   if( temp>pmax ) {
  140.     pmax = temp;
  141.     pwhich = A01;
  142.   }
  143.  
  144.   double_t qmax = fabs(AB[1][0]);
  145.   char qwhich = A10;
  146.   temp = fabs(AB[1][1]);
  147.   if( temp>qmax ) {
  148.     qmax = temp;
  149.     qwhich = A11;
  150.   }
  151.  
  152.   double_t max;
  153.   char which;
  154.   if( pmax > qmax ) {
  155.     max = pmax;
  156.     which = pwhich;
  157.   } else {
  158.     max = qmax;
  159.     which = qwhich;
  160.   }
  161.  
  162.   // Give up if entire matrix is zero (we were given two degenerate line segments)
  163.   if( max==0 )
  164.     return kNoIntersection;
  165.  
  166.   // Pivot around the largest element and back-substitute. If we're about to divide
  167.   // by zero, this means the two lines are parallel (or one segment is degenerate.)
  168.  
  169.   double_t sectx, secty;
  170.  
  171.   switch( which ) {
  172.     case A00:                    // p's ╞y is the greatest
  173.       temp = AB[1][0] / AB[0][0];
  174.       AB[1][1] -= temp * AB[0][1];
  175.       AB[1][2] -= temp * AB[0][2];
  176.       if( fabs(AB[1][1]) < 0.0001 )
  177.         return kNoIntersection;
  178.       secty = AB[1][2] / AB[1][1];
  179.       sectx = (AB[0][2] - AB[0][1]*secty) / AB[0][0];
  180.       break;
  181.     case A01:                    // p's ╞x is the greatest
  182.       temp = AB[1][1] / AB[0][1];
  183.       AB[1][0] -= temp * AB[0][0];
  184.       AB[1][2] -= temp * AB[0][2];
  185.       if( fabs(AB[1][0]) < 0.0001 )
  186.         return kNoIntersection;
  187.       sectx = AB[1][2] / AB[1][0];
  188.       secty = (AB[0][2] - AB[0][0]*sectx) / AB[0][1];
  189.       break;
  190.     case A10:                    // q's ╞y is the greatest
  191.       temp = AB[0][0] / AB[1][0];
  192.       AB[0][1] -= temp * AB[1][1];
  193.       AB[0][2] -= temp * AB[1][2];
  194.       if( fabs(AB[0][1]) < 0.0001 )
  195.         return kNoIntersection;
  196.       secty =  AB[0][2] / AB[0][1];
  197.       sectx = (AB[1][2] - AB[1][1]*secty) / AB[1][0];
  198.       break;
  199.     case A11:                    // q's ╞x is the greatest
  200.       temp = AB[0][1] / AB[1][1];
  201.       AB[0][0] -= temp * AB[1][0];
  202.       AB[0][2] -= temp * AB[1][2];
  203.       if( fabs(AB[0][0]) < 0.0001 )
  204.         return kNoIntersection;
  205.       sectx = AB[0][2] / AB[0][0];
  206.       secty = (AB[1][2] - AB[1][0]*sectx) / AB[1][1];
  207.       break;
  208.   }
  209.  
  210.   if( fabs(sectx)>32767.0 || fabs(secty)>32767.0 )
  211.     return kNoIntersection;
  212.   sect->x = ODFloatToFixed(sectx);
  213.   sect->y = ODFloatToFixed(secty);
  214.  
  215.   // Check whether the intersection is between endpoints of p and q.
  216.   // Use max delta of p and q to test for inclusion:
  217.   ODBoolean inside;
  218.   if( pwhich==A00 )
  219.     inside = InRange(sect->y, p0.y,p1.y);
  220.   else
  221.     inside = InRange(sect->x, p0.x,p1.x);
  222.   if( inside )
  223.     if( qwhich==A11 )
  224.       inside = InRange(sect->x, q0.x,q1.x);
  225.     else
  226.       inside = InRange(sect->y, q0.y,q1.y);
  227.  
  228.   if( inside )
  229.     return kIntersection;
  230.   else
  231.     return kOutsideIntersection;
  232.  
  233. }
  234.  
  235.  
  236. #if 0
  237.   // ORIGINAL FIXED-POINT VERSION:
  238.   IntersectionStatus
  239.   IntersectLines( const ODPoint &p0, const ODPoint &p1,
  240.             const ODPoint &q0, const ODPoint &q1,
  241.             ODPoint *sect )
  242.   {
  243.     ODCoordinate temp;
  244.  
  245.     // Construct the augmented matrix:
  246.  
  247.     ODCoordinate AB[2][3];
  248.     AB[0][0] = p1.y - p0.y;
  249.     AB[0][1] = p0.x - p1.x;
  250.     AB[0][2] = FixMul(AB[0][0],p0.x) + FixMul(AB[0][1],p0.y);
  251.  
  252.     AB[1][0] = q1.y - q0.y;
  253.     AB[1][1] = q0.x - q1.x;
  254.     AB[1][2] = FixMul(AB[1][0],q0.x) + FixMul(AB[1][1],q0.y);
  255.  
  256.     // Find the largest element (in absolute value):
  257.  
  258.     ODCoordinate pmax = Abs(AB[0][0]);
  259.     char pwhich = A00;
  260.     temp = Abs(AB[0][1]);
  261.     if( temp>pmax ) {
  262.       pmax = temp;
  263.       pwhich = A01;
  264.     }
  265.  
  266.     ODCoordinate qmax = Abs(AB[1][0]);
  267.     char qwhich = A10;
  268.     temp = Abs(AB[1][1]);
  269.     if( temp>qmax ) {
  270.       qmax = temp;
  271.       qwhich = A11;
  272.     }
  273.  
  274.     ODCoordinate max;
  275.     char which;
  276.     if( pmax > qmax ) {
  277.       max = pmax;
  278.       which = pwhich;
  279.     } else {
  280.       max = qmax;
  281.       which = qwhich;
  282.     }
  283.  
  284.     // Give up if entire matrix is zero (we were given two degenerate line segments)
  285.     if( max==0 )
  286.       return kNoIntersection;
  287.  
  288.     // Pivot around the largest element and back-substitute. If we're about to divide
  289.     // by zero, this means the two lines are parallel (or one segment is degenerate.)
  290.  
  291.     switch( which ) {
  292.       case A00:                    // p's ╞y is the greatest
  293.         temp = ODFractDivide(AB[1][0],AB[0][0]);
  294.         AB[1][1] -= FracMul(temp, AB[0][1]);
  295.         AB[1][2] -= FracMul(temp, AB[0][2]);
  296.         if( AB[1][1]==0 )
  297.           return kNoIntersection;
  298.         sect->y = FixDiv(AB[1][2], AB[1][1]);
  299.         sect->x = FixDiv(AB[0][2] - FixMul(AB[0][1],sect->y), AB[0][0]);
  300.         break;
  301.       case A01:                    // p's ╞x is the greatest
  302.         temp = ODFractDivide(AB[1][1],AB[0][1]);
  303.         AB[1][0] -= FracMul(temp, AB[0][0]);
  304.         AB[1][2] -= FracMul(temp, AB[0][2]);
  305.         if( AB[1][0]==0 )
  306.           return kNoIntersection;
  307.         sect->x = FixDiv(AB[1][2], AB[1][0]);
  308.         sect->y = FixDiv(AB[0][2] - FixMul(AB[0][0],sect->x), AB[0][1]);
  309.         break;
  310.       case A10:                    // q's ╞y is the greatest
  311.         temp = ODFractDivide(AB[0][0],AB[1][0]);
  312.         AB[0][1] -= FracMul(temp, AB[1][1]);
  313.         AB[0][2] -= FracMul(temp, AB[1][2]);
  314.         if( AB[0][1]==0 )
  315.           return kNoIntersection;
  316.         sect->y = FixDiv(AB[0][2], AB[0][1]);
  317.         sect->x = FixDiv(AB[1][2] - FixMul(AB[1][1],sect->y), AB[1][0]);
  318.         break;
  319.       case A11:                    // q's ╞x is the greatest
  320.         temp = ODFractDivide(AB[0][1],AB[1][1]);
  321.         AB[0][0] -= FracMul(temp, AB[1][0]);
  322.         AB[0][2] -= FracMul(temp, AB[1][2]);
  323.         if( AB[0][0]==0 )
  324.           return kNoIntersection;
  325.         sect->x = FixDiv(AB[0][2], AB[0][0]);
  326.         sect->y = FixDiv(AB[1][2] - FixMul(AB[1][0],sect->x), AB[1][1]);
  327.         break;
  328.     }
  329.  
  330.     // Check whether the intersection is between endpoints of p and q.
  331.     // Use max delta of p and q to test for inclusion:
  332.     ODBoolean inside;
  333.     if( pwhich==A00 )
  334.       inside = InRange(sect->x, p0.x,p1.x);
  335.     else
  336.       inside = InRange(sect->y, p0.y,p1.y);
  337.     if( inside )
  338.       if( qwhich==A11 )
  339.         inside = InRange(sect->x, q0.x,q1.x);
  340.       else
  341.         inside = InRange(sect->y, q0.y,q1.y);
  342.  
  343.     if( inside )
  344.       return kIntersection;
  345.     else
  346.       return kOutsideIntersection;
  347.  
  348.   }
  349. #endif
  350.  
  351.  
  352. //------------------------------------------------------------------------------
  353. // IntersectSegments
  354. //
  355. // Find the intersection of the two line segments determined by two pairs of points.
  356. // This is often faster than IntersectLines in that it does not bother to compute the
  357. // outside intersection point if the two segments do not intersect. In other words:
  358. // ** sect will only be valid if the function returns true!
  359. //------------------------------------------------------------------------------
  360.  
  361. ODBoolean
  362. IntersectSegments( const ODPoint &p0, const ODPoint &p1,
  363.            const ODPoint &q0, const ODPoint &q1,
  364.            ODPoint *sect )
  365. {
  366.   if( RangesDisjoint(p0.x,p1.x, q0.x,q1.x) || RangesDisjoint(p0.y,p1.y, q0.y,q1.y) )
  367.     return kODFalse;
  368.   else
  369.     return IntersectLines(p0,p1, q0,q1, sect) == kIntersection;
  370. }
  371.  
  372.  
  373. //------------------------------------------------------------------------------
  374. // GetIntersectionT
  375. //
  376. // Determines the "t" value (fractional distance) of a point on a segment.
  377. // This function assumes that sect is a point on the segment (p0,p1).
  378. // It returns 0.0 if sect=p0, 1.0 if sect=p1, and fractional values in between.
  379. //------------------------------------------------------------------------------
  380.  
  381. ODFract
  382. GetIntersectionT( const ODPoint &p0, const ODPoint &p1, const ODPoint § )
  383. {
  384.   ODCoordinate dx = p1.x - p0.x;
  385.   ODCoordinate dy = p1.y - p0.y;
  386.  
  387.   if( labs(dx) > labs(dy) )
  388.     return ODFractDivide( sect.x-p0.x, dx );      // fixed / fixed = fract
  389.   else
  390.     return ODFractDivide( sect.y-p0.y, dy );
  391. }
  392.  
  393.  
  394. //------------------------------------------------------------------------------
  395. // GetLineXAtY
  396. //
  397. // Determines the x position of a line at a given y position (i.e. the x coord
  398. // of the intersection of the line and an infinite horizontal line at y.)
  399. //------------------------------------------------------------------------------
  400.  
  401. ODCoordinate
  402. GetLineXAtY( const ODPoint &p0, const ODPoint &p1, ODCoordinate y )
  403. {
  404.   if( p0.x==p1.x )
  405.     return p0.x;              // Line is vertical
  406.   else if( y==p0.y )
  407.     return p0.x;              // One endpoint is at y
  408.   else if( y==p1.y )
  409.     return p1.x;              // Other endpoint is at y
  410.   else {                    // General case:
  411.     WASSERTM(p0.y!=p1.y,"Can't get x intercept of horiz line");
  412.     ODPoint q0 (p0.x,y);
  413.     ODPoint q1 (p1.x,y);
  414.     ODPoint sect;
  415.     IntersectLines(p0,p1,q0,q1,§);
  416.     return sect.x;
  417.   }
  418. }
  419.  
  420.  
  421. //------------------------------------------------------------------------------
  422. // Distance
  423. //
  424. // Returns the distance between two points, or kODFixedInfinity on overflow.
  425. //------------------------------------------------------------------------------
  426.  
  427. ODCoordinate
  428. Distance( const ODPoint &p0, const ODPoint &p1 )
  429. {
  430.   ODCoordinate dx = p1.x-p0.x;
  431.   ODCoordinate dy = p1.y-p0.y;
  432.  
  433.   // If dx or dy overflow a signed number, then so must the distance:
  434.   if( (p1.x<p0.x) != (dx<0)  ||  (p1.y<p0.y) != (dy<0) )
  435.     return kODFixedInfinity;
  436.  
  437.   if( dx==0 )
  438.     return Abs(dy);
  439.   else if( dy==0 )
  440.     return Abs(dx);
  441.  
  442.   ODWide dx2, dy2;
  443.   ODWideMultiply(dx,dx,&dx2);            // (16.16)^2 is 32.32
  444.   ODWideMultiply(dy,dy,&dy2);
  445.   ODWideAdd(&dx2,&dy2);
  446.  
  447.   ODCoordinate result = ODWideSquareRoot(&dx2);  // sqrt(32.32) is 16.16!
  448.   if( result >= 0 )
  449.     return result;
  450.   else
  451.     return kODFixedInfinity;          // Overflow!
  452. }
  453.  
  454.  
  455. //------------------------------------------------------------------------------
  456. // GetLineShift
  457. //
  458. // Return an offset by which to shift points on a line to move them a certain
  459. // distance to the left (in Mac coordinates) parallel to the line.
  460. //------------------------------------------------------------------------------
  461.  
  462. void
  463. GetLineShift( ODPoint p0, ODPoint p1, ODCoordinate dist, ODPoint &delta )
  464. {
  465.   if( p0.x==p1.x ) {
  466.     if( p1.y<p0.y )
  467.       dist = -dist;
  468.     delta.x = dist;
  469.     delta.y = 0;
  470.  
  471.   } else if( p0.y==p1.y ) {
  472.     if( p1.x>p0.x )
  473.       dist = -dist;
  474.     delta.x = 0;
  475.     delta.y = dist;
  476.  
  477.   } else {
  478.     ODCoordinate len = Distance(p0,p1);
  479.     if( len==kODFixedInfinity ) {
  480.       // Distance overflows, so just scale things down
  481.       p0.x >>= 2;    p0.y >>= 2;
  482.       p1.x >>= 2;    p1.y >>= 2;
  483.       len = Distance(p0,p1);
  484.     }
  485.     ODWide w;
  486.     ODFixed rem;
  487.     ODWideMultiply(dist,p1.y-p0.y, &w);    // delta.x =  (dist*dy)/len
  488.     delta.x = ODWideDivide(&w,len, &rem);
  489.     ODWideMultiply(dist,p0.x-p1.x, &w);    // delta.y = -(dist*dx)/len
  490.     delta.y = ODWideDivide(&w,len, &rem);
  491.   }
  492. }
  493.