art_svp.c 4.31 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
/* Libart_LGPL - library of basic graphic primitives
 * Copyright (C) 1998 Raph Levien
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library 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
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

/* Basic constructors and operations for sorted vector paths */

Darin Adler's avatar
Darin Adler committed
22
#include "config.h"
23 24
#include "art_svp.h"

Darin Adler's avatar
Darin Adler committed
25 26
#include "art_misc.h"

27 28 29 30 31 32
/* Add a new segment. The arguments can be zero and NULL if the caller
   would rather fill them in later.

   We also realloc one auxiliary array of ints of size n_segs if
   desired.
*/
Raph Levien's avatar
Raph Levien committed
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
/**
 * art_svp_add_segment: Add a segment to an #ArtSVP structure.
 * @p_vp: Pointer to where the #ArtSVP structure is stored.
 * @pn_segs_max: Pointer to the allocated size of *@p_vp.
 * @pn_points_max: Pointer to where auxiliary array is stored.
 * @n_points: Number of points for new segment.
 * @dir: Direction for new segment; 0 is up, 1 is down.
 * @points: Points for new segment.
 * @bbox: Bounding box for new segment.
 *
 * Adds a new segment to an ArtSVP structure. This routine reallocates
 * the structure if necessary, updating *@p_vp and *@pn_segs_max as
 * necessary.
 *
 * The new segment is simply added after all other segments. Thus,
 * this routine should be called in order consistent with the #ArtSVP
 * sorting rules.
 *
 * If the @bbox argument is given, it is simply stored in the new
 * segment. Otherwise (if it is NULL), the bounding box is computed
 * from the @points given.
 **/
55 56 57
int
art_svp_add_segment (ArtSVP **p_vp, int *pn_segs_max,
		     int **pn_points_max,
58 59
		     int n_points, int dir, ArtPoint *points,
		     ArtDRect *bbox)
60 61
{
  int seg_num;
62 63
  ArtSVP *svp;
  ArtSVPSeg *seg;
64

65 66
  svp = *p_vp;
  seg_num = svp->n_segs++;
67 68 69
  if (*pn_segs_max == seg_num)
    {
      *pn_segs_max <<= 1;
70 71 72
      svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
				   (*pn_segs_max - 1) * sizeof(ArtSVPSeg));
      *p_vp = svp;
73 74 75
      if (pn_points_max != NULL)
	*pn_points_max = art_renew (*pn_points_max, int, *pn_segs_max);
    }
76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
  seg = &svp->segs[seg_num];
  seg->n_points = n_points;
  seg->dir = dir;
  seg->points = points;
  if (bbox)
    seg->bbox = *bbox;
  else if (points)
    {
      double x_min, x_max;
      int i;

      x_min = x_max = points[0].x;
      for (i = 1; i < n_points; i++)
	{
	  if (x_min > points[i].x)
	    x_min = points[i].x;
	  if (x_max < points[i].x)
	    x_max = points[i].x;
	}
      seg->bbox.x0 = x_min;
      seg->bbox.y0 = points[0].y;
      
      seg->bbox.x1 = x_max;
      seg->bbox.y1 = points[n_points - 1].y;
    }
101 102 103
  return seg_num;
}

Raph Levien's avatar
Raph Levien committed
104 105 106 107 108 109 110

/**
 * art_svp_free: Free an #ArtSVP structure.
 * @svp: #ArtSVP to free.
 * 
 * Frees an #ArtSVP structure and all the segments in it.
 **/
111 112 113 114 115 116 117 118 119 120 121
void
art_svp_free (ArtSVP *svp)
{
  int n_segs = svp->n_segs;
  int i;

  for (i = 0; i < n_segs; i++)
    art_free (svp->segs[i].points);
  art_free (svp);
}

122 123 124
#ifdef ART_USE_NEW_INTERSECTOR
#define EPSILON 0
#else
125
#define EPSILON 1e-6
126
#endif
127

Raph Levien's avatar
Raph Levien committed
128 129 130 131 132 133
/**
 * art_svp_seg_compare: Compare two segments of an svp.
 * @seg1: First segment to compare.
 * @seg2: Second segment to compare.
 * 
 * Compares two segments of an svp. Return 1 if @seg2 is below or to the
134
 * right of @seg1, -1 otherwise.
Raph Levien's avatar
Raph Levien committed
135
 **/
136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152
int
art_svp_seg_compare (const void *s1, const void *s2)
{
  const ArtSVPSeg *seg1 = s1;
  const ArtSVPSeg *seg2 = s2;

  if (seg1->points[0].y - EPSILON > seg2->points[0].y) return 1;
  else if (seg1->points[0].y + EPSILON < seg2->points[0].y) return -1;
  else if (seg1->points[0].x - EPSILON > seg2->points[0].x) return 1;
  else if (seg1->points[0].x + EPSILON < seg2->points[0].x) return -1;
  else if ((seg1->points[1].x - seg1->points[0].x) *
	   (seg2->points[1].y - seg2->points[0].y) -
	   (seg1->points[1].y - seg1->points[0].y) *
	   (seg2->points[1].x - seg2->points[0].x) > 0) return 1;
  else return -1;
}