plotutils-graph-patches-lloda/libxmi/mi_fplycon.c

/* This file is part of the GNU libxmi package.  

   Copyright (C) 1985, 1986, 1987, 1988, 1989, X Consortium.  For an
   associated permission notice, see the accompanying file README-X.
   
   GNU enhancements Copyright (C) 1998, 1999, 2000, 2005, Free Software
   Foundation, Inc.

   The GNU libxmi package is free software.  You may redistribute it
   and/or modify it under the terms of the GNU General Public License as
   published by the Free Software foundation; either version 2, or (at your
   option) any later version.

   The GNU libxmi package is distributed in the hope that it will be
   useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License along
   with the GNU plotutils package; see the file COPYING.  If not, write to
   the Free Software Foundation, Inc., 51 Franklin St., Fifth Floor,
   Boston, MA 02110-1301, USA. */

#include "sys-defines.h"
#include "extern.h"

#include "xmi.h"
#include "mi_spans.h"
#include "mi_api.h"
#include "mi_fply.h"

/* forward references */
static int GetFPolyYBounds (const SppPoint *pts, int n, double yFtrans, int *by, int *ty);

/*
 * Written by Todd Newman; April 1987.
 * Hacked by Robert S. Maier, 1998-1999.
 *
 * Fill a convex polygon, with SPP (subpixel placement) of vertices.  If
 * the given polygon is not convex, then the result is undefined.  All
 * painting goes through the low-level MI_PAINT_SPANS() macro.
 *
 * In libxmi, this is used to draw polygonal line caps and line joins for
 * poly-arcs.  See mi_arc.c.
 *
 * The algorithm is to order the edges from smallest y to largest y, by
 * partitioning the array into a left edge list and a right edge list.  The
 * algorithm used to traverse each edge is the digital differencing
 * analyzer line algorithm, with y as the major axis. There's some funny
 * linear interpolation involved because of the subpixel postioning. */

/* ARGS: count = # points, ptsIn = points, 
   	 xTrans,yTrans = translation for each point, 
	 xFtrans,yFtrans = translation before conversion, which provides a
	 		   mechanism to match rounding errors with any
			   shape that meets the polygon exactly. */
