/* Libart_LGPL - library of basic graphic primitives
* Copyright (C) 1998-2000 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.
*/
/* "Unsort" a sorted vector path into an ordinary vector path. */
#include "config.h"
#include "art_vpath_svp.h"
#include <stdio.h> /* for printf - debugging */
#include "art_misc.h"
#include "art_vpath.h"
#include "art_svp.h"
typedef struct _ArtVpathSVPEnd ArtVpathSVPEnd;
struct _ArtVpathSVPEnd {
gint seg_num;
gint which; /* 0 = top, 1 = bottom */
gdouble x, y;
};
#define EPSILON 1e-6
static gint
art_vpath_svp_point_compare (gdouble x1, gdouble y1, gdouble x2, gdouble y2)
{
if (y1 - EPSILON > y2) return 1;
if (y1 + EPSILON < y2) return -1;
if (x1 - EPSILON > x2) return 1;
if (x1 + EPSILON < x2) return -1;
return 0;
}
static gint
art_vpath_svp_compare (gconstpointer s1, gconstpointer s2)
{
const ArtVpathSVPEnd *e1 = s1;
const ArtVpathSVPEnd *e2 = s2;
return art_vpath_svp_point_compare (e1->x, e1->y, e2->x, e2->y);
}
/* Convert from sorted vector path representation into regular
vector path representation.
Status of this routine:
Basic correctness: Only works with closed paths.
Numerical stability: Not known to work when more than two segments
meet at a point.
Speed: Should be pretty good.
Precision: Does not degrade precision.
*/
/**
* art_vpath_from_svp: Convert from svp to vpath form.
* @svp: Original #ArtSVP.
*
* Converts the sorted vector path @svp into standard vpath form.
*
* Return value: the newly allocated vpath.
**/
ArtVpath *
art_vpath_from_svp (const ArtSVP *svp)
{
gint n_segs = svp->n_segs;
ArtVpathSVPEnd *ends;
ArtVpath *new;
gint *visited;
gint n_new, n_new_max;
gint i, k;
gint j = 0; /* Quiet compiler */
gint seg_num;
gint first;
gdouble last_x, last_y;
gint n_points;
gint pt_num;
last_x = 0; /* to eliminate "uninitialized" warning */
last_y = 0;
ends = art_new (ArtVpathSVPEnd, n_segs * 2);
for (i = 0; i < svp->n_segs; i++)
{
gint lastpt;
ends[i * 2].seg_num = i;
ends[i * 2].which = 0;
ends[i * 2].x = svp->segs[i].points[0].x;
ends[i * 2].y = svp->segs[i].points[0].y;
lastpt = svp->segs[i].n_points - 1;
ends[i * 2 + 1].seg_num = i;
ends[i * 2 + 1].which = 1;
ends[i * 2 + 1].x = svp->segs[i].points[lastpt].x;
ends[i * 2 + 1].y = svp->segs[i].points[lastpt].y;
}
qsort (ends, n_segs * 2, sizeof (ArtVpathSVPEnd), art_vpath_svp_compare);
n_new = 0;
n_new_max = 16; /* I suppose we _could_ estimate this from traversing
the svp, so we don't have to reallocate */
new = art_new (ArtVpath, n_new_max);
visited = art_new (int, n_segs);
for (i = 0; i < n_segs; i++)
visited[i] = 0;
first = 1;
for (i = 0; i < n_segs; i++)
{
if (!first)
{
/* search for the continuation of the existing subpath */
/* This could be a binary search (which is why we sorted, above) */
for (j = 0; j < n_segs * 2; j++)
{
if (!visited[ends[j].seg_num] &&
art_vpath_svp_point_compare (last_x, last_y,
ends[j].x, ends[j].y) == 0)
break;
}
if (j == n_segs * 2)
first = 1;
}
if (first)
{
/* start a new subpath */
for (j = 0; j < n_segs * 2; j++)
if (!visited[ends[j].seg_num])
break;
}
if (j == n_segs * 2)
{
printf ("failure\n");
}
seg_num = ends[j].seg_num;
n_points = svp->segs[seg_num].n_points;
for (k = 0; k < n_points; k++)
{
pt_num = svp->segs[seg_num].dir ? k : n_points - (1 + k);
if (k == 0)
{
if (first)
{
art_vpath_add_point (&new, &n_new, &n_new_max,
ART_MOVETO,
svp->segs[seg_num].points[pt_num].x,
svp->segs[seg_num].points[pt_num].y);
}
}
else
{
art_vpath_add_point (&new, &n_new, &n_new_max,
ART_LINETO,
svp->segs[seg_num].points[pt_num].x,
svp->segs[seg_num].points[pt_num].y);
if (k == n_points - 1)
{
last_x = svp->segs[seg_num].points[pt_num].x;
last_y = svp->segs[seg_num].points[pt_num].y;
/* to make more robust, check for meeting first_[xy],
set first if so */
}
}
first = 0;
}
visited[seg_num] = 1;
}
art_vpath_add_point (&new, &n_new, &n_new_max,
ART_END, 0, 0);
art_free (visited);
art_free (ends);
return new;
}
