You can subscribe to this list here.
2000 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}
(33) 
_{Jun}

_{Jul}
(30) 
_{Aug}
(2) 
_{Sep}

_{Oct}
(30) 
_{Nov}
(136) 
_{Dec}
(59) 

2001 
_{Jan}
(255) 
_{Feb}
(169) 
_{Mar}
(322) 
_{Apr}
(185) 
_{May}
(33) 
_{Jun}
(89) 
_{Jul}
(47) 
_{Aug}
(59) 
_{Sep}
(40) 
_{Oct}
(31) 
_{Nov}
(74) 
_{Dec}
(84) 
2002 
_{Jan}
(163) 
_{Feb}
(78) 
_{Mar}
(23) 
_{Apr}
(5) 
_{May}
(22) 
_{Jun}
(75) 
_{Jul}
(143) 
_{Aug}
(48) 
_{Sep}
(111) 
_{Oct}
(58) 
_{Nov}
(124) 
_{Dec}
(278) 
2003 
_{Jan}
(106) 
_{Feb}
(276) 
_{Mar}
(354) 
_{Apr}
(97) 
_{May}
(14) 
_{Jun}
(3) 
_{Jul}
(7) 
_{Aug}
(21) 
_{Sep}
(83) 
_{Oct}
(110) 
_{Nov}
(3) 
_{Dec}
(119) 
2004 
_{Jan}
(318) 
_{Feb}
(409) 
_{Mar}
(68) 
_{Apr}
(23) 
_{May}
(105) 
_{Jun}
(147) 
_{Jul}
(69) 
_{Aug}
(53) 
_{Sep}
(23) 
_{Oct}
(14) 
_{Nov}
(15) 
_{Dec}
(63) 
2005 
_{Jan}
(146) 
_{Feb}
(69) 
_{Mar}
(157) 
_{Apr}
(127) 
_{May}
(166) 
_{Jun}
(8) 
_{Jul}
(5) 
_{Aug}
(3) 
_{Sep}
(8) 
_{Oct}
(17) 
_{Nov}
(29) 
_{Dec}
(34) 
2006 
_{Jan}
(3) 
_{Feb}
(4) 
_{Mar}
(1) 
_{Apr}
(70) 
_{May}
(241) 
_{Jun}
(82) 
_{Jul}
(344) 
_{Aug}
(196) 
_{Sep}
(87) 
_{Oct}
(57) 
_{Nov}
(121) 
_{Dec}
(86) 
2007 
_{Jan}
(60) 
_{Feb}
(67) 
_{Mar}
(102) 
_{Apr}
(28) 
_{May}
(13) 
_{Jun}
(29) 
_{Jul}
(38) 
_{Aug}
(56) 
_{Sep}
(91) 
_{Oct}
(89) 
_{Nov}
(50) 
_{Dec}
(68) 
2008 
_{Jan}
(87) 
_{Feb}
(47) 
_{Mar}
(100) 
_{Apr}
(34) 
_{May}
(65) 
_{Jun}
(54) 
_{Jul}
(98) 
_{Aug}
(128) 
_{Sep}
(109) 
_{Oct}
(141) 
_{Nov}
(40) 
_{Dec}
(206) 
2009 
_{Jan}
(176) 
_{Feb}
(226) 
_{Mar}
(134) 
_{Apr}
(84) 
_{May}
(152) 
_{Jun}
(85) 
_{Jul}
(91) 
_{Aug}
(153) 
_{Sep}
(141) 
_{Oct}
(59) 
_{Nov}
(87) 
_{Dec}
(75) 
2010 
_{Jan}
(58) 
_{Feb}
(41) 
_{Mar}
(51) 
_{Apr}
(74) 
_{May}
(81) 
_{Jun}
(39) 
_{Jul}
(30) 
_{Aug}
(43) 
_{Sep}
(76) 
_{Oct}
(59) 
_{Nov}
(62) 
_{Dec}
(52) 
2011 
_{Jan}
(125) 
_{Feb}
(41) 
_{Mar}
(96) 
_{Apr}
(53) 
_{May}
(21) 
_{Jun}
(23) 
_{Jul}
(48) 
_{Aug}
(71) 
_{Sep}
(37) 
_{Oct}
(81) 
_{Nov}
(60) 
_{Dec}
(32) 
2012 
_{Jan}
(51) 
_{Feb}
(23) 
_{Mar}