void
miFillSppPoly (miPaintedSet *paintedSet, miPixel pixel, int count, const SppPoint *ptsIn, int xTrans, int yTrans, double xFtrans, double yFtrans)
{
  double	xl = 0.0,	/* x vals of left and right edges */
  		xr = 0.0,
  		ml = 0.0,	/* left edge slope */
		mr = 0.0,	/* right edge slope */
		dy,		/* delta y */
		i;		/* loop counter */
  int		y,		/* current scanline */
		j,
		imin,		/* index of vertex with smallest y */
		ymin,		/* y-extents of polygon */
		ymax;
  int           left, right,	/* indices to first endpoints */
		nextleft,
		nextright;	/* indices to second endpoints */
  int		*Marked;	/* set if this vertex has been used */
  unsigned int	*width,
		*FirstWidth;	/* output buffer */
  miPoint	*ptsOut,
		*FirstPoint;	/* output buffer */

  imin = GetFPolyYBounds (ptsIn, count, yFtrans, &ymin, &ymax);

  y = ymax - ymin + 1;
  if ((count < 3) || (y <= 0))
    return;
  ptsOut = FirstPoint = (miPoint *)mi_xmalloc(sizeof(miPoint) * y);
  width = FirstWidth = (unsigned int *)mi_xmalloc(sizeof(unsigned int) * y);
  Marked = (int *) mi_xmalloc(sizeof(int) * count);

  for (j = 0; j < count; j++)
    Marked[j] = 0;
  nextleft = nextright = imin;
  Marked[imin] = -1;
  y = ICEIL(ptsIn[nextleft].y + yFtrans);

  /*
   *  loop through all edges of the polygon
   */
  do
    {
      /* add a left edge if we need to */
      if ((y > (ptsIn[nextleft].y + yFtrans) ||
	   ISEQUAL(y, ptsIn[nextleft].y + yFtrans)) 
	  && Marked[nextleft] != 1)
	{
	  Marked[nextleft]++;
	  left = nextleft++;

	  /* find the next edge, considering the end conditions */
	  if (nextleft >= count)
	    nextleft = 0;

	  /* now compute the starting point and slope */
	  dy = ptsIn[nextleft].y - ptsIn[left].y;
	  if (dy != 0.0)
	    { 
	      ml = (ptsIn[nextleft].x - ptsIn[left].x) / dy;
	      dy = y - (ptsIn[left].y + yFtrans);
	      xl = (ptsIn[left].x + xFtrans) + ml * DMAX(dy, 0);
	    }
        }

      /* add a right edge if we need to */
      if ((y > ptsIn[nextright].y + yFtrans) 
	  ||
	  (ISEQUAL(y, ptsIn[nextright].y + yFtrans)
	   && Marked[nextright] != 1))
	{
	  Marked[nextright]++;
	  right = nextright--;
	    
	  /* find the next edge, considering the end conditions */
	  if (nextright < 0)
	    nextright = count - 1;
	    
	  /* now compute the starting point and slope */
	  dy = ptsIn[nextright].y - ptsIn[right].y;
	  if (dy != 0.0) 
	    { 
	      mr = (ptsIn[nextright].x - ptsIn[right].x) / dy;
	      dy = y - (ptsIn[right].y + yFtrans); 
	      xr = (ptsIn[right].x + xFtrans) + mr * DMAX(dy, 0);
	    }
	}
	
      /*
       *  generate scans to fill while we still have
       *  a right edge as well as a left edge.
       */
      i = (DMIN(ptsIn[nextleft].y, ptsIn[nextright].y) + yFtrans) - y;

      if (i < EPSILON)
	{
	  if(Marked[nextleft] && Marked[nextright])
	    {
	      /* Arrgh, we're trapped! (no more points) 
	       * Out, we've got to get out of here before this decadence saps
	       * our will completely! */
	      break;
	    }
	  continue;
	}
      else
	{
	  j = (int) i;
	  if (!j)
	    j++;
	}
      while (j > 0) 
        {
	  int cxl, cxr;

	  ptsOut->y = (y) + yTrans;

	  cxl = ICEIL(xl);
	  cxr = ICEIL(xr);
	  /* reverse the edges if necessary */
	  if (xl < xr) 
            {
	      *(width++) = (unsigned int)(cxr - cxl);
	      (ptsOut++)->x = cxl + xTrans;
            }
	  else 
            {
	      *(width++) = (unsigned int)(cxl - cxr);
	      (ptsOut++)->x = cxr + xTrans;
            }
	  y++;

	  /* increment down the edges */
	  xl += ml;
	  xr += mr;
	  j--;
        }
    } while (y <= ymax);

  free (Marked);

  /* paint the spans (to miPaintedSet, or if NULL, to the canvas) */
  MI_PAINT_SPANS(paintedSet, pixel, ptsOut - FirstPoint, FirstPoint, FirstWidth)
}

/* Find the index of the point with the smallest y.  Also return the
   smallest and largest y. */
static int
GetFPolyYBounds (const SppPoint *pts, int n, double yFtrans, int *by, int *ty)
{
  const SppPoint *ptsStart = pts;
  const SppPoint *ptMin;
  double ymin, ymax;

  ptMin = pts;
  ymin = ymax = (pts++)->y;

  while (--n > 0) 
    {
      if (pts->y < ymin)
	{
	  ptMin = pts;
	  ymin = pts->y;
	}
      if(pts->y > ymax)
	ymax = pts->y;

      pts++;
    }

  *by = ICEIL(ymin + yFtrans);
  *ty = ICEIL(ymax + yFtrans - 1);
  return (ptMin - ptsStart);
}