28 #define INSIDE( ix, iy ) ( BETW( ix, xmin, xmax ) && BETW( iy, ymin, ymax ) )
30 #define DTOR ( PI / 180. )
35 #define BETW_NBCC( ix, ia, ib ) ( ( ( ix ) <= ( ia + PL_NBCC ) && ( ix ) >= ( ib - PL_NBCC ) ) || ( ( ix ) >= ( ia - PL_NBCC ) && ( ix ) <= ( ib + PL_NBCC ) ) )
81 compar(
const void *,
const void * );
98 #ifdef USE_FILL_INTERSECTION_POLYGON
100 fill_intersection_polygon(
PLINT recursion_depth,
PLINT ifextrapolygon,
102 void ( *fill )(
short *,
short *,
PLINT ),
137 PLINT *xpoly, *ypoly;
141 if ( plsc->level < 3 )
143 plabort(
"plfill: Please set up window first" );
148 plabort(
"plfill: Not enough points in object" );
154 xpoly = (
PLINT *) malloc( (
size_t) ( n + 1 ) *
sizeof (
PLINT ) );
155 ypoly = (
PLINT *) malloc( (
size_t) ( n + 1 ) *
sizeof (
PLINT ) );
157 if ( ( xpoly == NULL ) || ( ypoly == NULL ) )
159 plexit(
"plfill: Insufficient memory for large polygon" );
168 for ( i = 0; i < n; i++ )
175 if ( xpoly[0] != xpoly[n - 1] || ypoly[0] != ypoly[n - 1] )
178 xpoly[n - 1] = xpoly[0];
179 ypoly[n - 1] = ypoly[0];
182 plP_plfclp( xpoly, ypoly, n, plsc->clpxmi, plsc->clpxma,
183 plsc->clpymi, plsc->clpyma,
plP_fill );
210 PLINT *xpoly, *ypoly;
215 if ( plsc->level < 3 )
217 plabort(
"plfill3: Please set up window first" );
222 plabort(
"plfill3: Not enough points in object" );
229 tx = (
PLFLT *) malloc( (
size_t) ( n + 1 ) *
sizeof (
PLFLT ) );
230 ty = (
PLFLT *) malloc( (
size_t) ( n + 1 ) *
sizeof (
PLFLT ) );
231 tz = (
PLFLT *) malloc( (
size_t) ( n + 1 ) *
sizeof (
PLFLT ) );
232 xpoly = (
PLINT *) malloc( (
size_t) ( n + 1 ) *
sizeof (
PLINT ) );
233 ypoly = (
PLINT *) malloc( (
size_t) ( n + 1 ) *
sizeof (
PLINT ) );
235 if ( ( tx == NULL ) || ( ty == NULL ) || ( tz == NULL ) ||
236 ( xpoly == NULL ) || ( ypoly == NULL ) )
238 plexit(
"plfill3: Insufficient memory for large polygon" );
250 plP_gdom( &xmin, &xmax, &ymin, &ymax );
254 for ( i = 0; i < n; i++ )
256 tx[i] = x[i]; ty[i] = y[i]; tz[i] = z[i];
258 if ( tx[0] != tx[n - 1] || ty[0] != ty[n - 1] || tz[0] != tz[n - 1] )
261 tx[n - 1] = tx[0]; ty[n - 1] = ty[0]; tz[n - 1] = tz[0];
263 V[0] = tx; V[1] = ty; V[2] = tz;
270 for ( i = 0; i < n; i++ )
288 plP_plfclp( xpoly, ypoly, n, plsc->clpxmi, plsc->clpxma,
289 plsc->clpymi, plsc->clpyma,
plP_fill );
312 PLINT xp1, yp1, xp2, yp2, xp3, yp3;
321 plabort(
"plfill: Out of memory" );
327 for ( k = 0; k < plsc->nps; k++ )
331 temp =
DTOR * plsc->inclin[k] * 0.1;
332 si = sin( temp ) * plsc->ypmm;
333 ci = cos( temp ) * plsc->xpmm;
337 temp = sqrt( (
double) ( si * si + ci * ci ) );
341 dinc = (
PLINT) ( plsc->delta[k] *
SSQR( plsc->ypmm *
ABS( ci ),
342 plsc->xpmm *
ABS( si ) ) / 1000. );
359 for ( i = 0; i < n; i++ )
364 buildlist( xp1, yp1, xp2, yp2, xp3, yp3, dinc );
394 fprintf( stderr,
"plfill: oh oh we are lost\n" );
397 fprintf( stderr,
"plfill: %d %d\n",
421 *a = (
PLINT) floor( (
double) ( ta * c + tb * d + 0.5 ) );
422 *b = (
PLINT) floor( (
double) ( tb * c - ta * d + 0.5 ) );
430 PLINT dx,
dy, cstep, nstep, ploty, plotx;
437 if ( yp2 > yp3 && ( ( yp2 % dinc ) == 0 ) )
455 nstep = ( yp3 > yp2 ? 1 : -1 );
461 ploty = ( min_y / dinc ) * dinc;
465 for (; ploty <= max_y; ploty += dinc )
471 if ( cstep == -nstep )
473 if ( yp2 == yp3 && yp1 > yp2 )
476 plotx = xp1 + (
PLINT) floor( ( (
double) ( ploty - yp1 ) * dx ) / dy + 0.5 );
494 plexit(
"plfill: Out of memory!" );
504 compar(
const void *pnum1,
const void *pnum2 )
506 const struct point *pnt1, *pnt2;
508 pnt1 = (
const struct point *) pnum1;
509 pnt2 = (
const struct point *) pnum2;
511 if ( pnt1->
y < pnt2->
y )
513 else if ( pnt1->
y > pnt2->
y )
518 if ( pnt1->
x < pnt2->
x )
520 else if ( pnt1->
x > pnt2->
x )
535 void ( *draw )(
short *,
short *,
PLINT ) )
537 #ifdef USE_FILL_INTERSECTION_POLYGON
538 PLINT *x10, *y10, *x1, *y1, *if1, i1start = 0, i, im1, n1, n1m1,
542 PLINT if2[4] = { 0, 0, 0, 0 };
546 if ( npts < 3 || !draw )
549 if ( ( x10 = (
PLINT *) malloc( (
size_t) npts *
sizeof (
PLINT ) ) ) == NULL )
551 plexit(
"plP_plfclp: Insufficient memory" );
553 if ( ( y10 = (
PLINT *) malloc( (
size_t) npts *
sizeof (
PLINT ) ) ) == NULL )
555 plexit(
"plP_plfclp: Insufficient memory" );
563 for ( i = 0; i < npts; i++ )
565 if ( !( x[i] == x[im1] && y[i] == y[im1] ) )
586 if ( positive_orientation( n1, x10, y10 ) )
593 if ( ( x1 = (
PLINT *) malloc( (
size_t) n1 *
sizeof (
PLINT ) ) ) == NULL )
595 plexit(
"plP_plfclp: Insufficient memory" );
597 if ( ( y1 = (
PLINT *) malloc( (
size_t) n1 *
sizeof (
PLINT ) ) ) == NULL )
599 plexit(
"plP_plfclp: Insufficient memory" );
602 for ( i = 0; i < n1; i++ )
604 x1[n1m1 - i] = x10[i];
605 y1[n1m1 - i] = y10[i];
615 for ( i = 0; i < n1; i++ )
617 if ( ( ifnotpointinpolygon =
623 if ( ifnotpointinpolygon )
624 fill_intersection_polygon( 0, 0, 0, draw, x1, y1, i1start, n1, x2, y2, if2, n2 );
627 if ( ( if1 = (
PLINT *) calloc( n1,
sizeof (
PLINT ) ) ) == NULL )
629 plexit(
"plP_plfclp: Insufficient memory" );
631 fill_intersection_polygon( 0, 0, 0, draw, x2, y2, i1start, n2, x1, y1, if1, n1 );
638 #else // USE_FILL_INTERSECTION_POLYGON
640 PLINT i, x1, x2, y1, y2;
641 int iclp = 0, iout = 2;
643 short *xclp = NULL, *yclp = NULL;
645 int crossed_xmin1 = 0, crossed_xmax1 = 0;
646 int crossed_ymin1 = 0, crossed_ymax1 = 0;
647 int crossed_xmin2 = 0, crossed_xmax2 = 0;
648 int crossed_ymin2 = 0, crossed_ymax2 = 0;
649 int crossed_up = 0, crossed_down = 0;
650 int crossed_left = 0, crossed_right = 0;
657 if ( npts < 3 || !draw )
667 if ( ( ( xclp = (
short *) malloc( (
size_t) ( 2 * npts + 2 ) *
sizeof (
short ) ) ) == NULL ) ||
668 ( ( yclp = (
short *) malloc( (
size_t) ( 2 * npts + 2 ) *
sizeof (
short ) ) ) == NULL ) )
670 plexit(
"plP_plfclp: Insufficient memory" );
678 for ( i = 0; i < npts - 1; i++ )
680 x1 = x[i]; x2 = x[i + 1];
681 y1 = y[i]; y2 = y[i + 1];
686 xmin, xmax, ymin, ymax );
691 crossed_xmin2 = ( x1 ==
xmin ); crossed_xmax2 = ( x1 ==
xmax );
692 crossed_ymin2 = ( y1 ==
ymin ); crossed_ymax2 = ( y1 ==
ymax );
694 crossed_left = ( crossed_left || crossed_xmin2 );
695 crossed_right = ( crossed_right || crossed_xmax2 );
696 crossed_down = ( crossed_down || crossed_ymin2 );
697 crossed_up = ( crossed_up || crossed_ymax2 );
703 xclp[iclp] = (short) x1; yclp[iclp] = (short) y1; iclp++;
704 xclp[iclp] = (short) x2; yclp[iclp] = (short) y2; iclp++;
710 else if ( x1 == (
int) xclp[iclp - 1] && y1 == (int) yclp[iclp - 1] )
712 xclp[iclp] = (short) x2; yclp[iclp] = (short) y2; iclp++;
726 xclp[iclp + 1] = (short) x2; yclp[iclp + 1] = (short) y2;
727 xclp[iclp + 2] = (short) x1; yclp[iclp + 2] = (short) y1;
728 iout = iout - iclp + 1;
730 if ( ( ( crossed_xmin1 && crossed_xmax2 ) ||
731 ( crossed_xmin2 && crossed_xmax1 ) ) &&
736 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymax; iclp++;
737 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymax; iclp++;
741 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymax; iclp++;
742 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymax; iclp++;
746 else if ( ( ( crossed_xmin1 && crossed_xmax2 ) ||
747 ( crossed_xmin2 && crossed_xmax1 ) ) &&
752 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymin; iclp++;
753 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymin; iclp++;
757 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymin; iclp++;
758 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymin; iclp++;
762 else if ( ( ( crossed_ymin1 && crossed_ymax2 ) ||
763 ( crossed_ymin2 && crossed_ymax1 ) ) &&
768 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymin; iclp++;
769 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymax; iclp++;
773 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymax; iclp++;
774 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymin; iclp++;
778 else if ( ( ( crossed_ymin1 && crossed_ymax2 ) ||
779 ( crossed_ymin2 && crossed_ymax1 ) ) &&
784 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymin; iclp++;
785 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymax; iclp++;
789 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymax; iclp++;
790 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymin; iclp++;
795 else if ( ( crossed_xmin1 && crossed_ymin2 ) ||
796 ( crossed_ymin1 && crossed_xmin2 ) )
798 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymin; iclp++;
801 else if ( ( crossed_xmax1 && crossed_ymin2 ) ||
802 ( crossed_ymin1 && crossed_xmax2 ) )
804 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymin; iclp++;
807 else if ( ( crossed_xmin1 && crossed_ymax2 ) ||
808 ( crossed_ymax1 && crossed_xmin2 ) )
810 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymax; iclp++;
813 else if ( ( crossed_xmax1 && crossed_ymax2 ) ||
814 ( crossed_ymax1 && crossed_xmax2 ) )
816 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymax; iclp++;
820 xclp[iclp] = (short) x1; yclp[iclp] = (short) y1; iclp++;
821 xclp[iclp] = (short) x2; yclp[iclp] = (short) y2; iclp++;
825 crossed_xmin1 = ( x2 ==
xmin ); crossed_xmax1 = ( x2 ==
xmax );
826 crossed_ymin1 = ( y2 ==
ymin ); crossed_ymax1 = ( y2 ==
ymax );
837 xclp[0] = (short) xmin; yclp[0] = (short) ymin;
838 xclp[1] = (short) xmax; yclp[1] = (short) ymin;
839 xclp[2] = (short) xmax; yclp[2] = (short) ymax;
840 xclp[3] = (short) xmin; yclp[3] = (short) ymax;
841 xclp[4] = (short) xmin; yclp[4] = (short) ymin;
842 ( *draw )( xclp, yclp, 5 );
862 if ( ( xclp[0] == (
short) xmin && xclp[iclp - 1] == (
short) xmax ) ||
863 ( xclp[0] == (
short) xmax && xclp[iclp - 1] == (
short) xmin ) ||
864 ( yclp[0] == (
short) ymin && yclp[iclp - 1] == (
short) ymax ) ||
865 ( yclp[0] == (
short) ymax && yclp[iclp - 1] == (
short) ymin ) ||
866 ( xclp[0] == (
short) xmin && yclp[iclp - 1] == (
short) ymin ) ||
867 ( yclp[0] == (
short) ymin && xclp[iclp - 1] == (
short) xmin ) ||
868 ( xclp[0] == (
short) xmax && yclp[iclp - 1] == (
short) ymin ) ||
869 ( yclp[0] == (
short) ymin && xclp[iclp - 1] == (
short) xmax ) ||
870 ( xclp[0] == (
short) xmax && yclp[iclp - 1] == (
short) ymax ) ||
871 ( yclp[0] == (
short) ymax && xclp[iclp - 1] == (
short) xmax ) ||
872 ( xclp[0] == (
short) xmin && yclp[iclp - 1] == (
short) ymax ) ||
873 ( yclp[0] == (
short) ymax && xclp[iclp - 1] == (
short) xmin ) )
875 printf(
"dir=%d, clipped points:\n", dir );
876 for ( i = 0; i < iclp; i++ )
877 printf(
" x[%d]=%hd y[%d]=%hd", i, xclp[i], i, yclp[i] );
879 printf(
"pre-clipped points:\n" );
880 for ( i = 0; i < npts; i++ )
881 printf(
" x[%d]=%d y[%d]=%d", i, x[i], i, y[i] );
888 if ( xclp[0] == (
short) xmin && xclp[iclp - 1] == (
short) xmax )
892 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymax; iclp++;
893 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymax; iclp++;
897 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymin; iclp++;
898 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymin; iclp++;
901 else if ( xclp[0] == (
short) xmax && xclp[iclp - 1] == (short) xmin )
905 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymin; iclp++;
906 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymin; iclp++;
910 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymax; iclp++;
911 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymax; iclp++;
916 else if ( yclp[0] == (
short) ymin && yclp[iclp - 1] == (short) ymax )
920 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymax; iclp++;
921 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymin; iclp++;
925 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymax; iclp++;
926 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymin; iclp++;
929 else if ( yclp[0] == (
short) ymax && yclp[iclp - 1] == (short) ymin )
933 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymin; iclp++;
934 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymax; iclp++;
938 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymin; iclp++;
939 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymax; iclp++;
955 else if ( ( xclp[0] == (
short) xmin && yclp[iclp - 1] == (short) ymin && dir < 0 ) ||
956 ( yclp[0] == (short) ymin && xclp[iclp - 1] == (
short) xmin && dir > 0 ) )
958 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymin; iclp++;
961 else if ( ( xclp[0] == (
short) xmin && yclp[iclp - 1] == (short) ymin && dir > 0 ) )
963 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymin; iclp++;
964 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymax; iclp++;
965 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymax; iclp++;
968 else if ( ( yclp[0] == ymin && xclp[iclp - 1] == xmin && dir < 0 ) )
970 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymax; iclp++;
971 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymax; iclp++;
972 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymin; iclp++;
975 else if ( ( xclp[0] == (
short) xmax && yclp[iclp - 1] == (short) ymin && dir > 0 ) ||
976 ( yclp[0] == (short) ymin && xclp[iclp - 1] == (
short) xmax && dir < 0 ) )
978 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymin; iclp++;
981 else if ( yclp[0] == (
short) ymin && xclp[iclp - 1] == (short) xmax && dir > 0 )
983 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymax; iclp++;
984 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymax; iclp++;
985 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymin; iclp++;
988 else if ( xclp[0] == (
short) xmax && yclp[iclp - 1] == (short) ymin && dir < 0 )
990 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymin; iclp++;
991 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymax; iclp++;
992 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymax; iclp++;
995 else if ( ( xclp[0] == (
short) xmax && yclp[iclp - 1] == (short) ymax && dir < 0 ) ||
996 ( yclp[0] == (short) ymax && xclp[iclp - 1] == (
short) xmax && dir > 0 ) )
998 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymax; iclp++;
1001 else if ( xclp[0] == (
short) xmax && yclp[iclp - 1] == (short) ymax && dir > 0 )
1003 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymax; iclp++;
1004 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymin; iclp++;
1005 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymin; iclp++;
1008 else if ( yclp[0] == (
short) ymax && xclp[iclp - 1] == (short) xmax && dir < 0 )
1010 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymin; iclp++;
1011 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymin; iclp++;
1012 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymax; iclp++;
1015 else if ( ( xclp[0] == (
short) xmin && yclp[iclp - 1] == (short) ymax && dir > 0 ) ||
1016 ( yclp[0] == (short) ymax && xclp[iclp - 1] == (
short) xmin && dir < 0 ) )
1018 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymax; iclp++;
1021 else if ( yclp[0] == (
short) ymax && xclp[iclp - 1] == (short) xmin && dir > 0 )
1023 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymin; iclp++;
1024 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymin; iclp++;
1025 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymax; iclp++;
1028 else if ( xclp[0] == (
short) xmin && yclp[iclp - 1] == (short) ymax && dir < 0 )
1030 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymax; iclp++;
1031 xclp[iclp] = (short) xmax; yclp[iclp] = (short) ymin; iclp++;
1032 xclp[iclp] = (short) xmin; yclp[iclp] = (short) ymin; iclp++;
1041 if ( inside_lb + inside_rb + inside_lu + inside_ru == 4 )
1044 PLINT xlim[4], ylim[4];
1053 if ( crossed_left + crossed_right + crossed_down + crossed_up == 1 )
1058 insert = 0 * crossed_left + 1 * crossed_down + 2 * crossed_right +
1064 insert = 3 * crossed_left + 2 * crossed_up + 1 * crossed_right +
1069 if ( crossed_left + crossed_right == 2 && crossed_down + crossed_up == 0 )
1071 if ( xclp[iclp - 1] == xmin )
1099 if ( crossed_left + crossed_right == 0 && crossed_down + crossed_up == 2 )
1101 if ( yclp[iclp - 1] == ymin )
1129 for ( i = 0; i < 4; i++ )
1131 xclp[iclp] = (short) xlim[insert];
1132 yclp[iclp] = (short) ylim[insert];
1144 ( *draw )( xclp, yclp, iclp );
1146 if ( xclp != _xclp )
1152 #endif // USE_FILL_INTERSECTION_POLYGON
1182 PLFLT x1, y1, x2, y2, x3, y3;
1188 for ( i = 1; i < npts - 2; i++ )
1194 xproduct = xproduct + ( x2 - x1 ) * ( y3 - y2 ) - ( y2 - y1 ) * ( x3 - x2 );
1197 if ( xproduct > 0.0 )
1199 if ( xproduct < 0.0 )
1209 int i, return_value;
1212 if ( ( xint = (
PLINT *) malloc( (
size_t) n *
sizeof (
PLINT ) ) ) == NULL )
1214 plexit(
"PlP_pointinpolygon: Insufficient memory" );
1216 if ( ( yint = (
PLINT *) malloc( (
size_t) n *
sizeof (
PLINT ) ) ) == NULL )
1218 plexit(
"PlP_pointinpolygon: Insufficient memory" );
1220 for ( i = 0; i < n; i++ )
1222 xmaximum =
MAX( xmaximum, fabs( x[i] ) );
1223 ymaximum =
MAX( ymaximum, fabs( y[i] ) );
1225 xscale = 1.e8 / xmaximum;
1226 yscale = 1.e8 / ymaximum;
1227 for ( i = 0; i < n; i++ )
1230 yint[i] = (
PLINT) ( yscale * y[i] );
1236 return return_value;
1251 #define NEW_NOTPOINTINPOLYGON_CODE
1255 #ifdef NEW_NOTPOINTINPOLYGON_CODE
1256 int i, im1, ifnotcrossed;
1257 int count_crossings = 0;
1258 PLINT xmin, xout, yout, xintersect, yintersect;
1266 for ( i = 1; i < n; i++ )
1268 xout =
MAX( xout, x[i] );
1269 xmin =
MIN( xmin, x[i] );
1272 xout = xout + ( xout -
xmin ) + 10;
1278 for ( i = 0; i < n; i++ )
1280 if ( !( x[im1] == x[i] && y[im1] == y[i] ) )
1282 ifnotcrossed =
notcrossed( &xintersect, &yintersect,
1283 x[im1], y[im1], x[i], y[i],
1284 xp, yp, xout, yout );
1286 if ( !ifnotcrossed )
1298 if ( ( count_crossings % 2 ) == 1 )
1303 #else // NEW_NOTPOINTINPOLYGON_CODE
1305 int count_crossings;
1306 PLFLT x1, y1, x2, y2, xpp, ypp, xout, yout,
xmax;
1307 PLFLT xvp, yvp, xvv, yvv, xv1, yv1, xv2, yv2;
1308 PLFLT inprod1, inprod2;
1313 count_crossings = 0;
1321 for ( i = 0; i < n; i++ )
1332 xout = xout - ( xmax - xout );
1343 for ( i = 0; i < n; i++ )
1349 x2 = (
PLFLT) x[i + 1];
1350 y2 = (
PLFLT) y[i + 1];
1359 if ( x1 == x2 && y1 == y2 )
1370 inprod1 = xv1 * yvp - yv1 * xvp;
1371 inprod2 = xv2 * yvp - yv2 * xvp;
1372 if ( inprod1 * inprod2 >= 0.0 )
1386 inprod1 = xv1 * yvv - yv1 * xvv;
1387 inprod2 = xv2 * yvv - yv2 * xvv;
1388 if ( inprod1 * inprod2 >= 0.0 )
1401 return !( count_crossings % 2 );
1403 #endif // NEW_NOTPOINTINPOLYGON_CODE
1405 #define MAX_RECURSION_DEPTH 10
1453 #ifdef USE_FILL_INTERSECTION_POLYGON
1455 fill_intersection_polygon(
PLINT recursion_depth,
PLINT ifextrapolygon,
1457 void ( *fill )(
short *,
short *,
PLINT ),
1463 PLINT i1, i1m1, i1start_new,
1465 kk, kkstart1, kkstart21, kkstart22,
1467 range21, range22, ncrossed, ncrossed_change,
1468 nsplit1, nsplit2, nsplit2m1;
1469 PLINT xintersect[2], yintersect[2], i1intersect[2],
1471 PLINT *xsplit1, *ysplit1, *ifsplit1,
1472 *xsplit2, *ysplit2, *ifsplit2;
1473 PLINT ifill, nfill = 0,
1474 ifnotpolygon1inpolygon2, ifnotpolygon2inpolygon1;
1475 const PLINT *xfiller, *yfiller;
1476 short *xfill, *yfill;
1480 plwarn(
"fill_intersection_polygon: Recursion_depth too large. "
1481 "Probably an internal error figuring out intersections. " );
1487 plwarn(
"fill_intersection_polygon: Internal error; n1 < 3." );
1493 plwarn(
"fill_intersection_polygon: Internal error; n2 < 3." );
1497 if ( i1start < 0 || i1start >= n1 )
1499 plwarn(
"fill_intersection_polygon: invalid i1start." );
1508 for ( i1 = i1start; i1 < n1; i1++ )
1510 if ( x1[i1] == x1[i1m1] && y1[i1] == y1[i1m1] )
1517 plwarn(
"fill_intersection_polygon: Internal error; i1 < n1." );
1522 for ( i2 = 0; i2 < n2; i2++ )
1524 if ( x2[i2] == x2[i2m1] && y2[i2] == y2[i2m1] )
1531 plwarn(
"fill_intersection_polygon: Internal error; i2 < n2." );
1594 for ( i1 = i1start; i1 < n1; i1++ )
1596 ncrossed_change = number_crossings(
1597 &xintersect[ncrossed], &yintersect[ncrossed],
1598 &i2intersect[ncrossed], 2 - ncrossed,
1599 i1, n1, x1, y1, n2, x2, y2 );
1600 if ( ncrossed_change > 0 )
1602 i1intersect[ncrossed] = i1;
1603 if ( ncrossed_change == 2 )
1607 i1intersect[1] = i1;
1609 ncrossed += ncrossed_change;
1610 if ( ncrossed == 2 )
1625 range1 = i1intersect[1] - i1intersect[0];
1632 kkstart1 = i1intersect[0];
1637 range21 = i2intersect[0] - i2intersect[1];
1650 int ifxsort, ifascend;
1656 i2 = i2intersect[1];
1661 ifxsort = abs( x2[i2] - x2[i2m1] ) > abs( y2[i2] - y2[i2m1] );
1662 ifascend = ( ifxsort && x2[i2] > x2[i2m1] ) ||
1663 ( !ifxsort && y2[i2] > y2[i2m1] );
1664 if ( ( ifxsort && ifascend && xintersect[0] < xintersect[1] ) ||
1665 ( !ifxsort && ifascend && yintersect[0] < yintersect[1] ) ||
1666 ( ifxsort && !ifascend && xintersect[0] >= xintersect[1] ) ||
1667 ( !ifxsort && !ifascend && yintersect[0] >= yintersect[1] ) )
1673 kkstart21 = i2intersect[1];
1674 nsplit1 = 2 + range1 + range21;
1680 range22 = n2 - range21;
1682 kkstart22 = i2intersect[1] - 1;
1683 if ( kkstart22 < 0 )
1685 nsplit2 = 2 + range1 + range22;
1687 if ( ( xsplit1 = (
PLINT *) malloc( (
size_t) nsplit1 *
sizeof (
PLINT ) ) ) == NULL )
1689 plexit(
"fill_intersection_polygon: Insufficient memory" );
1691 if ( ( ysplit1 = (
PLINT *) malloc( (
size_t) nsplit1 *
sizeof (
PLINT ) ) ) == NULL )
1693 plexit(
"fill_intersection_polygon: Insufficient memory" );
1695 if ( ( ifsplit1 = (
PLINT *) malloc( (
size_t) nsplit1 *
sizeof (
PLINT ) ) ) == NULL )
1697 plexit(
"fill_intersection_polygon: Insufficient memory" );
1700 if ( ( xsplit2 = (
PLINT *) malloc( (
size_t) nsplit2 *
sizeof (
PLINT ) ) ) == NULL )
1702 plexit(
"fill_intersection_polygon: Insufficient memory" );
1704 if ( ( ysplit2 = (
PLINT *) malloc( (
size_t) nsplit2 *
sizeof (
PLINT ) ) ) == NULL )
1706 plexit(
"fill_intersection_polygon: Insufficient memory" );
1708 if ( ( ifsplit2 = (
PLINT *) malloc( (
size_t) nsplit2 *
sizeof (
PLINT ) ) ) == NULL )
1710 plexit(
"fill_intersection_polygon: Insufficient memory" );
1721 xsplit1[k] = xintersect[0];
1722 ysplit1[k] = yintersect[0];
1724 nsplit2m1 = nsplit2 - 1;
1725 xsplit2[nsplit2m1 - k] = xintersect[0];
1726 ysplit2[nsplit2m1 - k] = yintersect[0];
1727 ifsplit2[nsplit2m1 - k] = 1;
1733 for ( k = kstart; k < range1 + 1; k++ )
1735 xsplit1[k] = x1[kk];
1736 ysplit1[k] = y1[kk];
1738 xsplit2[nsplit2m1 - k] = x1[kk];
1739 ysplit2[nsplit2m1 - k] = y1[kk++];
1740 ifsplit2[nsplit2m1 - k] = 2;
1742 xsplit1[k] = xintersect[1];
1743 ysplit1[k] = yintersect[1];
1745 xsplit2[nsplit2m1 - k] = xintersect[1];
1746 ysplit2[nsplit2m1 - k] = yintersect[1];
1747 ifsplit2[nsplit2m1 - k] = 1;
1753 for ( k = kstart; k < nsplit1; k++ )
1755 xsplit1[k] = x2[kk];
1756 ysplit1[k] = y2[kk];
1757 ifsplit1[k] = if2[kk++];
1767 fill_intersection_polygon(
1768 recursion_depth + 1, ifextrapolygon, 1, fill,
1769 x1, y1, i1start_new, n1,
1770 xsplit1, ysplit1, ifsplit1, nsplit1 );
1778 for ( k = kstart; k < nsplit2; k++ )
1780 xsplit2[nsplit2m1 - k] = x2[kk];
1781 ysplit2[nsplit2m1 - k] = y2[kk];
1782 ifsplit2[nsplit2m1 - k] = if2[kk--];
1792 fill_intersection_polygon(
1793 recursion_depth + 1, ifextrapolygon, -1, fill,
1794 x1, y1, i1start_new, n1,
1795 xsplit2, ysplit2, ifsplit2, nsplit2 );
1805 if ( ncrossed != 0 )
1807 plwarn(
"fill_intersection_polygon: Internal error; ncrossed != 0." );
1816 if ( fill_status == -1 )
1818 else if ( fill_status == 1 )
1824 else if ( fill_status == 0 )
1827 if ( recursion_depth != 0 )
1829 plwarn(
"fill_intersection_polygon: Internal error; fill_status == 0 for recursion_depth > 0" );
1842 for ( i1 = 0; i1 < n1; i1++ )
1844 if ( ( ifnotpolygon1inpolygon2 =
1851 ifnotpolygon2inpolygon1 = 1;
1852 for ( i2 = 0; i2 < n2; i2++ )
1856 if ( !if2[i2] && ( ifnotpolygon2inpolygon1 =
1861 if ( ifnotpolygon2inpolygon1 == 0 && ifnotpolygon1inpolygon2 == 0 )
1862 plwarn(
"fill_intersection_polygon: Internal error; no intersections found but each polygon definitely inside the other!" );
1863 else if ( ifnotpolygon2inpolygon1 == 2 && ifnotpolygon1inpolygon2 == 2 )
1867 else if ( ifnotpolygon2inpolygon1 == 0 )
1874 else if ( ifnotpolygon1inpolygon2 == 0 )
1881 else if ( ifnotpolygon2inpolygon1 == 1 && ifnotpolygon1inpolygon2 == 1 )
1894 plwarn(
"fill_intersection_polygon: inscribed polygons are still ToDo" );
1900 if ( ( xfill = (
short *) malloc( (
size_t) nfill *
sizeof (
short ) ) ) == NULL )
1902 plexit(
"fill_intersection_polygon: Insufficient memory" );
1904 if ( ( yfill = (
short *) malloc( (
size_t) nfill *
sizeof (
short ) ) ) == NULL )
1906 plexit(
"fill_intersection_polygon: Insufficient memory" );
1908 for ( ifill = 0; ifill < nfill; ifill++ )
1910 xfill[ifill] = (short) xfiller[ifill];
1911 yfill[ifill] = (short) yfiller[ifill];
1913 ( *fill )( xfill, yfill, nfill );
1937 PLFLT factor, factor_NBCC, fxintersect, fyintersect;
1940 PLFLT xA2A1, yA2A1, xB2B1, yB2B1;
1941 PLFLT xB1A1, yB1A1, xB2A1, yB2A1;
1966 factor = xA2A1 * yB2B1 - yA2A1 * xB2B1;
1967 factor_NBCC =
PL_NBCC * ( fabs( xA2A1 ) + fabs( yB2B1 ) + fabs( yA2A1 ) + fabs( xB2B1 ) );
1968 if ( fabs( factor ) <= factor_NBCC )
1970 if ( fabs( factor ) > 0. )
1999 fxintersect = 0.25 * ( xA1 + xA2 + xB1 + xB2 );
2000 fyintersect = 0.25 * ( yA1 + yA2 + yB1 + yB2 );
2010 factor = ( xB1A1 * yB2A1 - yB1A1 * xB2A1 ) / factor;
2011 fxintersect = factor * xA2A1 + xA1;
2012 fyintersect = factor * yA2A1 + yA1;
2022 if ( fabs( fxintersect - xA1 ) <=
PL_NBCC && fabs( fyintersect - yA1 ) <=
PL_NBCC )
2024 else if ( fabs( fxintersect - xA2 ) <=
PL_NBCC && fabs( fyintersect - yA2 ) <=
PL_NBCC )
2026 else if ( fabs( fxintersect - xB1 ) <=
PL_NBCC && fabs( fyintersect - yB1 ) <=
PL_NBCC )
2028 else if ( fabs( fxintersect - xB2 ) <=
PL_NBCC && fabs( fyintersect - yB2 ) <=
PL_NBCC )
2035 *xintersect = (
PLINT) fxintersect;
2036 *yintersect = (
PLINT) fyintersect;
2041 #ifdef USE_FILL_INTERSECTION_POLYGON
2060 PLFLT twice_area = 0.;
2063 plwarn(
"positive_orientation: internal logic error, n < 3" );
2067 for ( i = 0; i < n; i++ )
2072 if ( twice_area == 0. )
2074 plwarn(
"positive_orientation: internal logic error, twice_area == 0." );
2078 return twice_area > 0.;
2098 int i1m1, i2, i2m1, ifnotcrossed;
2099 int ifxsort, ifascend, count_crossings = 0, status = 0;
2100 PLINT xintersect, yintersect;
2105 if ( !( ncross == 1 || ncross == 2 ) ||
2106 ( x1[i1m1] == x1[i1] && y1[i1m1] == y1[i1] ) || n1 < 2 || n2 < 2 )
2108 plwarn(
"findcrossings: invalid call" );
2112 ifxsort = abs( x1[i1] - x1[i1m1] ) > abs( y1[i1] - y1[i1m1] );
2113 ifascend = ( ifxsort && x1[i1] > x1[i1m1] ) ||
2114 ( !ifxsort && y1[i1] > y1[i1m1] );
2126 for ( i2 = 0; i2 < n2; i2++ )
2128 if ( !( x2[i2m1] == x2[i2] && y2[i2m1] == y2[i2] ) )
2130 ifnotcrossed =
notcrossed( &xintersect, &yintersect,
2131 x1[i1m1], y1[i1m1], x1[i1], y1[i1],
2132 x2[i2m1], y2[i2m1], x2[i2], y2[i2] );
2134 if ( !ifnotcrossed )
2137 if ( count_crossings == 1 )
2139 xcross[0] = xintersect;
2140 ycross[0] = yintersect;
2146 if ( ( ifxsort && ifascend && xintersect < xcross[0] ) ||
2147 ( !ifxsort && ifascend && yintersect < ycross[0] ) ||
2148 ( ifxsort && !ifascend && xintersect >= xcross[0] ) ||
2149 ( !ifxsort && !ifascend && yintersect >= ycross[0] ) )
2153 xcross[1] = xcross[0];
2154 ycross[1] = ycross[0];
2155 i2cross[1] = i2cross[0];
2158 xcross[0] = xintersect;
2159 ycross[0] = yintersect;
2162 else if ( ncross == 2 && ( count_crossings == 2 || (
2163 ( ifxsort && ifascend && xintersect < xcross[1] ) ||
2164 ( !ifxsort && ifascend && yintersect < ycross[1] ) ||
2165 ( ifxsort && !ifascend && xintersect >= xcross[1] ) ||
2166 ( !ifxsort && !ifascend && yintersect >= ycross[1] ) ) ) )
2168 xcross[1] = xintersect;
2169 ycross[1] = yintersect;
void c_plfill3(PLINT n, const PLFLT *x, const PLFLT *y, const PLFLT *z)
static int compar(const void *, const void *)
static int notcrossed(PLINT *xintersect, PLINT *yintersect, PLINT xA1, PLINT yA1, PLINT xA2, PLINT yA2, PLINT xB1, PLINT yB1, PLINT xB2, PLINT yB2)
int plP_pointinpolygon(PLINT n, const PLFLT *x, const PLFLT *y, PLFLT xp, PLFLT yp)
void plP_grange(PLFLT *p_zscl, PLFLT *p_zmin, PLFLT *p_zmax)
int plP_clipline(PLINT *p_x1, PLINT *p_y1, PLINT *p_x2, PLINT *p_y2, PLINT xmin, PLINT xmax, PLINT ymin, PLINT ymax)
void PLFLT PLINT PLINT PLFLT x
void PLFLT PLINT PLINT PLFLT PLFLT PLFLT PLFLT PLINT PLINT PLINT PLFLT PLFLT PLINT PLFLT PLINT const PLINT const char *const PLINT const char *const const PLFLT const PLINT const PLINT const PLFLT * a
static void tran(PLINT *, PLINT *, PLFLT, PLFLT)
static int notpointinpolygon(PLINT n, const PLINT *x, const PLINT *y, PLINT xp, PLINT yp)
int plP_clip_poly(int Ni, PLFLT *Vi[3], int axis, PLFLT dir, PLFLT offset)
void PLFLT PLINT PLINT PLFLT PLFLT y
#define TRANSFORM(x, y, xnew, ynew)
static void addcoord(PLINT, PLINT)
PLFLT plP_w3wcy(PLFLT x, PLFLT y, PLFLT z)
#define BETW_NBCC(ix, ia, ib)
static int circulation(PLINT *x, PLINT *y, PLINT npts)
static void buildlist(PLINT, PLINT, PLINT, PLINT, PLINT, PLINT, PLINT)
void plabort(const char *errormsg)
void plP_draphy(PLINT x, PLINT y)
void plP_fill(short *x, short *y, PLINT npts)
void plfill_soft(short *x, short *y, PLINT n)
PLFLT plP_w3wcx(PLFLT x, PLFLT y, PLFLT PL_UNUSED(z))
void plwarn(const char *errormsg)
void plP_movphy(PLINT x, PLINT y)
#define MAX_RECURSION_DEPTH
void plP_plfclp(PLINT *x, PLINT *y, PLINT npts, PLINT xmin, PLINT xmax, PLINT ymin, PLINT ymax, void(*draw)(short *, short *, PLINT))
void c_plfill(PLINT n, const PLFLT *x, const PLFLT *y)
dx
if { $zoomopts($this,1) == 0 } then {
void plP_gdom(PLFLT *p_xmin, PLFLT *p_xmax, PLFLT *p_ymin, PLFLT *p_ymax)
void plexit(const char *errormsg)