_{Apr}
(8) 
_{May}
(2) 
_{Jun}

_{Jul}
(8) 
_{Aug}
(25) 
_{Sep}
(4) 
_{Oct}
(32) 
_{Nov}
(17) 
_{Dec}
(2) 
2013 
_{Jan}
(8) 
_{Feb}
(2) 
_{Mar}
(9) 
_{Apr}
(9) 
_{May}
(37) 
_{Jun}
(48) 
_{Jul}
(63) 
_{Aug}
(42) 
_{Sep}
(59) 
_{Oct}
(83) 
_{Nov}
(141) 
_{Dec}
(133) 
2014 
_{Jan}
(57) 
_{Feb}
(58) 
_{Mar}
(58) 
_{Apr}
(25) 
_{May}
(14) 
_{Jun}
(3) 
_{Jul}
(6) 
_{Aug}
(1) 
_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 



1
(5) 
2
(14) 
3
(3) 
4
(6) 
5
(4) 
6
(7) 
7
(12) 
8
(6) 
9
(4) 
10
(1) 
11

12

13

14
(1) 
15
(1) 
16
(2) 
17

18
(2) 
19
(1) 
20

21
(1) 
22
(2) 
23

24
(1) 
25

26

27
(1) 
28
(1) 
29

30

31



From: <airwin@us...>  20091215 22:28:48

