home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 October: Mac OS SDK / Dev.CD Oct 96 SDK / Dev.CD Oct 96 SDK2.toast / Development Kits (Disc 2) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc Source Code / Imaging / PolygonClipper / PolyClip.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1996-04-22  |  9.5 KB  |  363 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        PolyClip.cpp
  3.  
  4.     Contains:    The polygon clipper! Performs intersection, union, difference.
  5.  
  6.     Owned by:    Jens Alfke (based on algorithm by A. C. Kilgour)
  7.  
  8.     Copyright:    © 1994 - 1995 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     Change History (most recent first):
  11.     
  12.         <10>     8/18/95    NP        1274946: Remove kODErrInvalidParameter
  13.          <9>     8/16/95    NP        1274946: ErrorDef.idl problems. Add include
  14.                                     file.
  15.          <8>     5/25/95    jpa        Fixed 'for' loop for ANSI compliance
  16.                                     [1253324]
  17.          <7>     4/15/95    jpa        Weakened post-clip bbox assertion for union
  18.                                     [1233290]
  19.          <6>     3/22/95    jpa        Use Approx... methods when testing bounding
  20.                                     boxes at end of clipping [1186959]. Added
  21.                                     aet param to MergeWith [1230776]. Generate
  22.                                     correct PolyDump filenames. Set version to
  23.                                     3.
  24.          <5>      1/6/95    jpa        Truncate PolyDump filename to 31 chars.
  25.                                     [1207604]
  26.          <4>     12/5/94    jpa        Made DumpPolygons more xplatform
  27.                                     compatible. Added version # to dump.
  28.          <3>    10/24/94    jpa        Implemented PolyOutset. [1186719]
  29.          <2>     9/29/94    RA        1189812: Mods for 68K build.
  30.          <1>     6/15/94    jpa        first checked in
  31.          ---------------------------Moved to ODSOM project.
  32.          <2>     5/27/94    jpa        Removed ASLM dependency [1165267]
  33.          <1>      5/9/94    jpa        first checked in
  34.          
  35.     Theory of Operation:
  36.     In Progress:
  37.         
  38. */
  39.  
  40.  
  41. #pragma segment ODPolygonClip
  42.  
  43.  
  44. #ifndef _ALTPOINT_
  45. #include "AltPoint.h"
  46. #endif
  47.  
  48. #ifndef _ALTPOLY_
  49. #include "AltPoly.h"
  50. #endif
  51.  
  52. #ifndef _PGPOLY_
  53. #include "PGPoly.h"
  54. #endif
  55.  
  56. #ifndef _PGEDGE_
  57. #include "PGEdge.h"
  58. #endif
  59.  
  60. #ifndef _PGEVENT_
  61. #include "PGEvent.h"
  62. #endif
  63.  
  64. #ifndef _POLYCLIP_
  65. #include "PolyClip.h"
  66. #endif
  67.  
  68. #ifndef _LINEOPS_
  69. #include "LineOps.h"
  70. #endif
  71.  
  72. #ifndef _ODDEBUG_
  73. #include "ODDebug.h"
  74. #endif
  75.  
  76. #ifndef _UTILERRS_
  77. #include "UtilErrs.h"
  78. #endif
  79.  
  80. #include <string.h>
  81.  
  82.  
  83. const short kPolyClipVersion = 3;
  84. /*    Version 1:            As of 10/27/94.
  85.     Version 2:             Fixes from Chuck Dumont. Code tweaks from Imaging code-review.
  86.     Version 3: 3/21/95: Another Chuck D. fix to PGEdge::TestPoint.
  87.                         Use approx bbox testing at end of clip. [1186959]
  88.                         Fix to PGEvent::MergeWith [1230776]
  89. */
  90.  
  91. #if ODDebug
  92. #define ODDebugPolyClip 1
  93. #else
  94. #define ODDebugPolyClip 0
  95. #endif
  96.  
  97.  
  98. ODSLong gMinWrap, gMaxWrap;
  99.  
  100.  
  101. #if ODDebugPolyClip
  102.  
  103.     #ifndef __ODMATH__
  104.     #include "ODMath.h"
  105.     #endif
  106.     #include <stdio.h>
  107.     #include <strings.h>
  108.     #include <time.h>
  109.     
  110.     static void
  111.     DumpPolygons( ODSLong errorCode, ODSLong nPolys, const ODPolygon* polys[], ODShapeOp op )
  112.     {
  113.         static const char *kOpStr[3] = {"kShapeIntersection", "kShapeUnion", "kShapeDifference"};
  114.     
  115.         WARN("Error %ld while clipping. About to dump",errorCode);
  116.     
  117.         char fileName[64];
  118.         time_t ltime;
  119.         time(<ime);
  120.         sprintf(fileName, "PolyDump%s", ctime(<ime));
  121.         fileName[31] = '\0';        // Truncate to 31 chars
  122.         char c;
  123.         int i;
  124.         for( i=0; (c=fileName[i])!=0; i++ )
  125.         if( c==':' )
  126.             fileName[i] = '.';      // Replace : with .
  127.         FILE *fil = fopen(fileName, "w+");
  128.         WASSERTM(fil!=kODNULL,"Couldn't open PolyDump file");
  129.         
  130.         fprintf(fil,"# OpenDoc polygon clipper version %d compiled %s\n",kPolyClipVersion,__DATE__);
  131.         fprintf(fil,"# Error %ld on %\n",errorCode,ctime(<ime));
  132.         fprintf(fil,"# %s on %d polygons\n\n",kOpStr[op], nPolys);
  133.     
  134.         fprintf(fil,"%d\n\n%d",(int)op,nPolys);
  135.         for( i=0; i<nPolys; i++ ) {
  136.             const ODPolygon &p = *polys[i];
  137.             fprintf(fil,"\n\n%d",p.GetNContours());
  138.             const ODContour *c = p.FirstContour();
  139.             for( int j=0; j<p.GetNContours(); j++ ) {
  140.                 fprintf(fil,"\n%d   ",c->nVertices);
  141.                 for( int k=0; k<c->nVertices; k++ ) {
  142.                     fprintf(fil," %6.2f,%6.2f", (float)ODFixedToFloat(c->vertex[k].x),
  143.                                                 (float)ODFixedToFloat(c->vertex[k].y));
  144.                 }
  145.                 c = c->NextContour();
  146.             }
  147.         }
  148.         fprintf(fil, "\n\n\n");
  149.         fclose(fil);
  150.     #ifdef _PLATFORM_MACINTOSH_
  151.         FlushVol(NULL,0);
  152.     #endif
  153.     }
  154. #endif
  155.  
  156.  
  157. ODBoolean
  158. PolyOutset( ODPolygon &poly, ODCoordinate dist )
  159. {
  160.     // This operation does NOT simplify the polygon! However, it returns True if the
  161.     // result needs [additional] simplification to remove degenerate edges or contours.
  162.     
  163.     ODULong i=poly.GetNContours();
  164.     ODBoolean needToSimplify = (i>1);
  165.     ODContour *cont = poly.FirstContour();
  166.     for( ; i>0; i-- ) {
  167.         // Simplify a contour. We work with a consecutive triplet of points, p0..p2.
  168.         // First p0 and p1 are moved perp to p0p1 to produce newp0 and newp10.
  169.         // Then  p1 and p2 are moved perp to p1p2 to produce newp12 and newp2.
  170.         // Then newp0newp10 and newp12newp2 are intersected to produce the new value of p1.
  171.         
  172.         ODULong n = cont->nVertices;
  173.         if( n<3 ) continue;
  174.         ODPoint newp0 = cont->vertex[n-2];
  175.         ODPoint *p1 = &cont->vertex[n-1];
  176.         ODPoint *p2 = &cont->vertex[0];
  177.         ODPoint delta, newp10;
  178.         GetLineShift(newp0,*p1,dist, delta);
  179.         newp0.x += delta.x;
  180.         newp0.y += delta.y;
  181.         newp10.x = p1->x + delta.x;
  182.         newp10.y = p1->y + delta.y;
  183.         ODPoint origFirstPt = *p1;        // Save for use on last iteration
  184.         
  185.         for( ODULong j=n; j>0; j-- ) {
  186.             ODPoint newp12, newp2;
  187.             
  188.             GetLineShift(*p1,*p2,dist, delta);
  189.             newp12.x = p1->x + delta.x;
  190.             newp12.y = p1->y + delta.y;
  191.             newp2.x = p2->x + delta.x;
  192.             newp2.y = p2->y + delta.y;
  193.             
  194.             // In order to snip off corners that got too sharp, we'd have to
  195.             // do the distance checking shown in Kilgour p.394.
  196.             if( IntersectLines(newp0,newp10, newp12,newp2, p1)                // SHAZAM! Move p1
  197.                             != kOutsideIntersection )
  198.                 needToSimplify = kODTrue;
  199.             
  200.             if( j>1 ) {
  201.                 newp0 = newp12;
  202.                 newp10 = newp2;
  203.                 p1 = p2;
  204.                 if( j>2 )
  205.                     p2++;                    // On last iteration, need to use _original_ value
  206.                 else                        // of the point at p2, not the version in the polygon,
  207.                     p2 = &origFirstPt;        // which was modified during the 1st iteration!
  208.             }
  209.         }
  210.         
  211.         cont = cont->NextContour();
  212.     }
  213.     
  214.     return needToSimplify;
  215. }
  216.  
  217.  
  218. void
  219. PolySimplify( ODPolygon &dstPoly, const ODPolygon &srcPoly )
  220. {
  221.     const ODPolygon *input = &srcPoly;
  222.     PolyClip(1,&input, kShapeUnion, dstPoly);
  223. }
  224.  
  225.  
  226.  
  227. void
  228. PolyClip( ODSLong nPolys, const ODPolygon* polys[], ODShapeOp op, ODPolygon &output )
  229. {
  230.     ASSERT(nPolys>0, kODErrValueOutOfRange);
  231.     ASSERT(polys!=kODNULL, kODErrIllegalNullInput);
  232.     ASSERT(op>=kShapeIntersection && op<=kShapeDifference, kODErrValueOutOfRange);
  233.     
  234.     PGEventQueue events(20);                // Event queue
  235.     PGEdgeTable aet;                        // Active Edge Table
  236.     PGContourList outputContours;
  237.     gOutputContours = &outputContours;
  238.     
  239.     if( op==kShapeIntersection ) {
  240.         gMinWrap = nPolys;
  241.         gMaxWrap = nPolys; //was 32767; removed by jpa 10/27/94
  242.     } else {
  243.         gMinWrap = gMaxWrap = 1;
  244.     }
  245.     
  246.     TRY{
  247.     
  248.     // Preprocess input polygons:
  249.  
  250. #if LOGGING
  251. //        ClearDebugWindow();
  252.         LOG("BEGIN CLIP: Processing %d polygons, op=%d\n", nPolys,(int)op);
  253. #endif
  254.     
  255.         PGContourList input;
  256.         ODBoolean reverse = kODFalse;
  257.         for( ODSLong i=0; i<nPolys; i++ ) {
  258.             LOG("INPUT polygon #%ld:\n",i);
  259.             input.ReadPolygon(*polys[i],reverse,events);
  260.             if( op==kShapeDifference )
  261.                 reverse = kODTrue;
  262.         }
  263.         
  264.         // Process all events in order from top to bottom:
  265.         
  266.         while( !events.IsEmpty() ) {
  267.             PGEvent *ev = events.RmvFirst();            // Get next event
  268.     
  269.             LOG("\n* Processing event at (%.2f,%.2f):\n", ev->x/65536.0,ev->y/65536.0);
  270.     
  271.             for(;;){
  272.                 PGEvent *evNext = events.First();
  273.                 if( evNext && *ev == *evNext ) {        // While equal to next...
  274.                     LOG("= Merged with next event.\n");
  275.                     events.RmvFirst();
  276.                     ev->MergeWith(evNext,aet);            // ...merge with next
  277.                 } else
  278.                     break;
  279.             }
  280.             
  281.             if( LOGGING ) {                                // Dump AET if logging:
  282.                 BEGINLOG;
  283.                 LOG("  AET =");
  284.                 for( Link *l=aet.First(); l; l=aet.After(*l) ) {
  285.                     PGEdge *e = (PGEdge*)l;
  286.                     ODCoordinate x;
  287.                     if( e->fHighVert->y == e->fLowVert->y )
  288.                         x = ev->x;        // horizontal
  289.                     else
  290.                         x = GetLineXAtY(*e->fHighVert,*e->fLowVert,ev->y);
  291.                     if( e->fRightBundle && !e->fLeftBundle )
  292.                         LOG(" {");
  293.                     LOG(" %.2f[%c%c%d]", x/65536.0,
  294.                                          e->fSense>0?'v':'^',
  295.                                          e->fSide==kLeft?'l':'r',
  296.                                          e->fWrapNo);
  297.                     if( e->fLeftBundle )
  298.                         if( e->fRightBundle )
  299.                             LOG(" =");
  300.                         else
  301.                             LOG(" }");
  302.                 }
  303.                 LOG("\n");
  304.                 ENDLOG;
  305.             }
  306.             
  307.             PGASSERT( (aet.Count() & 1) == 0 );            // Must have even # of edges in aet!
  308.             
  309.             ev->Process(aet,events);                    // Process event
  310.             delete ev;
  311.         }
  312.         
  313.         // Convert output into ODPolygon and return it:
  314.         
  315.         input.DeleteAllLinks();
  316.         
  317.         outputContours.BuildPolygon(output);
  318.         outputContours.DeleteAllLinks();
  319.         
  320.         if( ODDebug ) {
  321.             // Check the bounding boxes to make sure they make sense:
  322.             ODRect inBounds, outBounds;
  323.             output.ComputeBoundingBox(&outBounds);
  324.             polys[0]->ComputeBoundingBox(&inBounds);
  325.             if( op==kShapeDifference )
  326.                 PGASSERT(inBounds.ApproxContains(outBounds));
  327.             else {
  328.                 for( int i=1; i<nPolys; i++ ) {
  329.                     ODRect polyBounds;
  330.                     polys[i]->ComputeBoundingBox(&polyBounds);
  331.                     if( op==kShapeIntersection )
  332.                         inBounds &= polyBounds;
  333.                     else
  334.                         inBounds |= polyBounds;
  335.                 }
  336.                 
  337.                 // **** After a union the outBounds should equal the inBounds.
  338.                 // However Thomas has come up with one very complex case where it
  339.                 // doesn't. I need to investigate this; in the meantime, shoving
  340.                 // kODTrue in here will turn off the warning.  --jpa 4/15/95
  341.                 if( kODTrue /*op==kShapeIntersection*/ )
  342.                     PGASSERT(inBounds.ApproxContains(outBounds));
  343.                 else
  344.                     PGASSERT(inBounds.ApproxEquals(outBounds));
  345.             }
  346.         }
  347.  
  348.     }CATCH_ALL{
  349. #if ODDebugPolyClip
  350.         // Something went wrong during clipping. Dump the input polygons, and set the
  351.         // output to be a copy of the first input polygon. Do not propagate the failure!
  352.         // This should keep things limping along although things may look weird onscreen.
  353.         DumpPolygons(ErrorCode(),nPolys,polys,op);
  354.         output.CopyFrom(*polys[0]);
  355.         // Fall through and return...
  356. #else
  357.         RERAISE;
  358. #endif
  359.     }ENDTRY
  360.     
  361.     LOG("DONE clipping\n");
  362. }
  363.