/* 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.
*/
/* Vector path set operations, over sorted vpaths. */
#include "config.h"
#include "art_svp_ops.h"
#include "art_misc.h"
#include "art_svp.h"
#include "art_vpath.h"
#include "art_svp_vpath.h"
#include "art_svp.h"
#ifdef ART_USE_NEW_INTERSECTOR
#include "art_svp_intersect.h"
#else
#include "art_svp_wind.h"
#endif
#include "art_vpath_svp.h"
/* Merge the segments of the two svp's. The resulting svp will share
segments with args passed in, so be super-careful with the
allocation. */
/**
* art_svp_merge: Merge the segments of two svp's.
* @svp1: One svp to merge.
* @svp2: The other svp to merge.
*
* Merges the segments of two SVP's into a new one. The resulting
* #ArtSVP data structure will share the segments of the argument
* svp's, so it is probably a good idea to free it shallowly,
* especially if the arguments will be freed with art_svp_free().
*
* Return value: The merged #ArtSVP.
**/
static ArtSVP *
art_svp_merge (const ArtSVP *svp1, const ArtSVP *svp2)
{
ArtSVP *svp_new;
gint ix;
gint ix1, ix2;
svp_new = (ArtSVP *)art_alloc (sizeof (ArtSVP) +
(svp1->n_segs + svp2->n_segs - 1) *
sizeof (ArtSVPSeg));
ix1 = 0;
ix2 = 0;
for (ix = 0; ix < svp1->n_segs + svp2->n_segs; ix++)
{
if (ix1 < svp1->n_segs &&
(ix2 == svp2->n_segs ||
art_svp_seg_compare (&svp1->segs[ix1], &svp2->segs[ix2]) < 1))
svp_new->segs[ix] = svp1->segs[ix1++];
else
svp_new->segs[ix] = svp2->segs[ix2++];
}
svp_new->n_segs = ix;
return svp_new;
}
#ifndef ART_USE_NEW_INTERSECTOR
static ArtSVP *
art_svp_merge_perturbed (const ArtSVP *svp1, const ArtSVP *svp2)
{
ArtVpath *vpath1, *vpath2;
ArtVpath *vpath1_p, *vpath2_p;
ArtSVP *svp1_p, *svp2_p;
ArtSVP *svp_new;
vpath1 = art_vpath_from_svp (svp1);
vpath1_p = art_vpath_perturb (vpath1);
art_free (vpath1);
svp1_p = art_svp_from_vpath (vpath1_p);
art_free (vpath1_p);
vpath2 = art_vpath_from_svp (svp2);
vpath2_p = art_vpath_perturb (vpath2);
art_free (vpath2);
svp2_p = art_svp_from_vpath (vpath2_p);
art_free (vpath2_p);
svp_new = art_svp_merge (svp1_p, svp2_p);
art_free (svp1_p);
art_free (svp2_p);
return svp_new;
}
#endif
/* Compute the intersection of two vector paths.
Status of this routine:
Basic correctness: Seems to work.
Numerical stability: We cheat (adding random perturbation). Thus,
it seems very likely that no numerical stability problems will be
seen in practice.
Speed: Would be better if we didn't go to unsorted vector path
and back to add the perturbation.
Precision: The perturbation fuzzes the coordinates slightly. In
cases of butting segments, razor thin long isolated segments may
appear.
*/
/**
* art_svp_intersect: Compute the intersection of two sorted vector paths.
* @svp1: One sorted vector path.
* @svp2: The other sorted vector path.
*
* Computes the intersection of the two argument svp's. Given two
* svp's with winding numbers of 0 and 1 everywhere, the resulting
* winding number will be 1 where both of the argument svp's has a
* winding number 1, 0 otherwise. The result is newly allocated.
*
* Currently, this routine has accuracy problems pending the
* implementation of the new intersector.
*
* Return value: The intersection of @svp1 and @svp2.
**/
ArtSVP *
art_svp_intersect (const ArtSVP *svp1, const ArtSVP *svp2)
{
#ifdef ART_USE_NEW_INTERSECTOR
ArtSVP *svp3, *svp_new;
ArtSvpWriter *swr;
svp3 = art_svp_merge (svp1, svp2);
swr = art_svp_writer_rewind_new (ART_WIND_RULE_INTERSECT);
art_svp_intersector (svp3, swr);
svp_new = art_svp_writer_rewind_reap (swr);
art_free (svp3); /* shallow free because svp3 contains shared segments */
return svp_new;
#else
ArtSVP *svp3, *svp4, *svp_new;
svp3 = art_svp_merge_perturbed (svp1, svp2);
svp4 = art_svp_uncross (svp3);
art_svp_free (svp3);
svp_new = art_svp_rewind_uncrossed (svp4, ART_WIND_RULE_INTERSECT);
art_svp_free (svp4);
return svp_new;
#endif
}
