lib/art/art_svp.c

   1 /* Libart_LGPL - library of basic graphic primitives
   2  * Copyright (C) 1998 Raph Levien
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 /* Basic constructors and operations for sorted vector paths */
  21
  22 #include "config.h"
  23 #include "art_svp.h"
  24
  25 #include "art_misc.h"
  26
  27 /* Add a new segment. The arguments can be zero and NULL if the caller
  28    would rather fill them in later.
  29
  30    We also realloc one auxiliary array of ints of size n_segs if
  31    desired.
  32 */
  33 /**
  34  * art_svp_add_segment: Add a segment to an #ArtSVP structure.
  35  * @p_vp: Pointer to where the #ArtSVP structure is stored.
  36  * @pn_segs_max: Pointer to the allocated size of *@p_vp.
  37  * @pn_points_max: Pointer to where auxiliary array is stored.
  38  * @n_points: Number of points for new segment.
  39  * @dir: Direction for new segment; 0 is up, 1 is down.
  40  * @points: Points for new segment.
  41  * @bbox: Bounding box for new segment.
  42  *
  43  * Adds a new segment to an ArtSVP structure. This routine reallocates
  44  * the structure if necessary, updating *@p_vp and *@pn_segs_max as
  45  * necessary.
  46  *
  47  * The new segment is simply added after all other segments. Thus,
  48  * this routine should be called in order consistent with the #ArtSVP
  49  * sorting rules.
  50  *
  51  * If the @bbox argument is given, it is simply stored in the new
  52  * segment. Otherwise (if it is NULL), the bounding box is computed
  53  * from the @points given.
  54  **/
  55 int
  56 art_svp_add_segment (ArtSVP **p_vp, int *pn_segs_max,
  57                      int **pn_points_max,
  58                      int n_points, int dir, ArtPoint *points,
  59                      ArtDRect *bbox)
  60 {
  61   int seg_num;
  62   ArtSVP *svp;
  63   ArtSVPSeg *seg;
  64
  65   svp = *p_vp;
  66   seg_num = svp->n_segs++;
  67   if (*pn_segs_max == seg_num)
  68     {
  69       *pn_segs_max <<= 1;
  70       svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
  71                                    (*pn_segs_max - 1) * sizeof(ArtSVPSeg));
  72       *p_vp = svp;
  73       if (pn_points_max != NULL)
  74         *pn_points_max = art_renew (*pn_points_max, int, *pn_segs_max);
  75     }
  76   seg = &svp->segs[seg_num];
  77   seg->n_points = n_points;
  78   seg->dir = dir;
  79   seg->points = points;
  80   if (bbox)
  81     seg->bbox = *bbox;
  82   else if (points)
  83     {
  84       double x_min, x_max;
  85       int i;
  86
  87       x_min = x_max = points[0].x;
  88       for (i = 1; i < n_points; i++)
  89         {
  90           if (x_min > points[i].x)
  91             x_min = points[i].x;
  92           if (x_max < points[i].x)
  93             x_max = points[i].x;
  94         }
  95       seg->bbox.x0 = x_min;
  96       seg->bbox.y0 = points[0].y;
  97
  98       seg->bbox.x1 = x_max;
  99       seg->bbox.y1 = points[n_points - 1].y;
 100     }
 101   return seg_num;
 102 }
 103
 104
 105 /**
 106  * art_svp_free: Free an #ArtSVP structure.
 107  * @svp: #ArtSVP to free.
 108  *
 109  * Frees an #ArtSVP structure and all the segments in it.
 110  **/
 111 void
 112 art_svp_free (ArtSVP *svp)
 113 {
 114   int n_segs = svp->n_segs;
 115   int i;
 116
 117   for (i = 0; i < n_segs; i++)
 118     art_free (svp->segs[i].points);
 119   art_free (svp);
 120 }
 121
 122 #ifdef ART_USE_NEW_INTERSECTOR
 123 #define EPSILON 0
 124 #else
 125 #define EPSILON 1e-6
 126 #endif
 127
 128 /**
 129  * art_svp_seg_compare: Compare two segments of an svp.
 130  * @seg1: First segment to compare.
 131  * @seg2: Second segment to compare.
 132  *
 133  * Compares two segments of an svp. Return 1 if @seg2 is below or to the
 134  * right of @seg1, -1 otherwise.
 135  **/
 136 int
 137 art_svp_seg_compare (const void *s1, const void *s2)
 138 {
 139   const ArtSVPSeg *seg1 = (ArtSVPSeg *)s1;
 140   const ArtSVPSeg *seg2 = (ArtSVPSeg *)s2;
 141
 142   if (seg1->points[0].y - EPSILON > seg2->points[0].y) return 1;
 143   else if (seg1->points[0].y + EPSILON < seg2->points[0].y) return -1;
 144   else if (seg1->points[0].x - EPSILON > seg2->points[0].x) return 1;
 145   else if (seg1->points[0].x + EPSILON < seg2->points[0].x) return -1;
 146   else if ((seg1->points[1].x - seg1->points[0].x) *
 147            (seg2->points[1].y - seg2->points[0].y) -
 148            (seg1->points[1].y - seg1->points[0].y) *
 149            (seg2->points[1].x - seg2->points[0].x) > 0) return 1;
 150   else return -1;
 151 }
 152