Menu
▾
▴
[Plplot-cvs] SF.net SVN: plplot:[10651] trunk
|
From: <ai...@us...> - 2009-11-30 17:57:39
|
Revision: 10651
http://plplot.svn.sourceforge.net/plplot/?rev=10651&view=rev
Author: airwin
Date: 2009-11-30 17:57:25 +0000 (Mon, 30 Nov 2009)
Log Message:
-----------
Move plP_plfclp and associated routines from plline.c to its more natural
position in plfill.c
Modified Paths:
--------------
trunk/include/plplotP.h
trunk/src/plfill.c
trunk/src/plline.c
Modified: trunk/include/plplotP.h
===================================================================
--- trunk/include/plplotP.h 2009-11-30 12:05:36 UTC (rev 10650)
+++ trunk/include/plplotP.h 2009-11-30 17:57:25 UTC (rev 10651)
@@ -468,6 +468,12 @@
int
plP_clip_poly( int Ni, PLFLT *Vi[3], int axis, PLFLT dir, PLFLT offset );
+/* Get clipped endpoints */
+
+int
+plP_clipline( PLINT *p_x1, PLINT *p_y1, PLINT *p_x2, PLINT *p_y2,
+ PLINT xmin, PLINT xmax, PLINT ymin, PLINT ymax );
+
/* Stores hex digit value into FCI (font characterization integer). */
void
plP_hex2fci( unsigned char hexdigit, unsigned char hexpower, PLUNICODE *pfci );
Modified: trunk/src/plfill.c
===================================================================
--- trunk/src/plfill.c 2009-11-30 12:05:36 UTC (rev 10650)
+++ trunk/src/plfill.c 2009-11-30 17:57:25 UTC (rev 10651)
@@ -24,6 +24,8 @@
#include "plplotP.h"
+#define INSIDE( ix, iy ) ( BETW( ix, xmin, xmax ) && BETW( iy, ymin, ymax ))
+
#define DTOR 0.0174533
#define BINC 50
@@ -36,11 +38,25 @@
/* Static function prototypes */
/* INDENT OFF */
-static int compar( const void *, const void * );
-static void addcoord( PLINT, PLINT );
-static void tran( PLINT *, PLINT *, PLFLT, PLFLT );
-static void buildlist( PLINT, PLINT, PLINT, PLINT, PLINT, PLINT, PLINT );
+static int
+compar( const void *, const void * );
+static void
+addcoord( PLINT, PLINT );
+
+static void
+tran( PLINT *, PLINT *, PLFLT, PLFLT );
+
+static void
+buildlist( PLINT, PLINT, PLINT, PLINT, PLINT, PLINT, PLINT );
+
+static int
+pointinpolygon( PLINT n, PLINT *x, PLINT *y, PLINT xp, PLINT yp );
+
+static int
+circulation( PLINT *x, PLINT *y, PLINT npts );
+
+
/* INDENT ON */
/*----------------------------------------------------------------------*\
@@ -382,3 +398,649 @@
return 0;
}
+
+/*----------------------------------------------------------------------*\
+ * void plP_plfclp()
+ *
+ * Fills a polygon within the clip limits.
+ \*----------------------------------------------------------------------*/
+
+void
+plP_plfclp( PLINT *x, PLINT *y, PLINT npts,
+ PLINT xmin, PLINT xmax, PLINT ymin, PLINT ymax,
+ void ( *draw )( short *, short *, PLINT ))
+{
+ PLINT i, x1, x2, y1, y2;
+ int iclp = 0, iout = 2;
+ short _xclp[2 * PL_MAXPOLY + 2], _yclp[2 * PL_MAXPOLY + 2];
+ short *xclp, *yclp;
+ int drawable;
+ int crossed_xmin1 = 0, crossed_xmax1 = 0;
+ int crossed_ymin1 = 0, crossed_ymax1 = 0;
+ int crossed_xmin2 = 0, crossed_xmax2 = 0;
+ int crossed_ymin2 = 0, crossed_ymax2 = 0;
+ int crossed_up = 0, crossed_down = 0;
+ int crossed_left = 0, crossed_right = 0;
+ int inside_lb;
+ int inside_lu;
+ int inside_rb;
+ int inside_ru;
+
+/* Must have at least 3 points and draw() specified */
+ if ( npts < 3 || !draw ) return;
+
+ if ( npts < PL_MAXPOLY )
+ {
+ xclp = _xclp;
+ yclp = _yclp;
+ }
+ else
+ {
+ if ((( xclp = (short *) malloc(( 2 * npts + 2 ) * sizeof ( short ))) == NULL ) ||
+ (( yclp = (short *) malloc(( 2 * npts + 2 ) * sizeof ( short ))) == NULL ))
+ {
+ 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 );
+ inside_ru = pointinpolygon( npts, x, y, xmax, ymax );
+
+ for ( i = 0; i < npts - 1; i++ )
+ {
+ x1 = x[i]; x2 = x[i + 1];
+ y1 = y[i]; y2 = y[i + 1];
+
+ drawable = ( INSIDE( x1, y1 ) && INSIDE( x2, y2 ));
+ if ( !drawable )
+ drawable = !plP_clipline( &x1, &y1, &x2, &y2,
+ xmin, xmax, ymin, ymax );
+
+ if ( drawable )
+ {
+ /* Boundary crossing condition -- coming in. */
+ crossed_xmin2 = ( x1 == xmin ); crossed_xmax2 = ( x1 == xmax );
+ crossed_ymin2 = ( y1 == ymin ); crossed_ymax2 = ( y1 == ymax );
+
+ crossed_left = ( crossed_left || crossed_xmin2 );
+ crossed_right = ( crossed_right || crossed_xmax2 );
+ crossed_down = ( crossed_down || crossed_ymin2 );
+ crossed_up = ( crossed_up || crossed_ymax2 );
+ iout = iclp + 2;
+ /* If the first segment, just add it. */
+
+ if ( iclp == 0 )
+ {
+ xclp[iclp] = x1; yclp[iclp] = y1; iclp++;
+ xclp[iclp] = x2; yclp[iclp] = y2; iclp++;
+ }
+
+ /* Not first point. If first point of this segment matches up to the
+ * previous point, just add it. */
+
+ else if ( x1 == xclp[iclp - 1] && y1 == yclp[iclp - 1] )
+ {
+ xclp[iclp] = x2; yclp[iclp] = y2; iclp++;
+ }
+
+ /* Otherwise, we need to add both points, to connect the points in the
+ * polygon along the clip boundary. If we encircled a corner, we have
+ * to add that first.
+ */
+
+ else
+ {
+ /* Treat the case where we encircled two corners:
+ * Construct a polygon out of the subset of vertices
+ * Note that the direction is important too when adding
+ * the extra points */
+ xclp[iclp + 1] = x2; yclp[iclp + 1] = y2;
+ xclp[iclp + 2] = x1; yclp[iclp + 2] = y1;
+ iout = iout - iclp + 1;
+ /* Upper two */
+ if ((( crossed_xmin1 && crossed_xmax2 ) ||
+ ( crossed_xmin2 && crossed_xmax1 )) &&
+ inside_lu )
+ {
+ if ( crossed_xmin1 )
+ {
+ xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
+ xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
+ }
+ else
+ {
+ xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
+ xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
+ }
+ }
+ /* Lower two */
+ else if ((( crossed_xmin1 && crossed_xmax2 ) ||
+ ( crossed_xmin2 && crossed_xmax1 )) &&
+ inside_lb )
+ {
+ if ( crossed_xmin1 )
+ {
+ xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
+ xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
+ }
+ else
+ {
+ xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
+ xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
+ }
+ }
+ /* Left two */
+ else if ((( crossed_ymin1 && crossed_ymax2 ) ||
+ ( crossed_ymin2 && crossed_ymax1 )) &&
+ inside_lb )
+ {
+ if ( crossed_ymin1 )
+ {
+ xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
+ xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
+ }
+ else
+ {
+ xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
+ xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
+ }
+ }
+ /* Right two */
+ else if ((( crossed_ymin1 && crossed_ymax2 ) ||
+ ( crossed_ymin2 && crossed_ymax1 )) &&
+ inside_rb )
+ {
+ if ( crossed_ymin1 )
+ {
+ xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
+ xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
+ }
+ else
+ {
+ xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
+ xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
+ }
+ }
+ /* Now the case where we encircled one corner */
+ /* Lower left */
+ else if (( crossed_xmin1 && crossed_ymin2 ) ||
+ ( crossed_ymin1 && crossed_xmin2 ))
+ {
+ xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
+ }
+ /* Lower right */
+ else if (( crossed_xmax1 && crossed_ymin2 ) ||
+ ( crossed_ymin1 && crossed_xmax2 ))
+ {
+ xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
+ }
+ /* Upper left */
+ else if (( crossed_xmin1 && crossed_ymax2 ) ||
+ ( crossed_ymax1 && crossed_xmin2 ))
+ {
+ xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
+ }
+ /* Upper right */
+ else if (( crossed_xmax1 && crossed_ymax2 ) ||
+ ( crossed_ymax1 && crossed_xmax2 ))
+ {
+ xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
+ }
+
+ /* Now add current segment. */
+ xclp[iclp] = x1; yclp[iclp] = y1; iclp++;
+ xclp[iclp] = x2; yclp[iclp] = y2; iclp++;
+ }
+
+ /* Boundary crossing condition -- going out. */
+ crossed_xmin1 = ( x2 == xmin ); crossed_xmax1 = ( x2 == xmax );
+ crossed_ymin1 = ( y2 == ymin ); crossed_ymax1 = ( y2 == ymax );
+ }
+ }
+
+/* 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 )
+ {
+ xclp[0] = xmin; yclp[0] = ymin;
+ xclp[1] = xmax; yclp[1] = ymin;
+ xclp[2] = xmax; yclp[2] = ymax;
+ xclp[3] = xmin; yclp[3] = ymax;
+ xclp[4] = xmin; yclp[4] = ymin;
+ ( *draw )( xclp, yclp, 5 );
+
+ if ( xclp != _xclp )
+ {
+ free( xclp );
+ free( yclp );
+ }
+
+
+ return;
+ }
+ }
+
+/* Now handle cases where fill polygon intersects two sides of the box */
+
+ if ( iclp >= 2 )
+ {
+ int debug = 0;
+ int dir = circulation( x, y, npts );
+ if ( debug )
+ {
+ if (( xclp[0] == xmin && xclp[iclp - 1] == xmax ) ||
+ ( xclp[0] == xmax && xclp[iclp - 1] == xmin ) ||
+ ( yclp[0] == ymin && yclp[iclp - 1] == ymax ) ||
+ ( yclp[0] == ymax && yclp[iclp - 1] == ymin ) ||
+ ( xclp[0] == xmin && yclp[iclp - 1] == ymin ) ||
+ ( yclp[0] == ymin && xclp[iclp - 1] == xmin ) ||
+ ( xclp[0] == xmax && yclp[iclp - 1] == ymin ) ||
+ ( yclp[0] == ymin && xclp[iclp - 1] == xmax ) ||
+ ( xclp[0] == xmax && yclp[iclp - 1] == ymax ) ||
+ ( yclp[0] == ymax && xclp[iclp - 1] == xmax ) ||
+ ( xclp[0] == xmin && yclp[iclp - 1] == ymax ) ||
+ ( yclp[0] == ymax && xclp[iclp - 1] == xmin ))
+ {
+ printf( "dir=%d, clipped points:\n", dir );
+ for ( i = 0; i < iclp; i++ )
+ printf( " x[%d]=%d y[%d]=%d", i, xclp[i], i, yclp[i] );
+ printf( "\n" );
+ printf( "pre-clipped points:\n" );
+ for ( i = 0; i < npts; i++ )
+ printf( " x[%d]=%d y[%d]=%d", i, x[i], i, y[i] );
+ printf( "\n" );
+ }
+ }
+
+ /* The cases where the fill region is divided 2/2 */
+ /* Divided horizontally */
+ if ( xclp[0] == xmin && xclp[iclp - 1] == xmax )
+ {
+ if ( dir > 0 )
+ {
+ xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
+ xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
+ }
+ else
+ {
+ xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
+ xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
+ }
+ }
+ else if ( xclp[0] == xmax && xclp[iclp - 1] == xmin )
+ {
+ if ( dir > 0 )
+ {
+ xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
+ xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
+ }
+ else
+ {
+ xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
+ xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
+ }
+ }
+
+ /* Divided vertically */
+ else if ( yclp[0] == ymin && yclp[iclp - 1] == ymax )
+ {
+ if ( dir > 0 )
+ {
+ xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
+ xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
+ }
+ else
+ {
+ xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
+ xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
+ }
+ }
+ else if ( yclp[0] == ymax && yclp[iclp - 1] == ymin )
+ {
+ if ( dir > 0 )
+ {
+ xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
+ xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
+ }
+ else
+ {
+ xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
+ xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
+ }
+ }
+
+ /* The cases where the fill region is divided 3/1 --
+ * LL LR UR UL
+ +-----+ +-----+ +-----+ +-----+
+ | | | | | \| |/ |
+ | | | | | | | |
+ |\ | | /| | | | |
+ +-----+ +-----+ +-----+ +-----+
+ *
+ * Note when we go the long way around, if the direction is reversed the
+ * three vertices must be visited in the opposite order.
+ */
+ /* LL, short way around */
+ else if (( xclp[0] == xmin && yclp[iclp - 1] == ymin && dir < 0 ) ||
+ ( yclp[0] == ymin && xclp[iclp - 1] == xmin && dir > 0 ))
+ {
+ xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
+ }
+ /* LL, long way around, counterclockwise */
+ else if (( xclp[0] == xmin && yclp[iclp - 1] == ymin && dir > 0 ))
+ {
+ xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
+ xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
+ xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
+ }
+ /* LL, long way around, clockwise */
+ else if (( yclp[0] == ymin && xclp[iclp - 1] == xmin && dir < 0 ))
+ {
+ xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
+ xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
+ xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
+ }
+ /* LR, short way around */
+ else if (( xclp[0] == xmax && yclp[iclp - 1] == ymin && dir > 0 ) ||
+ ( yclp[0] == ymin && xclp[iclp - 1] == xmax && dir < 0 ))
+ {
+ xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
+ }
+ /* LR, long way around, counterclockwise */
+ else if ( yclp[0] == ymin && xclp[iclp - 1] == xmax && dir > 0 )
+ {
+ xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
+ xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
+ xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
+ }
+ /* LR, long way around, clockwise */
+ else if ( xclp[0] == xmax && yclp[iclp - 1] == ymin && dir < 0 )
+ {
+ xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
+ xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
+ xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
+ }
+ /* UR, short way around */
+ else if (( xclp[0] == xmax && yclp[iclp - 1] == ymax && dir < 0 ) ||
+ ( yclp[0] == ymax && xclp[iclp - 1] == xmax && dir > 0 ))
+ {
+ xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
+ }
+ /* UR, long way around, counterclockwise */
+ else if ( xclp[0] == xmax && yclp[iclp - 1] == ymax && dir > 0 )
+ {
+ xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
+ xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
+ xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
+ }
+ /* UR, long way around, clockwise */
+ else if ( yclp[0] == ymax && xclp[iclp - 1] == xmax && dir < 0 )
+ {
+ xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
+ xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
+ xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
+ }
+ /* UL, short way around */
+ else if (( xclp[0] == xmin && yclp[iclp - 1] == ymax && dir > 0 ) ||
+ ( yclp[0] == ymax && xclp[iclp - 1] == xmin && dir < 0 ))
+ {
+ xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
+ }
+ /* UL, long way around, counterclockwise */
+ else if ( yclp[0] == ymax && xclp[iclp - 1] == xmin && dir > 0 )
+ {
+ xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
+ xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
+ xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
+ }
+ /* UL, long way around, clockwise */
+ else if ( xclp[0] == xmin && yclp[iclp - 1] == ymax && dir < 0 )
+ {
+ xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
+ xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
+ xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
+ }
+ }
+
+/* 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 ( crossed_left + crossed_right + crossed_down + crossed_up == 1 &&
+ inside_lb + inside_rb + inside_lu + inside_ru == 4 )
+ {
+ int dir = circulation( x, y, npts );
+ PLINT xlim[4], ylim[4];
+ int insert;
+ int incr;
+
+ xlim[0] = xmin; ylim[0] = ymin;
+ xlim[1] = xmax; ylim[1] = ymin;
+ xlim[2] = xmax; ylim[2] = ymax;
+ xlim[3] = xmin; ylim[3] = ymax;
+ if ( dir > 0 )
+ {
+ incr = 1;
+ insert = 0 * crossed_left + 1 * crossed_down + 2 * crossed_right +
+ 3 * crossed_up;
+ }
+ else
+ {
+ incr = -1;
+ insert = 3 * crossed_left + 2 * crossed_up + 1 * crossed_right +
+ 0 * crossed_down;
+ }
+ for ( i = 0; i < 4; i++ )
+ {
+ xclp[iclp] = xlim[insert];
+ yclp[iclp] = ylim[insert];
+ iclp++;
+ insert += incr;
+ if ( insert > 3 ) insert = 0;
+ if ( insert < 0 ) insert = 3;
+ }
+ }
+
+/* Draw the sucker */
+ if ( iclp >= 3 )
+ ( *draw )( xclp, yclp, iclp );
+
+ if ( xclp != _xclp )
+ {
+ free( xclp );
+ free( yclp );
+ }
+}
+
+/*----------------------------------------------------------------------*\
+ * int circulation()
+ *
+ * Returns the circulation direction for a given polyline: positive is
+ * counterclockwise, negative is clockwise (right hand rule).
+ *
+ * Used to get the circulation of the fill polygon around the bounding box,
+ * when the fill polygon is larger than the bounding box. Counts left
+ * (positive) vs right (negative) hand turns using a cross product, instead of
+ * performing all the expensive trig calculations needed to get this 100%
+ * correct. For the fill cases encountered in plplot, this treatment should
+ * give the correct answer most of the time, by far. When used with plshades,
+ * the typical return value is 3 or -3, since 3 turns are necessary in order
+ * to complete the fill region. Only for really oddly shaped fill regions
+ * will it give the wrong answer.
+ *
+ * AM:
+ * Changed the computation: use the outer product to compute the surface
+ * area, the sign determines if the polygon is followed clockwise or
+ * counterclockwise. This is more reliable. Floating-point numbers
+ * are used to avoid overflow.
+ \*----------------------------------------------------------------------*/
+
+static int
+circulation( PLINT *x, PLINT *y, PLINT npts )
+{
+ PLFLT xproduct;
+ int direction = 0;
+ PLFLT x1, y1, x2, y2, x3, y3;
+ int i;
+
+ xproduct = 0.0;
+ x1 = x[0];
+ y1 = y[0];
+ for ( i = 1; i < npts - 2; i++ )
+ {
+ x2 = x[i + 1];
+ y2 = y[i + 1];
+ x3 = x[i + 2];
+ y3 = y[i + 2];
+ xproduct = xproduct + ( x2 - x1 ) * ( y3 - y2 ) - ( y2 - y1 ) * ( x3 - x2 );
+ }
+
+ if ( xproduct > 0.0 ) direction = 1;
+ if ( xproduct < 0.0 ) direction = -1;
+ return direction;
+}
+
+/*----------------------------------------------------------------------*\
+ * int pointinpolygon()
+ *
+ * PLINT wrapper for plP_pointinpolygon.
+ \*----------------------------------------------------------------------*/
+
+static int
+pointinpolygon( PLINT n, PLINT *x, PLINT *y, PLINT xp, PLINT yp )
+{
+ int i, return_value;
+ PLFLT *xflt, *yflt;
+ if (( xflt = (PLFLT *) malloc( n * sizeof ( PLFLT ))) == NULL )
+ {
+ plexit( "pointinpolygon: Insufficient memory" );
+ }
+ if (( yflt = (PLFLT *) malloc( n * sizeof ( PLFLT ))) == NULL )
+ {
+ plexit( "pointinpolygon: Insufficient memory" );
+ }
+ for ( i = 0; i < n; i++ )
+ {
+ xflt[i] = (PLFLT) x[i];
+ yflt[i] = (PLFLT) y[i];
+ }
+ return_value = plP_pointinpolygon( n, xflt, yflt, (PLFLT) xp, (PLFLT) yp );
+ free( xflt );
+ free( yflt );
+ return return_value;
+}
+/*----------------------------------------------------------------------*\
+ * int plP_pointinpolygon()
+ *
+ * Returns 1 if the point is inside the polygon, 0 otherwise
+ * Notes:
+ * Points on the polygon are considered to be outside.
+ * This "Ray casting algorithm" has been described in
+ * http://en.wikipedia.org/wiki/Point_in_polygon.
+ * Logic still needs to be inserted to take care of the "ray passes
+ * through vertex" problem in a numerically robust way.
+ \*----------------------------------------------------------------------*/
+
+int
+plP_pointinpolygon( PLINT n, PLFLT *x, PLFLT *y, PLFLT xp, PLFLT yp )
+{
+ 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;
+
+ count_crossings = 0;
+
+
+ /* Determine a point outside the polygon */
+
+ xmax = x[0];
+ xout = x[0];
+ yout = y[0];
+ for ( i = 0; i < n; i++ )
+ {
+ if ( xout > x[i] )
+ {
+ xout = x[i];
+ }
+ if ( xmax < x[i] )
+ {
+ xmax = x[i];
+ }
+ }
+ xout = xout - ( xmax - xout );
+
+ /* Determine for each side whether the line segment between
+ * our two points crosses the vertex */
+
+ xvp = xp - xout;
+ yvp = yp - yout;
+
+ for ( i = 0; i < n; i++ )
+ {
+ x1 = x[i];
+ y1 = y[i];
+ if ( i < n - 1 )
+ {
+ x2 = x[i + 1];
+ y2 = y[i + 1];
+ }
+ else
+ {
+ x2 = x[0];
+ y2 = y[0];
+ }
+
+ /* Skip zero-length segments */
+ if ( x1 == x2 && y1 == y2 )
+ {
+ continue;
+ }
+
+ /* Line through the two fixed points:
+ * Are x1 and x2 on either side? */
+ xv1 = x1 - xout;
+ yv1 = y1 - yout;
+ xv2 = x2 - xout;
+ yv2 = y2 - yout;
+ inprod1 = xv1 * yvp - yv1 * xvp; /* Well, with the normal vector */
+ inprod2 = xv2 * yvp - yv2 * xvp;
+ if ( inprod1 * inprod2 >= 0.0 )
+ {
+ /* No crossing possible! */
+ continue;
+ }
+
+ /* Line through the two vertices:
+ * Are xout and xp on either side? */
+ xvv = x2 - x1;
+ yvv = y2 - y1;
+ xv1 = xp - x1;
+ yv1 = yp - y1;
+ xv2 = xout - x1;
+ yv2 = yout - y1;
+ inprod1 = xv1 * yvv - yv1 * xvv;
+ inprod2 = xv2 * yvv - yv2 * xvv;
+ if ( inprod1 * inprod2 >= 0.0 )
+ {
+ /* No crossing possible! */
+ continue;
+ }
+
+ /* We do have a crossing */
+ count_crossings++;
+ }
+
+ /* Return the result: an even number of crossings means the
+ * point is outside the polygon */
+
+ return ( count_crossings % 2 );
+}
Modified: trunk/src/plline.c
===================================================================
--- trunk/src/plline.c 2009-11-30 12:05:36 UTC (rev 10650)
+++ trunk/src/plline.c 2009-11-30 17:57:25 UTC (rev 10651)
@@ -37,12 +37,6 @@
static void
pllclp( PLINT *x, PLINT *y, PLINT npts );
-/* Get clipped endpoints */
-
-static int
-clipline( PLINT *p_x1, PLINT *p_y1, PLINT *p_x2, PLINT *p_y2,
- PLINT xmin, PLINT xmax, PLINT ymin, PLINT ymax );
-
/* General line-drawing routine. Takes line styles into account. */
static void
@@ -55,9 +49,6 @@
/* Determines if a point is inside a polygon or not */
-static int
-pointinpolygon( PLINT n, PLINT *x, PLINT *y, PLINT xp, PLINT yp );
-
/*----------------------------------------------------------------------*\
* void pljoin()
*
@@ -593,7 +584,8 @@
drawable = ( INSIDE( x1, y1 ) && INSIDE( x2, y2 ));
if ( !drawable )
- drawable = !clipline( &x1, &y1, &x2, &y2, xmin, xmax, ymin, ymax );
+ drawable = !plP_clipline( &x1, &y1, &x2, &y2,
+ xmin, xmax, ymin, ymax );
if ( drawable )
{
@@ -650,521 +642,13 @@
}
/*----------------------------------------------------------------------*\
- * int circulation()
+ * int plP_clipline()
*
- * Returns the circulation direction for a given polyline: positive is
- * counterclockwise, negative is clockwise (right hand rule).
- *
- * Used to get the circulation of the fill polygon around the bounding box,
- * when the fill polygon is larger than the bounding box. Counts left
- * (positive) vs right (negative) hand turns using a cross product, instead of
- * performing all the expensive trig calculations needed to get this 100%
- * correct. For the fill cases encountered in plplot, this treatment should
- * give the correct answer most of the time, by far. When used with plshades,
- * the typical return value is 3 or -3, since 3 turns are necessary in order
- * to complete the fill region. Only for really oddly shaped fill regions
- * will it give the wrong answer.
- *
- * AM:
- * Changed the computation: use the outer product to compute the surface
- * area, the sign determines if the polygon is followed clockwise or
- * counterclockwise. This is more reliable. Floating-point numbers
- * are used to avoid overflow.
- \*----------------------------------------------------------------------*/
-
-static int
-circulation( PLINT *x, PLINT *y, PLINT npts )
-{
- PLFLT xproduct;
- int direction = 0;
- PLFLT x1, y1, x2, y2, x3, y3;
- int i;
-
- xproduct = 0.0;
- x1 = x[0];
- y1 = y[0];
- for ( i = 1; i < npts - 2; i++ )
- {
- x2 = x[i + 1];
- y2 = y[i + 1];
- x3 = x[i + 2];
- y3 = y[i + 2];
- xproduct = xproduct + ( x2 - x1 ) * ( y3 - y2 ) - ( y2 - y1 ) * ( x3 - x2 );
- }
-
- if ( xproduct > 0.0 ) direction = 1;
- if ( xproduct < 0.0 ) direction = -1;
- return direction;
-}
-
-/*----------------------------------------------------------------------*\
- * void plP_plfclp()
- *
- * Fills a polygon within the clip limits.
- \*----------------------------------------------------------------------*/
-
-void
-plP_plfclp( PLINT *x, PLINT *y, PLINT npts,
- PLINT xmin, PLINT xmax, PLINT ymin, PLINT ymax,
- void ( *draw )( short *, short *, PLINT ))
-{
- PLINT i, x1, x2, y1, y2;
- int iclp = 0, iout = 2;
- short _xclp[2 * PL_MAXPOLY + 2], _yclp[2 * PL_MAXPOLY + 2];
- short *xclp, *yclp;
- int drawable;
- int crossed_xmin1 = 0, crossed_xmax1 = 0;
- int crossed_ymin1 = 0, crossed_ymax1 = 0;
- int crossed_xmin2 = 0, crossed_xmax2 = 0;
- int crossed_ymin2 = 0, crossed_ymax2 = 0;
- int crossed_up = 0, crossed_down = 0;
- int crossed_left = 0, crossed_right = 0;
- int inside_lb;
- int inside_lu;
- int inside_rb;
- int inside_ru;
-
-/* Must have at least 3 points and draw() specified */
- if ( npts < 3 || !draw ) return;
-
- if ( npts < PL_MAXPOLY )
- {
- xclp = _xclp;
- yclp = _yclp;
- }
- else
- {
- if ((( xclp = (short *) malloc(( 2 * npts + 2 ) * sizeof ( short ))) == NULL ) ||
- (( yclp = (short *) malloc(( 2 * npts + 2 ) * sizeof ( short ))) == NULL ))
- {
- 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 );
- inside_ru = pointinpolygon( npts, x, y, xmax, ymax );
-
- for ( i = 0; i < npts - 1; i++ )
- {
- x1 = x[i]; x2 = x[i + 1];
- y1 = y[i]; y2 = y[i + 1];
-
- drawable = ( INSIDE( x1, y1 ) && INSIDE( x2, y2 ));
- if ( !drawable )
- drawable = !clipline( &x1, &y1, &x2, &y2, xmin, xmax, ymin, ymax );
-
- if ( drawable )
- {
- /* Boundary crossing condition -- coming in. */
- crossed_xmin2 = ( x1 == xmin ); crossed_xmax2 = ( x1 == xmax );
- crossed_ymin2 = ( y1 == ymin ); crossed_ymax2 = ( y1 == ymax );
-
- crossed_left = ( crossed_left || crossed_xmin2 );
- crossed_right = ( crossed_right || crossed_xmax2 );
- crossed_down = ( crossed_down || crossed_ymin2 );
- crossed_up = ( crossed_up || crossed_ymax2 );
- iout = iclp + 2;
- /* If the first segment, just add it. */
-
- if ( iclp == 0 )
- {
- xclp[iclp] = x1; yclp[iclp] = y1; iclp++;
- xclp[iclp] = x2; yclp[iclp] = y2; iclp++;
- }
-
- /* Not first point. If first point of this segment matches up to the
- * previous point, just add it. */
-
- else if ( x1 == xclp[iclp - 1] && y1 == yclp[iclp - 1] )
- {
- xclp[iclp] = x2; yclp[iclp] = y2; iclp++;
- }
-
- /* Otherwise, we need to add both points, to connect the points in the
- * polygon along the clip boundary. If we encircled a corner, we have
- * to add that first.
- */
-
- else
- {
- /* Treat the case where we encircled two corners:
- * Construct a polygon out of the subset of vertices
- * Note that the direction is important too when adding
- * the extra points */
- xclp[iclp + 1] = x2; yclp[iclp + 1] = y2;
- xclp[iclp + 2] = x1; yclp[iclp + 2] = y1;
- iout = iout - iclp + 1;
- /* Upper two */
- if ((( crossed_xmin1 && crossed_xmax2 ) ||
- ( crossed_xmin2 && crossed_xmax1 )) &&
- inside_lu )
- {
- if ( crossed_xmin1 )
- {
- xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
- xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
- }
- else
- {
- xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
- xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
- }
- }
- /* Lower two */
- else if ((( crossed_xmin1 && crossed_xmax2 ) ||
- ( crossed_xmin2 && crossed_xmax1 )) &&
- inside_lb )
- {
- if ( crossed_xmin1 )
- {
- xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
- xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
- }
- else
- {
- xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
- xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
- }
- }
- /* Left two */
- else if ((( crossed_ymin1 && crossed_ymax2 ) ||
- ( crossed_ymin2 && crossed_ymax1 )) &&
- inside_lb )
- {
- if ( crossed_ymin1 )
- {
- xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
- xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
- }
- else
- {
- xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
- xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
- }
- }
- /* Right two */
- else if ((( crossed_ymin1 && crossed_ymax2 ) ||
- ( crossed_ymin2 && crossed_ymax1 )) &&
- inside_rb )
- {
- if ( crossed_ymin1 )
- {
- xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
- xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
- }
- else
- {
- xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
- xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
- }
- }
- /* Now the case where we encircled one corner */
- /* Lower left */
- else if (( crossed_xmin1 && crossed_ymin2 ) ||
- ( crossed_ymin1 && crossed_xmin2 ))
- {
- xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
- }
- /* Lower right */
- else if (( crossed_xmax1 && crossed_ymin2 ) ||
- ( crossed_ymin1 && crossed_xmax2 ))
- {
- xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
- }
- /* Upper left */
- else if (( crossed_xmin1 && crossed_ymax2 ) ||
- ( crossed_ymax1 && crossed_xmin2 ))
- {
- xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
- }
- /* Upper right */
- else if (( crossed_xmax1 && crossed_ymax2 ) ||
- ( crossed_ymax1 && crossed_xmax2 ))
- {
- xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
- }
-
- /* Now add current segment. */
- xclp[iclp] = x1; yclp[iclp] = y1; iclp++;
- xclp[iclp] = x2; yclp[iclp] = y2; iclp++;
- }
-
- /* Boundary crossing condition -- going out. */
- crossed_xmin1 = ( x2 == xmin ); crossed_xmax1 = ( x2 == xmax );
- crossed_ymin1 = ( y2 == ymin ); crossed_ymax1 = ( y2 == ymax );
- }
- }
-
-/* 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 )
- {
- xclp[0] = xmin; yclp[0] = ymin;
- xclp[1] = xmax; yclp[1] = ymin;
- xclp[2] = xmax; yclp[2] = ymax;
- xclp[3] = xmin; yclp[3] = ymax;
- xclp[4] = xmin; yclp[4] = ymin;
- ( *draw )( xclp, yclp, 5 );
-
- if ( xclp != _xclp )
- {
- free( xclp );
- free( yclp );
- }
-
-
- return;
- }
- }
-
-/* Now handle cases where fill polygon intersects two sides of the box */
-
- if ( iclp >= 2 )
- {
- int debug = 0;
- int dir = circulation( x, y, npts );
- if ( debug )
- {
- if (( xclp[0] == xmin && xclp[iclp - 1] == xmax ) ||
- ( xclp[0] == xmax && xclp[iclp - 1] == xmin ) ||
- ( yclp[0] == ymin && yclp[iclp - 1] == ymax ) ||
- ( yclp[0] == ymax && yclp[iclp - 1] == ymin ) ||
- ( xclp[0] == xmin && yclp[iclp - 1] == ymin ) ||
- ( yclp[0] == ymin && xclp[iclp - 1] == xmin ) ||
- ( xclp[0] == xmax && yclp[iclp - 1] == ymin ) ||
- ( yclp[0] == ymin && xclp[iclp - 1] == xmax ) ||
- ( xclp[0] == xmax && yclp[iclp - 1] == ymax ) ||
- ( yclp[0] == ymax && xclp[iclp - 1] == xmax ) ||
- ( xclp[0] == xmin && yclp[iclp - 1] == ymax ) ||
- ( yclp[0] == ymax && xclp[iclp - 1] == xmin ))
- {
- printf( "dir=%d, clipped points:\n", dir );
- for ( i = 0; i < iclp; i++ )
- printf( " x[%d]=%d y[%d]=%d", i, xclp[i], i, yclp[i] );
- printf( "\n" );
- printf( "pre-clipped points:\n" );
- for ( i = 0; i < npts; i++ )
- printf( " x[%d]=%d y[%d]=%d", i, x[i], i, y[i] );
- printf( "\n" );
- }
- }
-
- /* The cases where the fill region is divided 2/2 */
- /* Divided horizontally */
- if ( xclp[0] == xmin && xclp[iclp - 1] == xmax )
- {
- if ( dir > 0 )
- {
- xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
- xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
- }
- else
- {
- xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
- xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
- }
- }
- else if ( xclp[0] == xmax && xclp[iclp - 1] == xmin )
- {
- if ( dir > 0 )
- {
- xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
- xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
- }
- else
- {
- xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
- xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
- }
- }
-
- /* Divided vertically */
- else if ( yclp[0] == ymin && yclp[iclp - 1] == ymax )
- {
- if ( dir > 0 )
- {
- xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
- xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
- }
- else
- {
- xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
- xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
- }
- }
- else if ( yclp[0] == ymax && yclp[iclp - 1] == ymin )
- {
- if ( dir > 0 )
- {
- xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
- xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
- }
- else
- {
- xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
- xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
- }
- }
-
- /* The cases where the fill region is divided 3/1 --
- * LL LR UR UL
- +-----+ +-----+ +-----+ +-----+
- | | | | | \| |/ |
- | | | | | | | |
- |\ | | /| | | | |
- +-----+ +-----+ +-----+ +-----+
- *
- * Note when we go the long way around, if the direction is reversed the
- * three vertices must be visited in the opposite order.
- */
- /* LL, short way around */
- else if (( xclp[0] == xmin && yclp[iclp - 1] == ymin && dir < 0 ) ||
- ( yclp[0] == ymin && xclp[iclp - 1] == xmin && dir > 0 ))
- {
- xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
- }
- /* LL, long way around, counterclockwise */
- else if (( xclp[0] == xmin && yclp[iclp - 1] == ymin && dir > 0 ))
- {
- xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
- xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
- xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
- }
- /* LL, long way around, clockwise */
- else if (( yclp[0] == ymin && xclp[iclp - 1] == xmin && dir < 0 ))
- {
- xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
- xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
- xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
- }
- /* LR, short way around */
- else if (( xclp[0] == xmax && yclp[iclp - 1] == ymin && dir > 0 ) ||
- ( yclp[0] == ymin && xclp[iclp - 1] == xmax && dir < 0 ))
- {
- xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
- }
- /* LR, long way around, counterclockwise */
- else if ( yclp[0] == ymin && xclp[iclp - 1] == xmax && dir > 0 )
- {
- xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
- xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
- xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
- }
- /* LR, long way around, clockwise */
- else if ( xclp[0] == xmax && yclp[iclp - 1] == ymin && dir < 0 )
- {
- xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
- xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
- xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
- }
- /* UR, short way around */
- else if (( xclp[0] == xmax && yclp[iclp - 1] == ymax && dir < 0 ) ||
- ( yclp[0] == ymax && xclp[iclp - 1] == xmax && dir > 0 ))
- {
- xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
- }
- /* UR, long way around, counterclockwise */
- else if ( xclp[0] == xmax && yclp[iclp - 1] == ymax && dir > 0 )
- {
- xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
- xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
- xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
- }
- /* UR, long way around, clockwise */
- else if ( yclp[0] == ymax && xclp[iclp - 1] == xmax && dir < 0 )
- {
- xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
- xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
- xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
- }
- /* UL, short way around */
- else if (( xclp[0] == xmin && yclp[iclp - 1] == ymax && dir > 0 ) ||
- ( yclp[0] == ymax && xclp[iclp - 1] == xmin && dir < 0 ))
- {
- xclp[iclp] = xmin; yclp[iclp] = ymax; iclp++;
- }
- /* UL, long way around, counterclockwise */
- else if ( yclp[0] == ymax && xclp[iclp - 1] == xmin && dir > 0 )
- {
- xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
- xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
- xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
- }
- /* UL, long way around, clockwise */
- else if ( xclp[0] == xmin && yclp[iclp - 1] == ymax && dir < 0 )
- {
- xclp[iclp] = xmax; yclp[iclp] = ymax; iclp++;
- xclp[iclp] = xmax; yclp[iclp] = ymin; iclp++;
- xclp[iclp] = xmin; yclp[iclp] = ymin; iclp++;
- }
- }
-
-/* 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 ( crossed_left + crossed_right + crossed_down + crossed_up == 1 &&
- inside_lb + inside_rb + inside_lu + inside_ru == 4 )
- {
- int dir = circulation( x, y, npts );
- PLINT xlim[4], ylim[4];
- int insert;
- int incr;
-
- xlim[0] = xmin; ylim[0] = ymin;
- xlim[1] = xmax; ylim[1] = ymin;
- xlim[2] = xmax; ylim[2] = ymax;
- xlim[3] = xmin; ylim[3] = ymax;
- if ( dir > 0 )
- {
- incr = 1;
- insert = 0 * crossed_left + 1 * crossed_down + 2 * crossed_right +
- 3 * crossed_up;
- }
- else
- {
- incr = -1;
- insert = 3 * crossed_left + 2 * crossed_up + 1 * crossed_right +
- 0 * crossed_down;
- }
- for ( i = 0; i < 4; i++ )
- {
- xclp[iclp] = xlim[insert];
- yclp[iclp] = ylim[insert];
- iclp++;
- insert += incr;
- if ( insert > 3 ) insert = 0;
- if ( insert < 0 ) insert = 3;
- }
- }
-
-/* Draw the sucker */
- if ( iclp >= 3 )
- ( *draw )( xclp, yclp, iclp );
-
- if ( xclp != _xclp )
- {
- free( xclp );
- free( yclp );
- }
-}
-
-/*----------------------------------------------------------------------*\
- * int clipline()
- *
* Get clipped endpoints
\*----------------------------------------------------------------------*/
-static int
-clipline( PLINT *p_x1, PLINT *p_y1, PLINT *p_x2, PLINT *p_y2,
+int
+plP_clipline( PLINT *p_x1, PLINT *p_y1, PLINT *p_x2, PLINT *p_y2,
PLINT xmin, PLINT xmax, PLINT ymin, PLINT ymax )
{
PLINT t, dx, dy, flipx, flipy;
@@ -1430,141 +914,3 @@
lasty = ytmp;
}
}
-
-/*----------------------------------------------------------------------*\
- * int pointinpolygon()
- *
- * PLINT wrapper for plP_pointinpolygon.
- \*----------------------------------------------------------------------*/
-
-static int
-pointinpolygon( PLINT n, PLINT *x, PLINT *y, PLINT xp, PLINT yp )
-{
- int i, return_value;
- PLFLT *xflt, *yflt;
- if (( xflt = (PLFLT *) malloc( n * sizeof ( PLFLT ))) == NULL )
- {
- plexit( "pointinpolygon: Insufficient memory" );
- }
- if (( yflt = (PLFLT *) malloc( n * sizeof ( PLFLT ))) == NULL )
- {
- plexit( "pointinpolygon: Insufficient memory" );
- }
- for ( i = 0; i < n; i++ )
- {
- xflt[i] = (PLFLT) x[i];
- yflt[i] = (PLFLT) y[i];
- }
- return_value = plP_pointinpolygon( n, xflt, yflt, (PLFLT) xp, (PLFLT) yp );
- free( xflt );
- free( yflt );
- return return_value;
-}
-/*----------------------------------------------------------------------*\
- * int plP_pointinpolygon()
- *
- * Returns 1 if the point is inside the polygon, 0 otherwise
- * Notes:
- * Points on the polygon are considered to be outside.
- * This "Ray casting algorithm" has been described in
- * http://en.wikipedia.org/wiki/Point_in_polygon.
- * Logic still needs to be inserted to take care of the "ray passes
- * through vertex" problem in a numerically robust way.
- \*----------------------------------------------------------------------*/
-
-int
-plP_pointinpolygon( PLINT n, PLFLT *x, PLFLT *y, PLFLT xp, PLFLT yp )
-{
- 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;
-
- count_crossings = 0;
-
-
- /* Determine a point outside the polygon */
-
- xmax = x[0];
- xout = x[0];
- yout = y[0];
- for ( i = 0; i < n; i++ )
- {
- if ( xout > x[i] )
- {
- xout = x[i];
- }
- if ( xmax < x[i] )
- {
- xmax = x[i];
- }
- }
- xout = xout - ( xmax - xout );
-
- /* Determine for each side whether the line segment between
- * our two points crosses the vertex */
-
- xvp = xp - xout;
- yvp = yp - yout;
-
- for ( i = 0; i < n; i++ )
- {
- x1 = x[i];
- y1 = y[i];
- if ( i < n - 1 )
- {
- x2 = x[i + 1];
- y2 = y[i + 1];
- }
- else
- {
- x2 = x[0];
- y2 = y[0];
- }
-
- /* Skip zero-length segments */
- if ( x1 == x2 && y1 == y2 )
- {
- continue;
- }
-
- /* Line through the two fixed points:
- * Are x1 and x2 on either side? */
- xv1 = x1 - xout;
- yv1 = y1 - yout;
- xv2 = x2 - xout;
- yv2 = y2 - yout;
- inprod1 = xv1 * yvp - yv1 * xvp; /* Well, with the normal vector */
- inprod2 = xv2 * yvp - yv2 * xvp;
- if ( inprod1 * inprod2 >= 0.0 )
- {
- /* No crossing possible! */
- continue;
- }
-
- /* Line through the two vertices:
- * Are xout and xp on either side? */
- xvv = x2 - x1;
- yvv = y2 - y1;
- xv1 = xp - x1;
- yv1 = yp - y1;
- xv2 = xout - x1;
- yv2 = yout - y1;
- inprod1 = xv1 * yvv - yv1 * xvv;
- inprod2 = xv2 * yvv - yv2 * xvv;
- if ( inprod1 * inprod2 >= 0.0 )
- {
- /* No crossing possible! */
- continue;
- }
-
- /* We do have a crossing */
- count_crossings++;
- }
-
- /* Return the result: an even number of crossings means the
- * point is outside the polygon */
-
- return ( count_crossings % 2 );
-}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