Revision: 10720 http://plplot.svn.sourceforge.net/plplot/?rev=10720&view=rev Author: airwin Date: 20091215 22:28:41 +0000 (Tue, 15 Dec 2009) Log Message:  Qualify arguments for plP_pointinpolygon. Implement fill_intersection_polygon and ifnotintersect (which fill_intersection_polygon calls), but do not use these experimental functions (which still have issues) to do clipped fills and gradients unless the user sets the cmake option DUSE_FILL_INTERSECTION_POLYGON=ON. Modified Paths:  trunk/cmake/modules/plplot.cmake trunk/config.h.cmake trunk/include/plplotP.h trunk/src/plfill.c Modified: trunk/cmake/modules/plplot.cmake ===================================================================  trunk/cmake/modules/plplot.cmake 20091214 18:06:07 UTC (rev 10719) +++ trunk/cmake/modules/plplot.cmake 20091215 22:28:41 UTC (rev 10720) @@ 31,6 +31,12 @@ set(DEFAULT_CMAP1_FILE "cmap1_default.pal") endif(NOT DEFAULT_CMAP1_FILE) +# Set to ON if want to use general fill_intersection_polygon approach +# rather than the traditional code to fill the intersection of a +# polygon with the clipping limits. */ + +option(USE_FILL_INTERSECTION_POLYGON "use fill_intersection_polygon" OFF) + # Need these modules to do subsequent checks. include(CheckIncludeFiles) include(CheckFunctionExists) Modified: trunk/config.h.cmake ===================================================================  trunk/config.h.cmake 20091214 18:06:07 UTC (rev 10719) +++ trunk/config.h.cmake 20091215 22:28:41 UTC (rev 10720) @@ 282,6 +282,11 @@ /* Define if csa is desired */ #cmakedefine WITH_CSA +/* Define if want to use general fill_intersection_polygon approach + * rather than the traditional code to fill the intersection of a polygon with + * the clipping limits. */ +#cmakedefine USE_FILL_INTERSECTION_POLYGON + /* Define to `char *' if <sys/types.h> does not define. */ #cmakedefine caddr_t Modified: trunk/include/plplotP.h ===================================================================  trunk/include/plplotP.h 20091214 18:06:07 UTC (rev 10719) +++ trunk/include/plplotP.h 20091215 22:28:41 UTC (rev 10720) @@ 975,7 +975,8 @@ /* Test whether a point is in a polygon. */ int plP_pointinpolygon( PLINT n, PLFLT *x, PLFLT *y, PLFLT xp, PLFLT yp ); +plP_pointinpolygon( PLINT n, const PLFLT *x, const PLFLT *y, + PLFLT xp, PLFLT yp ); /* Driver calls */ Modified: trunk/src/plfill.c ===================================================================  trunk/src/plfill.c 20091214 18:06:07 UTC (rev 10719) +++ trunk/src/plfill.c 20091215 22:28:41 UTC (rev 10720) @@ 26,7 +26,7 @@ #define INSIDE( ix, iy ) ( BETW( ix, xmin, xmax ) && BETW( iy, ymin, ymax )) #define DTOR 0.0174533 +#define DTOR ( PI / 180. ) #define BINC 50 struct point @@ 36,7 +36,6 @@ static PLINT bufferleng, buffersize, *buffer; /* Static function prototypes */ /* INDENT OFF */ static int compar( const void *, const void * ); @@ 51,13 +50,23 @@ buildlist( PLINT, PLINT, PLINT, PLINT, PLINT, PLINT, PLINT ); static int pointinpolygon( PLINT n, PLINT *x, PLINT *y, PLINT xp, PLINT yp ); +pointinpolygon( PLINT n, const PLINT *x, const PLINT *y, PLINT xp, PLINT yp ); static int circulation( PLINT *x, PLINT *y, PLINT npts ); +static void +fill_intersection_polygon( PLINT recursion_depth, PLINT ifclip, + void ( *fill )( short *, short *, PLINT ), + const PLINT *x1, const PLINT *y1, + PLINT i1start, PLINT n1, + const PLINT *x2, const PLINT *y2, + const PLINT *if2, PLINT n2 ); /* INDENT ON */ +static int +ifnotintersect( PLINT *xintersect, PLINT *yintersect, + PLINT xA1, PLINT yA1, PLINT xA2, PLINT yA2, + PLINT xB1, PLINT yB1, PLINT xB2, PLINT yB2 ); /**\ * void plfill() @@ 410,6 +419,46 @@ PLINT xmin, PLINT xmax, PLINT ymin, PLINT ymax, void ( *draw )( short *, short *, PLINT )) { + /* Must have at least 3 points and draw() specified */ + if ( npts < 3  !draw ) return; + +#ifdef USE_FILL_INTERSECTION_POLYGON + PLINT *x1, *y1, i1start = 0, i, im1, n1; + PLINT x2[4] = { xmin, xmax, xmax, xmin }; + PLINT y2[4] = { ymin, ymin, ymax, ymax }; + PLINT if2[4] = { 0, 0, 0, 0 }; + PLINT n2 = 4; + if (( x1 = (PLINT *) malloc( npts * sizeof ( PLINT ))) == NULL ) + { + plexit( "plP_plfclp: Insufficient memory" ); + } + if (( y1 = (PLINT *) malloc( npts * sizeof ( PLINT ))) == NULL ) + { + plexit( "plP_plfclp: Insufficient memory" ); + } + /* Polygon 2 obviously has no dups, but get rid of them in polygon + * 1 if they exist. ToDo: Deal with selfintersecting polygon 1 + * case as well. */ + + im1 = npts  1; + n1 = 0; + for ( i = 0; i < npts; i++ ) + { + if ( !( x[i] == x[im1] && y[i] == y[im1] )) + { + x1[n1] = x[i]; + y1[n1++] = y[i]; + } + im1 = i; + } + + fill_intersection_polygon( 0, 0, draw, x1, y1, i1start, n1, x2, y2, if2, n2 ); + free( x1 ); + free( y1 ); + return; +} +#else /* USE_FILL_INTERSECTION_POLYGON */ + PLINT i, x1, x2, y1, y2; int iclp = 0, iout = 2; short _xclp[2 * PL_MAXPOLY + 2], _yclp[2 * PL_MAXPOLY + 2]; @@ 426,8 +475,6 @@ int inside_rb; int inside_ru; /* Must have at least 3 points and draw() specified */  if ( npts < 3  !draw ) return; if ( npts < PL_MAXPOLY ) { @@ 442,7 +489,6 @@ plexit( "plP_plfclp: Insufficient memory" ); } }  inside_lb = pointinpolygon( npts, x, y, xmin, ymin ); inside_lu = pointinpolygon( npts, x, y, xmin, ymax ); inside_rb = pointinpolygon( npts, x, y, xmax, ymin ); @@ 600,9 +646,9 @@ } } /* Limit case  all vertices are outside of bounding box. So just fill entire  * box, *if* the bounding box is completely encircled.  */ + /* Limit case  all vertices are outside of bounding box. So just fill entire + * box, *if* the bounding box is completely encircled. + */ if ( iclp == 0 ) { if ( inside_lb ) @@ 624,7 +670,7 @@ } } /* Now handle cases where fill polygon intersects two sides of the box */ + /* Now handle cases where fill polygon intersects two sides of the box */ if ( iclp >= 2 ) { @@ 806,11 +852,11 @@ } } /* Check for the case that only one side has been crossed  * (AM) Just checking a single point turns out not to be  * enough, apparently the crossed_*1 and crossed_*2 variables  * are not quite what I expected.  */ + /* Check for the case that only one side has been crossed + * (AM) Just checking a single point turns out not to be + * enough, apparently the crossed_*1 and crossed_*2 variables + * are not quite what I expected. + */ if ( inside_lb + inside_rb + inside_lu + inside_ru == 4 ) { int dir = circulation( x, y, npts ); @@ 910,7 +956,7 @@ } } /* Draw the sucker */ + /* Draw the sucker */ if ( iclp >= 3 ) ( *draw )( xclp, yclp, iclp ); @@ 920,6 +966,7 @@ free( yclp ); } } +#endif /* USE_FILL_INTERSECTION_POLYGON */ /**\ * int circulation() @@ 948,9 +995,9 @@ circulation( PLINT *x, PLINT *y, PLINT npts ) { PLFLT xproduct;  int direction = 0; + int direction = 0; PLFLT x1, y1, x2, y2, x3, y3;  int i; + int i; xproduct = 0.0; x1 = x[0]; @@ 976,9 +1023,9 @@ \**/ static int pointinpolygon( PLINT n, PLINT *x, PLINT *y, PLINT xp, PLINT yp ) +pointinpolygon( PLINT n, const PLINT *x, const PLINT *y, PLINT xp, PLINT yp ) {  int i, return_value; + int i, return_value; PLFLT *xflt, *yflt; if (( xflt = (PLFLT *) malloc( n * sizeof ( PLFLT ))) == NULL ) { @@ 1011,10 +1058,10 @@ \**/ int plP_pointinpolygon( PLINT n, PLFLT *x, PLFLT *y, PLFLT xp, PLFLT yp ) +plP_pointinpolygon( PLINT n, const PLFLT *x, const PLFLT *y, PLFLT xp, PLFLT yp ) {  int i;  int count_crossings; + int i; + int count_crossings; PLFLT x1, y1, x2, y2, xout, yout, xmax; PLFLT xvp, yvp, xvv, yvv, xv1, yv1, xv2, yv2; PLFLT inprod1, inprod2; @@ 1106,3 +1153,504 @@ return ( count_crossings % 2 ); } + +/* Fill intersection of two simple (not selfintersecting) polygons. + * There must be an even number of edge intersections between the two + * polygons (ignoring vertex intersections which touch, but do not cross). + * Eliminate those intersection pairs by recursion (calling the same + * routine again with either the first or second polygon split between + * the two intersecting edges into two independent second polygons.) + * Once the recursion has eliminated all intersecting edges, fill or + * not using the appropriate polygon depending on whether the first + * and second polygons are identical or whether one of them is + * entirely inside the other of them. If ifclip is true, the fill + * step will consist of another recursive call to the routine with + * ifclip false and the second polygon set to the clip rectangle. + * N.B. it is the calling routine's responsibility to insure the two + * polygons are not selfintersecting and do not have duplicate points. */ + +/* Consider the intersections between the first and second + * polygons (including the possibility of multiple intersections per edge of + * the first polygon). The total number of such intersections must be even. + * Solve for the first pair of intersections (if any) and simplify the problem + * by recursively calling the same routine twice with the same first polygon + * and two modified second polygons consisting of the lefthand segment of the + * second polygon + two intersection points and the righthand segment of the + * second polygon + two intersection points. Note that for the recursive call + * the vertices that were intersection points should not generate new + * intersections with the first unchanging polygon because points on the + * perimeter of polygons are always considered to be outside it. However, due + * to integer truncation and other numerical errors I doubt we can guaranteed + * that numerically in all cases. So we set up a logical array that drops + * segments from the intersection test that are already bounded by + * intersections generated higher in the recursion stack. The result + * of this recursion is deep in the recursion stack you finally end up + * considering the case of the original first polygon and a modified second + * polygon that does not intersect with it at all. + * + * + * . Solve that simple case. Check for identical polygons (taking into account + * the possibilities of different starting points and different directions + * traversing the perimeter), and if so, do a fill of the first polygon (to be + * specific) in that case. If not identical, then do one testinpolygon call to + * decide if the second polygon is totally inside the first. If so, fill the + * second polygon. If not, use one additional testinpolygon call to decide if + * the first polygon is totally inside the second, and if so, fill the first + * polygon. + * + * . Carry a clip flag as part of the recursion, and for the simple case above + * with the flag true, start the recursion all over again (with the clip flag + * false) with the "filling" polygon as the first polygon, and the clip + * rectangle as the the second. + * + * + * Find innermost polygon of (x1,y1) and (x2, y2) for the purposes of + * filling. The number of vertices is returned, and the resulting + * inner (xinner, yinner) polygon calculated for that number of + * vertices. A zero is returned as an error code if the number of + * inner polygon vertices exceeds max_ninner (which should be set + * externally to the size allocated externally for xinner, yinner). A + * zero is also returned if n1 < 3 or (n2 < 3 && n2 != 2). (Note + * that n2 = 2 signals the special case when the second polygon is a + * rectangle.) */ + +#define MAX_RECURSION_DEPTH 10 +void +fill_intersection_polygon( PLINT recursion_depth, PLINT ifclip, + void ( *fill )( short *, short *, PLINT ), + const PLINT *x1, const PLINT *y1, + PLINT i1start, PLINT n1, + const PLINT *x2, const PLINT *y2, + const PLINT *if2, PLINT n2 ) +{ + PLINT i1, i1m1, i1wrap, i1wraplast, + i2, i2m1, i2wrap, i2wraplast, + kk, kkstart1, kkstart21, kkstart22, + k, kstart, range1, range21, range22, nintersect, + nsplit1, nsplit2; + PLINT xintersect[2], yintersect[2], ifintersect; + PLINT *xsplit1, *ysplit1, *ifsplit1, + *xsplit2, *ysplit2, *ifsplit2; + PLINT ifill, nfill = 0; + const PLINT *xfiller, *yfiller; + short *xfill, *yfill; + + if ( recursion_depth > MAX_RECURSION_DEPTH ) + { + plwarn( "fill_intersection_polygon: Recursion_depth too large. " + "Probably an internal error figuring out intersections. " ); + return; + } + + if ( n1 < 3 ) + { + plwarn( "fill_intersection_polygon: Internal error; n1 < 3." ); + return; + } + + if ( n2 < 3 ) + { + plwarn( "fill_intersection_polygon: Internal error; n2 < 3." ); + return; + } + + if ( i1start < 0  i1start >= n1 ) + { + plwarn( "fill_intersection_polygon: invalid i1start." ); + return; + } + + i1m1 = i1start  1; + if ( i1m1 <= 0 ) + i1m1 = n1  1; + + for ( i1 = i1start; i1 < n1; i1++ ) + { + if ( x1[i1] == x1[i1m1] && y1[i1] == y1[i1m1] ) + break; + i1m1 = i1; + } + + if ( i1 < n1 ) + { + plwarn( "fill_intersection_polygon: Internal error; i1 < n1." ); + return; + } + + i2m1 = n2  1; + for ( i2 = 0; i2 < n2; i2++ ) + { + if ( x2[i2] == x2[i2m1] && y2[i2] == y2[i2m1] ) + break; + i2m1 = i2; + } + + if ( i2 < n2 ) + { + plwarn( "fill_intersection_polygon: Internal error; i < n2." ); + return; + } + + /* + * + * Follow polygon 1 (checking intersections with polygon 2 for each + * segment of polygon 1) until you have accumulated two + * intersections with polygon 2. Here is an asciiart illustration + * of the situation. + * + * + * 2???2 + * + * 2 2 + * + *  1 1 + * 1 2 1 1 ... + * x + * 1 + * x + * 2 + * 1 1 + * 1 + * 2 + * 2 + * 2???2 + * + * + * "1" marks polygon 1 vertices, "2" marks polygon 2 vertices, "x" + * marks the intersections, "" stands for part of polygon 1 + * that has been previously searched for all possible intersections + * from index 0, and "..." means polygon 1 continues + * with more potential intersections both above or below this diagram + * before it finally hooks back to connect with the index 0 vertex. + * "2???2" stands for parts of polygon 2 that must connect with each other + * (since the polygon 1 path between the two intersections is + * known to be free of intersections.) + * + * Polygon 2 is split at the boundary defined by the two + * intersections and all (in this case three) polygon 1 vertices + * between the two intersections for the next recursion level. We + * absolutely know for that boundary that no more intersections can + * occur (both polygon 1 and polygon 2 are guaranteed not to + * selfintersect) so we mark the status of those vertices with that + * information so those polygon 2 split vertices will not be used to + * search for further intersections at deeper recursion levels. + * Note, we know nothing about whether the remaining "2???2" parts of the + * split polygon 2 intersect with polygon 1 or not so those will + * continued to be searched at deeper recursion levels. At the same + * time, we absolutely know that the part of polygon 1 to the left of + * rightmost x down to and including index 0 cannot yield more + * intersections with any split of polygon 2 so we adjust the lower + * limit of polygon 1 to be used for intersection searches at deeper + * recursion levels. The result should be that at sufficiently deep + * recursion depth we always end up with the case that there are no + * intersections to be found between polygon 1 and some polygon 2 + * split, and in that case we move on to the end phase below. + */ + nintersect = 0; + i1m1 = n1  1; + i1wrap = 1; + for ( i1 = i1start; i1 < n1; i1++ ) + { + i2m1 = n2  1; + i2wrap = 1; + for ( i2 = 0; i2 < n2; i2++ ) + { + if ( !if2[i2] ) + { + /* intersect is acted upon only if a series of conditions are met. */ + ifintersect = !ifnotintersect( + &xintersect[nintersect], &yintersect[nintersect], + x1[i1m1], y1[i1m1], x1[i1], y1[i1], + x2[i2m1], y2[i2m1], x2[i2], y2[i2] ); + ifintersect = ifintersect && !( + xintersect[nintersect] == x1[i1m1] && + yintersect[nintersect] == y1[i1m1] ); + ifintersect = ifintersect && !( + xintersect[nintersect] == x1[i1] && + yintersect[nintersect] == y1[i1] ); + ifintersect = ifintersect && !( + xintersect[nintersect] == x2[i2m1] && + yintersect[nintersect] == y2[i2m1] ); + ifintersect = ifintersect && !( + xintersect[nintersect] == x2[i2] && + yintersect[nintersect] == y2[i2] ); + if ( ifintersect ) + { + /* The above test must be more elaborate if the intersection + * point is a vertex of the first polygon, the second polygon + * or both. ToDo! */ + if ( nintersect == 0 ) + { + i1wraplast = i1wrap; + i2wraplast = i2wrap; + + nintersect++; + } + else + { + /* Have discovered the first two intersections for + * polygon 1 at i1 = i1start or above. */ + /* New i1start is the largest nonnegative polygon 1 + * index below the last detected intersect. */ + i1start = MAX( i1wrap, 0 ); + + /* Split polygon 2 at the boundary consisting of + * first intersection, intervening (if any) range1 + * polygon 1 points and second intersection. */ + /* range1 must always be nonnegative because i1 + * range only traversed once. */ + range1 = i1wrap  i1wraplast; + /* Polygon 2 intersects could be anywhere (since + * i2 range repeated until get an intersect). + * Divide polygon 2 into two polygons with a + * common boundary consisting of the first intersect, + * range1 points from polygon1 starting at index + * kkstart1 of polygon 1, and the second intersect. */ + kkstart1 = i1wraplast + 1; + + /* Split 1 of polygon2 consists of the + * boundary + range21 points between kkstart21 + * (= i2) and i2wraplast in ascending order of + * polygon 2 indices. N.B. if range21 is zero + * below we change that to n2, i.e., use the + * whole range of polygon 2 in ascending + * order. For this case, range22 (below) will + * be zero and range1 (above) must be nonzero + * (in order to have two intersections). */ + range21 = i2wraplast  i2wrap; + if ( range21 <= 0 ) + range21 += n2; + kkstart21 = i2; + + /* Split 2 of polygon 2 consists of the + * boundary + range22 (= n2  range21) points + * between kkstart22 (= i2wrap) and i2wraplast + 1 in + * descending order of polygon 2 indices. */ + range22 = n2  range21; + kkstart22 = i2wrap; + if ( kkstart22 == 1 ) + kkstart22 = i2m1; + nsplit1 = 2 + range1 + range21; + nsplit2 = 2 + range1 + range22; + + if (( xsplit1 = (PLINT *) malloc( nsplit1 * sizeof ( PLINT ))) == NULL ) + { + plexit( "fill_intersection_polygon: Insufficient memory" ); + } + if (( ysplit1 = (PLINT *) malloc( nsplit1 * sizeof ( PLINT ))) == NULL ) + { + plexit( "fill_intersection_polygon: Insufficient memory" ); + } + if (( ifsplit1 = (PLINT *) malloc( nsplit1 * sizeof ( PLINT ))) == NULL ) + { + plexit( "fill_intersection_polygon: Insufficient memory" ); + } + + if (( xsplit2 = (PLINT *) malloc( nsplit2 * sizeof ( PLINT ))) == NULL ) + { + plexit( "fill_intersection_polygon: Insufficient memory" ); + } + if (( ysplit2 = (PLINT *) malloc( nsplit2 * sizeof ( PLINT ))) == NULL ) + { + plexit( "fill_intersection_polygon: Insufficient memory" ); + } + if (( ifsplit2 = (PLINT *) malloc( nsplit2 * sizeof ( PLINT ))) == NULL ) + { + plexit( "fill_intersection_polygon: Insufficient memory" ); + } + /* Common boundary between split1 and split2. */ + k = 0; + xsplit1[k] = xintersect[0]; + ysplit1[k] = yintersect[0]; + ifsplit1[k] = 1; + xsplit2[k] = xintersect[0]; + ysplit2[k] = yintersect[0]; + ifsplit2[k] = 1; + kstart = k + 1; + kk = kkstart1; + /* No wrap checks on kk index below because + * it must always be in valid range (since + * polygon 1 traversed only once). */ + for ( k = kstart; k < range1 + 1; k++ ) + { + xsplit1[k] = x1[kk]; + ysplit1[k] = y1[kk]; + ifsplit1[k] = 2; + xsplit2[k] = x1[kk]; + ysplit2[k] = y1[kk++]; + ifsplit2[k] = 2; + } + xsplit1[k] = xintersect[1]; + ysplit1[k] = yintersect[1]; + ifsplit1[k] = 1; + xsplit2[k] = xintersect[1]; + ysplit2[k] = yintersect[1]; + ifsplit2[k] = 1; + + /* Finish off collecting split1 using ascending kk + * values. */ + kstart = k + 1; + kk = kkstart21; + for ( k = kstart; k < nsplit1; k++ ) + { + xsplit1[k] = x2[kk]; + ysplit1[k] = y2[kk]; + ifsplit1[k] = if2[kk++]; + if ( kk >= n2 ) + kk = n2; + } + fill_intersection_polygon( recursion_depth + 1, ifclip, fill, + x1, y1, i1start, n1, + xsplit1, ysplit1, ifsplit1, nsplit1 ); + free( xsplit1 ); + free( ysplit1 ); + free( ifsplit1 ); + + /* Finish off collecting split2 using descending kk + * values. */ + kk = kkstart22; + for ( k = kstart; k < nsplit2; k++ ) + { + xsplit2[k] = x2[kk]; + ysplit2[k] = y2[kk]; + ifsplit2[k] = if2[kk]; + if ( kk < 0 ) + kk += n2; + } + fill_intersection_polygon( recursion_depth + 1, ifclip, fill, + x1, y1, i1start, n1, + xsplit2, ysplit2, ifsplit2, nsplit2 ); + free( xsplit2 ); + free( ysplit2 ); + free( ifsplit2 ); + return; + } + } + } + i2m1 = i2; + i2wrap = i2m1; + } + i1m1 = i1; + i1wrap = i1m1; + } + if ( nintersect != 0 ) + { + plwarn( "fill_intersection_polygon: Internal error; nintersect != 0." ); + return; + } + + /* Look for first vertex in Polygon 2 that does not intersect with 1. */ + for ( i2 = 0; i2 < n2; i2++ ) + { + if ( !if2[i2] ) + break; + } + + if ( i2 < n2 && pointinpolygon( n1, x1, y1, x2[i2], y2[i2] )) + { + /* All of polygon 2 inside polygon 1. */ + nfill = n2; + xfiller = x2; + yfiller = y2; + } + else + { + /* Look for first vertex in polygon 1 that is inside polygon 2. */ + for ( i1 = 0; i1 < n1; i1++ ) + { + if ( pointinpolygon( n2, x2, y2, x1[i1], y1[i1] )) + break; + } + + if ( i1 < n1 ) + { + /* All of polygon 1 inside polygon 2 */ + nfill = n1; + xfiller = x1; + yfiller = y1; + } + else + plwarn( "fill_intersection_polygon: inscribed polygon not yet implemented" ); + } + if ( nfill > 0 ) + { + if (( xfill = (short *) malloc( nfill * sizeof ( short ))) == NULL ) + { + plexit( "fill_intersection_polygon: Insufficient memory" ); + } + if (( yfill = (short *) malloc( nfill * sizeof ( short ))) == NULL ) + { + plexit( "fill_intersection_polygon: Insufficient memory" ); + } + for ( ifill = 0; ifill < nfill; ifill++ ) + { + xfill[ifill] = xfiller[ifill]; + yfill[ifill] = yfiller[ifill]; + } + ( *fill )( xfill, yfill, nfill ); + free( xfill ); + free( yfill ); + } + + return; +} + +/* Find if an intersection (N.B. including end points) exists between + * straight line segments A and B defined by their endpoints xA1, yA1, + * xA2, yA2, xB1, yB1, xB2, yB2. If not return true (1 if parallel, + * 1 if intersecting away from segments). If true, return false. + * Except for the parallel line case always return the intersection, + * (xintersect, yintersect) via the argument list. */ + +int +ifnotintersect( PLINT * xintersect, PLINT * yintersect, + PLINT xA1, PLINT yA1, PLINT xA2, PLINT yA2, + PLINT xB1, PLINT yB1, PLINT xB2, PLINT yB2 ) +{ + PLINT xA2A1, yA2A1, xB2B1, yB2B1; + PLINT xB1A1, yB1A1, xB2A1, yB2A1; + PLFLT factor; + /* + * Two linear equations to be solved for x and y. + * y = ((x  xA1)*yA2 + (xA2  x)*yA1)/(xA2  xA1) + * y = ((x  xB1)*yB2 + (xB2  x)*yB1)/(xB2  xB1) + * + * Transform those two equations to coordinate system with origin + * at (xA1, yA1). + * y' = x'*yA2A1/xA2A1 + * y' = ((x'  xB1A1)*yB2A1 + (xB2A1  x')*yB1A1)/xB2B1 + * ==> + * x' = ( + * (xB1A1*yB2A1 + xB2A1*yB1A1)/xB2B1)/ + * (yB2B1/xB2B1  yA2A1/xA2A1) + * = (xB1A1*yB2A1  xB2A1*yB1A1)*xA2A1/ + * (xA2A1*yB2B1  yA2A1*xB2B1) + * + */ + + xA2A1 = xA2  xA1; + yA2A1 = yA2  yA1; + xB2B1 = xB2  xB1; + yB2B1 = yB2  yB1; + + factor = xA2A1 * yB2B1  yA2A1 * xB2B1; + /* If two line segments are parallel (including identical) .... */ + if ( fabs( factor ) == 0. ) + return 1; + xB1A1 = xB1  xA1; + yB1A1 = yB1  yA1; + xB2A1 = xB2  xA1; + yB2A1 = yB2  yA1; + + factor = ( xB1A1 * yB2A1  yB1A1 * xB2A1 ) / factor; + *xintersect = factor * xA2A1 + xA1; + *yintersect = factor * yA2A1 + yA1; + /* The x and y range checks (which include end points) are redundant + * with each other for infiniteprecision floatingpoint arithmetic. + * But we don't have that so do these "redundant" checks. */ + if ( BETW( *xintersect, xA1, xA2 ) && BETW( *yintersect, yA1, yA2 ) && + BETW( *xintersect, xB1, xB2 ) && BETW( *yintersect, yB1, yB2 )) + return 0; + else + return 1; +} This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. 