summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorEduard Braun <eduard.braun2@gmx.de>2018-10-01 23:21:40 +0000
committerEduard Braun <eduard.braun2@gmx.de>2018-10-01 23:21:40 +0000
commit33cd18d64ea3a67b90aa87b225b0d18447f01138 (patch)
tree7e404a57fa4b7a8b10825c2f26741c90f89f7c5c
parentAvoid duplicating defines in config.h and on command line (diff)
downloadinkscape-33cd18d64ea3a67b90aa87b225b0d18447f01138.tar.gz
inkscape-33cd18d64ea3a67b90aa87b225b0d18447f01138.zip
2geom: update to c709d6b6780098d3e53363d925f7aee3c2640478
Update README and remove obsolete files
-rw-r--r--src/2geom/!PLEASE DON'T MAKE CHANGES IN THESE FILES.README7
-rw-r--r--src/2geom/CMakeLists.txt3
-rw-r--r--src/2geom/bezier-clipping.cpp4
-rw-r--r--src/2geom/bezier-curve.cpp2
-rw-r--r--src/2geom/circulator.h150
-rw-r--r--src/2geom/concepts.h2
-rw-r--r--src/2geom/conic_section_clipper_impl.cpp2
-rw-r--r--src/2geom/conic_section_clipper_impl.h2
-rw-r--r--src/2geom/conicsec.cpp4
-rw-r--r--src/2geom/conicsec.h2
-rw-r--r--src/2geom/convex-hull.h2
-rw-r--r--src/2geom/curve.h2
-rw-r--r--src/2geom/elliptical-arc-from-sbasis.cpp6
-rw-r--r--src/2geom/elliptical-arc.h2
-rw-r--r--src/2geom/generic-rect.h8
-rw-r--r--src/2geom/intersection-graph.cpp8
-rw-r--r--src/2geom/line.h4
-rw-r--r--src/2geom/math-utils.h2
-rw-r--r--src/2geom/path.cpp2
-rw-r--r--src/2geom/path.h2
-rw-r--r--src/2geom/piecewise.h4
-rw-r--r--src/2geom/sbasis-geometric.cpp7
-rw-r--r--src/2geom/sbasis-roots.cpp14
-rw-r--r--src/2geom/solve-bezier.cpp2
-rwxr-xr-xsrc/2geom/sync.sh31
-rw-r--r--src/2geom/toposweep.cpp666
-rw-r--r--src/2geom/toposweep.h222
-rw-r--r--src/2geom/transforms.h2
28 files changed, 47 insertions, 1117 deletions
diff --git a/src/2geom/!PLEASE DON'T MAKE CHANGES IN THESE FILES.README b/src/2geom/!PLEASE DON'T MAKE CHANGES IN THESE FILES.README
index e94a549f6..e0919de21 100644
--- a/src/2geom/!PLEASE DON'T MAKE CHANGES IN THESE FILES.README
+++ b/src/2geom/!PLEASE DON'T MAKE CHANGES IN THESE FILES.README
@@ -8,6 +8,7 @@ The command above will only update existing files. If you add new files
to 2Geom, you'll need to copy the new files manually. Same if you remove
some files. Note that the trailing slashes are required!
-2geom's BZR repo = lp:lib2geom
-http://lib2geom.sourceforge.net
-
+2Geom's git repository is hosted on GitHub
+ https://github.com/inkscape/lib2geom
+and mirrored on GitLab
+ https://gitlab.com/inkscape/lib2geom
diff --git a/src/2geom/CMakeLists.txt b/src/2geom/CMakeLists.txt
index d2c1ea50e..244f3ff62 100644
--- a/src/2geom/CMakeLists.txt
+++ b/src/2geom/CMakeLists.txt
@@ -49,7 +49,6 @@ set(2geom_SRC
svg-path-parser.cpp
svg-path-writer.cpp
sweep-bounds.cpp
- toposweep.cpp
transforms.cpp
utils.cpp
@@ -67,7 +66,6 @@ set(2geom_SRC
cairo-path-sink.h
choose.h
circle.h
- circulator.h
concepts.h
conic_section_clipper.h
conic_section_clipper_cr.h
@@ -118,7 +116,6 @@ set(2geom_SRC
svg-path-writer.h
sweep-bounds.h
sweeper.h
- toposweep.h
transforms.h
utils.h
diff --git a/src/2geom/bezier-clipping.cpp b/src/2geom/bezier-clipping.cpp
index 03a6dfecd..e7bbcc30e 100644
--- a/src/2geom/bezier-clipping.cpp
+++ b/src/2geom/bezier-clipping.cpp
@@ -729,7 +729,7 @@ const Interval H2_INTERVAL(nextafter(0.5, 1.0), 1.0);
* in case the clipping doesn't shrink the initial interval more than 20%,
* a subdivision step is performed.
* If during the computation both curves collapse to a single point
- * the routine exits indipendently by the precision reached in the computation
+ * the routine exits independently by the precision reached in the computation
* of the curve intervals.
*/
template <>
@@ -888,7 +888,7 @@ void iterate<intersection_point_tag> (std::vector<Interval>& domsA,
* in case the clipping doesn't shrink the initial interval more than 20%,
* a subdivision step is performed.
* If during the computation one of the two curve interval length becomes less
- * than MAX_PRECISION the routine exits indipendently by the precision reached
+ * than MAX_PRECISION the routine exits independently by the precision reached
* in the computation of the other curve interval.
*/
template <>
diff --git a/src/2geom/bezier-curve.cpp b/src/2geom/bezier-curve.cpp
index 866263047..73fafe4f3 100644
--- a/src/2geom/bezier-curve.cpp
+++ b/src/2geom/bezier-curve.cpp
@@ -79,7 +79,7 @@ namespace Geom
* @image html bezier-curve-evaluation.png "Evaluation of the Bezier curve"
*
* An important property of the Bezier curves is that their parameters (control points)
- * have an intutive geometric interpretation. Because of this, they are frequently used
+ * have an intuitive geometric interpretation. Because of this, they are frequently used
* in vector graphics editors.
*
* Every Bezier curve is contained in its control polygon (the convex polygon composed
diff --git a/src/2geom/circulator.h b/src/2geom/circulator.h
deleted file mode 100644
index 06e4d2c4e..000000000
--- a/src/2geom/circulator.h
+++ /dev/null
@@ -1,150 +0,0 @@
-/** @file
- * @brief Circular iterator adapter
- *//*
- * Copyright 2006 MenTaLguY <mental@rydia.net>
- *
- * This library is free software; you can redistribute it and/or
- * modify it either under the terms of the GNU Lesser General Public
- * License version 2.1 as published by the Free Software Foundation
- * (the "LGPL") or, at your option, under the terms of the Mozilla
- * Public License Version 1.1 (the "MPL"). If you do not alter this
- * notice, a recipient may use your version of this file under either
- * the MPL or the LGPL.
- *
- * You should have received a copy of the LGPL along with this library
- * in the file COPYING-LGPL-2.1; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
- * You should have received a copy of the MPL along with this library
- * in the file COPYING-MPL-1.1
- *
- * The contents of this file are subject to the Mozilla Public License
- * Version 1.1 (the "License"); you may not use this file except in
- * compliance with the License. You may obtain a copy of the License at
- * http://www.mozilla.org/MPL/
- *
- * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
- * OF ANY KIND, either express or implied. See the LGPL or the MPL for
- * the specific language governing rights and limitations.
- *
- */
-
-#ifndef LIB2GEOM_SEEN_CIRCULATOR_H
-#define LIB2GEOM_SEEN_CIRCULATOR_H
-
-#include <iterator>
-
-namespace Geom {
-
-/** @brief Circular iterator adapter
- * This iterator adapter will loop indefinitely over a set of values
- * from a random access container. */
-template <typename Iterator>
-class Circulator {
-public:
- typedef std::random_access_iterator_tag iterator_category;
- typedef typename std::iterator_traits<Iterator>::value_type value_type;
- typedef typename std::iterator_traits<Iterator>::difference_type difference_type;
- typedef typename std::iterator_traits<Iterator>::pointer pointer;
- typedef typename std::iterator_traits<Iterator>::reference reference;
-
- Circulator(Iterator const &first,
- Iterator const &last,
- Iterator const &pos)
- : _first(first), _last(last), _pos(pos)
- {
- match_random_access(iterator_category(first));
- }
-
- reference operator*() const {
- return *_pos;
- }
- pointer operator->() const {
- return &*_pos;
- }
-
- Circulator &operator++() {
- if ( _first == _last ) return *this;
- ++_pos;
- if ( _pos == _last ) _pos = _first;
- return *this;
- }
- Circulator operator++(int) {
- Circulator saved=*this;
- ++(*this);
- return saved;
- }
-
- Circulator &operator--() {
- if ( _pos == _first ) _pos = _last;
- --_pos;
- return *this;
- }
- Circulator operator--(int) {
- Circulator saved=*this;
- --(*this);
- return saved;
- }
-
- Circulator &operator+=(int n) {
- _pos = _offset(n);
- return *this;
- }
- Circulator operator+(int n) const {
- return Circulator(_first, _last, _offset(n));
- }
- Circulator &operator-=(int n) {
- _pos = _offset(-n);
- return *this;
- }
- Circulator operator-(int n) const {
- return Circulator(_first, _last, _offset(-n));
- }
-
- difference_type operator-(Circulator const &other) {
- return _pos - other._pos;
- }
-
- reference operator[](int n) const {
- return *_offset(n);
- }
-
-private:
- void match_random_access(iterator_category) {}
-
- Iterator _offset(int n) {
- difference_type range=( _last - _first );
- difference_type offset=( _pos - _first + n );
-
- if ( offset < 0 ) {
- // modulus not well-defined for negative numbers in C++
- offset += ( ( -offset / range ) + 1 ) * range;
- } else if ( offset >= range ) {
- offset %= range;
- }
- return _first + offset;
- }
-
- Iterator _first;
- Iterator _last;
- Iterator _pos;
-};
-
-}
-
-template <typename T>
-Geom::Circulator<T> operator+(int n, Geom::Circulator<T> const &c) {
- return c + n;
-}
-
-#endif // LIB2GEOM_SEEN_CIRCULATOR_H
-
-/*
- Local Variables:
- mode:c++
- c-file-style:"stroustrup"
- c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
- indent-tabs-mode:nil
- fill-column:99
- End:
-*/
-// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
diff --git a/src/2geom/concepts.h b/src/2geom/concepts.h
index c331f078b..de76d0f0b 100644
--- a/src/2geom/concepts.h
+++ b/src/2geom/concepts.h
@@ -139,7 +139,7 @@ template <typename T>
struct EqualityComparableConcept {
T a, b;
bool bool_;
- void constaints() {
+ void constraints() {
bool_ = (a == b);
bool_ = (a != b);
}
diff --git a/src/2geom/conic_section_clipper_impl.cpp b/src/2geom/conic_section_clipper_impl.cpp
index c57307974..23731afed 100644
--- a/src/2geom/conic_section_clipper_impl.cpp
+++ b/src/2geom/conic_section_clipper_impl.cpp
@@ -53,7 +53,7 @@ bool CLIPPER_CLASS::intersect (std::vector<Point> & crossing_points) const
bool no_crossing = true;
- // rigth edge
+ // right edge
cs.roots (rts, R.right(), X);
if (!rts.empty())
{
diff --git a/src/2geom/conic_section_clipper_impl.h b/src/2geom/conic_section_clipper_impl.h
index e38a6d416..2e8fd246c 100644
--- a/src/2geom/conic_section_clipper_impl.h
+++ b/src/2geom/conic_section_clipper_impl.h
@@ -324,7 +324,7 @@ void CLIPPER_CLASS::rsplit (std::list<Point> & points,
}
// they have to be called both to keep the number of points in the list
- // in the form 2k+1 where k are the sub-arcs the initial arc is splitted in.
+ // in the form 2k+1 where k are the sub-arcs the initial arc is split in.
rsplit (points, sp, ip, length);
rsplit (points, ip, fp, length);
}
diff --git a/src/2geom/conicsec.cpp b/src/2geom/conicsec.cpp
index 3e0a53816..1e821c38c 100644
--- a/src/2geom/conicsec.cpp
+++ b/src/2geom/conicsec.cpp
@@ -249,7 +249,7 @@ std::vector<Point> decompose_degenerate(xAx const & C1, xAx const & C2, xAx cons
(-A[1][0]*b[0] + A[0][0]*b[1]));
B0 *= ideterm;
Point n0, n1;
- // Are these just the eigenvectors of A[1][1]?
+ // Are these just the eigenvectors of A11?
if(xC0.c[0] == xC0.c[2]) {
double b = 0.5*xC0.c[1]/xC0.c[0];
double c = xC0.c[2]/xC0.c[0];
@@ -1246,7 +1246,7 @@ xAx xAx::rotate (double angle) const
/*
* Decompose a degenerate conic in two lines the conic section is made by.
- * Return true if the decomposition is successfull, else if it fails.
+ * Return true if the decomposition is successful, else if it fails.
*
* l1, l2: out parameters where the decomposed conic section is returned
*/
diff --git a/src/2geom/conicsec.h b/src/2geom/conicsec.h
index dbe564872..8b9b1f917 100644
--- a/src/2geom/conicsec.h
+++ b/src/2geom/conicsec.h
@@ -336,7 +336,7 @@ public:
/*
* Compute the centre of simmetry of the conic section when it exists,
- * else it return an unitialized boost::optional<Point> instance.
+ * else it return an uninitialized boost::optional<Point> instance.
*/
boost::optional<Point> centre() const
{
diff --git a/src/2geom/convex-hull.h b/src/2geom/convex-hull.h
index 4f4d10bd6..b4f078806 100644
--- a/src/2geom/convex-hull.h
+++ b/src/2geom/convex-hull.h
@@ -203,7 +203,7 @@ public:
/// @name Iterate over points.
/// @{
/** @brief Get the begin iterator to the points that form the hull.
- * Points are are returned beginning the the leftmost one, going along
+ * Points are returned beginning with the leftmost one, going along
* the upper (minimum Y) side, and then along the bottom.
* Thus the points are always ordered clockwise. No point is
* repeated. */
diff --git a/src/2geom/curve.h b/src/2geom/curve.h
index 41db9ca8a..4470366c6 100644
--- a/src/2geom/curve.h
+++ b/src/2geom/curve.h
@@ -302,7 +302,7 @@ public:
* This will return an unit vector (a Point with length() equal to 1) that denotes a vector
* tangent to the curve. This vector is defined as
* \f$ \mathbf{v}(t) = \frac{\mathbf{C}'(t)}{||\mathbf{C}'(t)||} \f$. It is pointed
- * in the direction of increasing \f$t\f$, at the specfied time value. The method uses
+ * in the direction of increasing \f$t\f$, at the specified time value. The method uses
* l'Hopital's rule when the derivative is zero. A zero vector is returned if no non-zero
* derivative could be found.
* @param t Time value
diff --git a/src/2geom/elliptical-arc-from-sbasis.cpp b/src/2geom/elliptical-arc-from-sbasis.cpp
index 54f995fb6..9be2d1265 100644
--- a/src/2geom/elliptical-arc-from-sbasis.cpp
+++ b/src/2geom/elliptical-arc-from-sbasis.cpp
@@ -42,7 +42,7 @@
namespace Geom {
-// forward declation
+// forward declaration
namespace detail
{
struct ellipse_equation;
@@ -52,7 +52,7 @@ namespace detail
* make_elliptical_arc
*
* convert a parametric polynomial curve given in symmetric power basis form
- * into an EllipticalArc type; in order to be successfull the input curve
+ * into an EllipticalArc type; in order to be successful the input curve
* has to look like an actual elliptical arc even if a certain tolerance
* is allowed through an ad-hoc parameter.
* The conversion is performed through an interpolation on a certain amount of
@@ -109,7 +109,7 @@ class make_elliptical_arc
public:
/*
* perform the actual conversion
- * return true if the conversion is successfull, false on the contrary
+ * return true if the conversion is successful, false on the contrary
*/
bool operator()()
{
diff --git a/src/2geom/elliptical-arc.h b/src/2geom/elliptical-arc.h
index 96a92eb88..d0f9db91d 100644
--- a/src/2geom/elliptical-arc.h
+++ b/src/2geom/elliptical-arc.h
@@ -246,7 +246,7 @@ public:
}
/** @brief Get the line segment connecting the arc's endpoints.
- * @return A linear segment with initial and final point correspoding to those of the arc. */
+ * @return A linear segment with initial and final point corresponding to those of the arc. */
LineSegment chord() const { return LineSegment(_initial_point, _final_point); }
/// @}
diff --git a/src/2geom/generic-rect.h b/src/2geom/generic-rect.h
index fdc7f369b..f611f3e90 100644
--- a/src/2geom/generic-rect.h
+++ b/src/2geom/generic-rect.h
@@ -89,7 +89,7 @@ public:
f[Y] = CInterval(y0, y1);
}
/** @brief Create a rectangle from a range of points.
- * The resulting rectangle will contain all ponts from the range.
+ * The resulting rectangle will contain all points from the range.
* The return type of iterators must be convertible to Point.
* The range must not be empty. For possibly empty ranges, see OptRect.
* @param start Beginning of the range
@@ -280,7 +280,7 @@ public:
void unionWith(OptCRect const &b);
/** @brief Expand the rectangle in both directions by the specified amount.
- * Note that this is different from scaling. Negative values wil shrink the
+ * Note that this is different from scaling. Negative values will shrink the
* rectangle. If <code>-amount</code> is larger than
* half of the width, the X interval will contain only the X coordinate
* of the midpoint; same for height. */
@@ -288,7 +288,7 @@ public:
expandBy(amount, amount);
}
/** @brief Expand the rectangle in both directions.
- * Note that this is different from scaling. Negative values wil shrink the
+ * Note that this is different from scaling. Negative values will shrink the
* rectangle. If <code>-x</code> is larger than
* half of the width, the X interval will contain only the X coordinate
* of the midpoint; same for height. */
@@ -374,7 +374,7 @@ public:
}
/** @brief Create a rectangle from a range of points.
- * The resulting rectangle will contain all ponts from the range.
+ * The resulting rectangle will contain all points from the range.
* If the range contains no points, the result will be an empty rectangle.
* The return type of iterators must be convertible to the corresponding
* point type (Point or IntPoint).
diff --git a/src/2geom/intersection-graph.cpp b/src/2geom/intersection-graph.cpp
index cac010942..4ee4f65fa 100644
--- a/src/2geom/intersection-graph.cpp
+++ b/src/2geom/intersection-graph.cpp
@@ -174,7 +174,7 @@ void PathIntersectionGraph::_assignEdgeWindingParities(Coord precision)
void PathIntersectionGraph::_assignComponentStatusFromDegenerateIntersections()
{
// If a path has only degenerate intersections, assign its status now.
- // This protects against later accidentaly picking a point for winding
+ // This protects against later accidentally picking a point for winding
// determination that is exactly at a removed intersection.
for (unsigned w = 0; w < 2; ++w) {
for (unsigned li = 0; li < _components[w].size(); ++li) {
@@ -410,10 +410,10 @@ PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b)
assert(!result.back().empty());
}
- if (n_processed != size() * 2) {
+ /*if (n_processed != size() * 2) {
std::cerr << "Processed " << n_processed << " intersections, expected " << (size() * 2) << std::endl;
- }
- //assert(n_processed == size() * 2);
+ }*/
+ assert(n_processed == size() * 2);
return result;
}
diff --git a/src/2geom/line.h b/src/2geom/line.h
index 62b3652f1..5d570d069 100644
--- a/src/2geom/line.h
+++ b/src/2geom/line.h
@@ -342,7 +342,7 @@ public:
* This operation is useful in reducing intersection problems to root-finding problems.
* There are many affines which do this transformation. This function returns one that
* preserves angles, areas and distances - a rotation combined with a translation, and
- * additionaly moves the initial point of the line to (0,0). This way it works without
+ * additionally moves the initial point of the line to (0,0). This way it works without
* problems even for lines perpendicular to the target, though may in some cases have
* lower precision than e.g. a shear transform.
* @param d Which coordinate of points on the line should be zero after the transformation */
@@ -431,7 +431,7 @@ bool are_parallel(Line const &l1, Line const &l2, double eps = EPSILON)
* This tests for being parallel and the origin of one line being close to the other,
* so it tests whether the images of the lines are similar, not whether the same time values
* correspond to similar points. For example a line from (1,1) to (2,2) and a line from
- * (-1,-1) to (0,0) will the the same, because their images match, even though there is
+ * (-1,-1) to (0,0) will be the same, because their images match, even though there is
* no time value for which the lines give similar points.
* @relates Line */
inline
diff --git a/src/2geom/math-utils.h b/src/2geom/math-utils.h
index 0d5d3667b..246c8dd14 100644
--- a/src/2geom/math-utils.h
+++ b/src/2geom/math-utils.h
@@ -107,7 +107,7 @@ inline void sincos(double angle, double &sin_, double &cos_) {
# define IS_NAN(_a) (__isnan(_a))
#elif defined(__APPLE__) && __GNUC__ == 3
# define IS_NAN(_a) (__isnan(_a)) /* MacOSX/Darwin definition < 10.4 */
-#elif defined(WIN32) || defined(_isnan)
+#elif defined(_WIN32) || defined(_isnan)
# define IS_NAN(_a) (_isnan(_a)) /* Win32 definition */
#elif defined(isnan) || defined(__FreeBSD__) || defined(__osf__)
# define IS_NAN(_a) (isnan(_a)) /* GNU definition */
diff --git a/src/2geom/path.cpp b/src/2geom/path.cpp
index 2e2bce9f1..3288eb4f6 100644
--- a/src/2geom/path.cpp
+++ b/src/2geom/path.cpp
@@ -455,7 +455,7 @@ Coord Path::valueAt(PathTime const &pos, Dim2 d) const
std::vector<PathTime> Path::roots(Coord v, Dim2 d) const
{
std::vector<PathTime> res;
- for (unsigned i = 0; i <= size(); i++) {
+ for (unsigned i = 0; i < size(); i++) {
std::vector<Coord> temp = (*this)[i].roots(v, d);
for (unsigned j = 0; j < temp.size(); j++)
res.push_back(PathTime(i, temp[j]));
diff --git a/src/2geom/path.h b/src/2geom/path.h
index 3552ec43e..81511b21e 100644
--- a/src/2geom/path.h
+++ b/src/2geom/path.h
@@ -728,7 +728,7 @@ public:
/** @brief Append a new curve to the path.
*
- * This family of methods will automaticaly use the current final point of the path
+ * This family of methods will automatically use the current final point of the path
* as the first argument of the new curve's constructor. To call this method,
* you'll need to write e.g.:
* @code
diff --git a/src/2geom/piecewise.h b/src/2geom/piecewise.h
index 3a12671e0..a085670f3 100644
--- a/src/2geom/piecewise.h
+++ b/src/2geom/piecewise.h
@@ -235,7 +235,7 @@ class Piecewise {
cuts[size()] = dom.max();
}
- //Concatenates this Piecewise function with another, offseting time of the other to match the end.
+ //Concatenates this Piecewise function with another, offsetting time of the other to match the end.
inline void concat(const Piecewise<T> &other) {
if(other.empty()) return;
@@ -738,7 +738,7 @@ inline Piecewise<T>& operator*=(Piecewise<T> &a, Piecewise<T> const &b) {
Piecewise<SBasis> divide(Piecewise<SBasis> const &a, Piecewise<SBasis> const &b, unsigned k);
//TODO: replace divide(a,b,k) by divide(a,b,tol,k)?
-//TODO: atm, relative error is ~(tol/a)%. Find a way to make it independant of a.
+//TODO: atm, relative error is ~(tol/a)%. Find a way to make it independent of a.
//Nota: the result is 'truncated' where b is smaller than 'zero': ~ a/max(b,zero).
Piecewise<SBasis>
divide(Piecewise<SBasis> const &a, Piecewise<SBasis> const &b, double tol, unsigned k, double zero=1.e-3);
diff --git a/src/2geom/sbasis-geometric.cpp b/src/2geom/sbasis-geometric.cpp
index 3fe27748e..275b09620 100644
--- a/src/2geom/sbasis-geometric.cpp
+++ b/src/2geom/sbasis-geometric.cpp
@@ -227,9 +227,9 @@ Geom::unitVector(D2<SBasis> const &V_in, double tol, unsigned order){
// -This approach is numerically bad. Find a stable way to rescale V_in to have non vanishing ends.
// -This done, unitVector will have jumps at zeros: fill the gaps with arcs of circles.
D2<SBasis> V = RescaleForNonVanishingEnds(V_in);
+
if (V[0].isZero(tol) && V[1].isZero(tol))
return Piecewise<D2<SBasis> >(D2<SBasis>(Linear(1),SBasis()));
-
SBasis x = V[0], y = V[1];
SBasis r_eqn1, r_eqn2;
@@ -242,6 +242,7 @@ Geom::unitVector(D2<SBasis> const &V_in, double tol, unsigned order){
r_eqn1 = -(a*x+b*y);
r_eqn2 = Linear(1.)-(a*a+b*b);
+
for (unsigned k=1; k<=order; k++){
double r0 = (k<r_eqn1.size())? r_eqn1.at(k).at0() : 0;
double r1 = (k<r_eqn1.size())? r_eqn1.at(k).at1() : 0;
@@ -614,14 +615,14 @@ solve_lambda0(double a0,double a1,double c0,double c1,
* or
* value, speed, and cross(acceleration,speed)
* of the original curve at the both ends.
-* (the second is often technically usefull, as it avoids unnecessary division by |v|^2)
+* (the second is often technically useful, as it avoids unnecessary division by |v|^2)
* Recall that K=1/R=cross(acceleration,speed)/|speed|^3.
*
* Moreover, a 7-th argument 'insist_on_speed_signs' can be supplied to select solutions:
* If insist_on_speed_signs == 1, only consider solutions where speeds at both ends are positively
* proportional to the given ones.
* If insist_on_speed_signs == 0, allow speeds to point in the opposite direction (both at the same time)
-* If insist_on_speed_signs == -1, allow speeds to point in both direction independantly.
+* If insist_on_speed_signs == -1, allow speeds to point in both direction independently.
*
* \relates D2
*/
diff --git a/src/2geom/sbasis-roots.cpp b/src/2geom/sbasis-roots.cpp
index e3e5e4441..244b7efe4 100644
--- a/src/2geom/sbasis-roots.cpp
+++ b/src/2geom/sbasis-roots.cpp
@@ -46,11 +46,11 @@
* the gsl poly roots finder is faster than bernstein too, but we don't use it for 3 reasons:
- a) it requires convertion to poly, which is numerically unstable
+ a) it requires conversion to poly, which is numerically unstable
b) it requires gsl (which is currently not a dependency, and would bring in a whole slew of unrelated stuff)
- c) it finds all roots, even complex ones. We don't want to accidently treat a nearly real root as a real root
+ c) it finds all roots, even complex ones. We don't want to accidentally treat a nearly real root as a real root
From memory gsl poly roots was about 10 times faster than bernstein in the case where all the roots
are in [0,1] for polys of order 5. I spent some time working out whether eigenvalue root finding
@@ -85,7 +85,7 @@ namespace Geom{
/** Find the smallest interval that bounds a
\param a sbasis function
- \returns inteval
+ \returns interval
*/
@@ -113,7 +113,7 @@ OptInterval bounds_exact(SBasis const &a) {
/** Find a small interval that bounds a
\param a sbasis function
- \returns inteval
+ \returns interval
*/
// I have no idea how this works, some clever bounding argument by jfb.
@@ -231,7 +231,7 @@ static void multi_roots_internal(SBasis const &f,
}
return;
}
-////usefull?
+////useful?
// if (f.size()==1){
// int idxa=upper_level(levels,fa);
// int idxb=upper_level(levels,fb);
@@ -390,8 +390,8 @@ static std::vector<Interval> fuseContiguous(std::vector<Interval> const &sets, d
-compute f at both ends of the given segment [a,b].
-compute bounds m<df(t)<M for df on the segment.
Suppose f(a) is between two 'levels' c and C. Then
- f wont enter c before a + (f(a)-c.max())/m
- f wont enter C before a + (C.min()-f(a))/M
+ f won't enter c before a + (f(a)-c.max())/m
+ f won't enter C before a + (C.min()-f(a))/M
From this we conclude nothing happens before a'=a+min((f(a)-c.max())/m,(C.min()-f(a))/M).
We do the same for b: compute some b' such that nothing happens in (b',b].
-if [a',b'] is not empty, repeat the process with [a',(a'+b')/2] and [(a'+b')/2,b'].
diff --git a/src/2geom/solve-bezier.cpp b/src/2geom/solve-bezier.cpp
index 4732169cb..ffed20626 100644
--- a/src/2geom/solve-bezier.cpp
+++ b/src/2geom/solve-bezier.cpp
@@ -218,7 +218,7 @@ void Bernsteins::find_bernstein_roots(Bezier const &bz,
dsplit_t = dsolutions[0];
split_t = left_t + (right_t - left_t)*dsplit_t;
debug(std::cout << "split_value = " << bz(split_t) << std::endl);
- debug(std::cout << "spliting around " << dsplit_t << " = "
+ debug(std::cout << "splitting around " << dsplit_t << " = "
<< split_t << "\n");
}
diff --git a/src/2geom/sync.sh b/src/2geom/sync.sh
deleted file mode 100755
index a2c162903..000000000
--- a/src/2geom/sync.sh
+++ /dev/null
@@ -1,31 +0,0 @@
-#!/bin/bash
-set -e
-
-function usage {
- echo "2Geom sync to upstream script"
- echo "Usage: $0 path/to/2geom/checkout/dir"
-}
-
-if [ "x$(which rsync)" = "x" ]; then
- echo "rsync not found on your system, please install it"
- exit 1
-fi
-
-if [ "x$1" = "x" ]; then
- usage $0
- exit 64
-fi
-if [ ! -d "$1" ]; then
- usage $0
- exit 64
-fi
-if [ ! -f "$1/src/2geom/path.h" ]; then
- usage $0
- exit 64
-fi
-
-INK_2GEOM="$(dirname $0)/"
-UPSTREAM_2GEOM="$1/src/2geom/"
-rsync -r --existing \
- --exclude CMakeLists.txt --exclude sync.sh \
- "$UPSTREAM_2GEOM" "$INK_2GEOM"
diff --git a/src/2geom/toposweep.cpp b/src/2geom/toposweep.cpp
deleted file mode 100644
index 3cb231142..000000000
--- a/src/2geom/toposweep.cpp
+++ /dev/null
@@ -1,666 +0,0 @@
-#include <2geom/toposweep.h>
-
-#include <2geom/path-intersection.h>
-#include <2geom/basic-intersection.h>
-
-//using namespace Geom;
-
-namespace Geom {
-
-TopoGraph::Edge &TopoGraph::Vertex::operator[](unsigned ix) {
- ix %= degree();
- return ix < enters.size() ? enters[ix] : exits[ix - enters.size()];
-}
-
-TopoGraph::Edge TopoGraph::Vertex::operator[](unsigned ix) const {
- ix %= degree();
- return ix < enters.size() ? enters[ix] : exits[ix - enters.size()];
-}
-
-void TopoGraph::Vertex::erase(unsigned ix) {
- ix %= degree();
- if(ix < enters.size())
- enters.erase(enters.begin() + ix);
- else
- exits.erase(exits.begin() + (ix - enters.size()));
-}
-
-void TopoGraph::Vertex::insert(unsigned ix, Edge v) {
- ix %= degree();
- if(ix < enters.size())
- enters.insert(enters.begin() + ix, v);
- else
- exits.insert(exits.begin() + (ix - enters.size()), v);
-}
-
-unsigned TopoGraph::Vertex::find_section(boost::shared_ptr<Section> section) const {
- unsigned i = 0;
- for(; i < degree(); i++)
- if((*this)[i].section == section) return i;
- return i;
-}
-
-TopoGraph::Edge TopoGraph::remove_edge(unsigned ix, unsigned jx) {
- Vertex &v = vertices[ix];
- if(v.degree()) {
- jx %= v.degree();
- Edge &ret = v[jx];
- v.erase(jx);
- v = vertices[ret.other];
- if(v.degree()) {
- v.erase(v.find_section(ret.section));
- return ret;
- }
- }
- assert(0);
- return v[0]; // if assert is disabled, return first Edge.
-}
-
-void TopoGraph::cannonize() {
- std::vector<unsigned> vix;
- unsigned ix = 0;
- for(unsigned i = 0; i < vertices.size(); i++) {
- vix.push_back(ix);
- if(vertices[i].degree() != 0) vertices[ix++] = vertices[i];
- }
-
- for(unsigned i = 0; i < ix; i++)
- for(unsigned j = 0; j < vertices[i].degree(); j++)
- vertices[i][j].other = vix[vertices[i][j].other];
-}
-
-
-void TopoGraph::assert_invariants() const {
- for(unsigned i = 0; i < vertices.size(); i++) {
- for(unsigned j = 0; j < vertices[i].degree(); j++) {
- Edge e = vertices[i][j];
- assert(e.other != i);
- assert(are_near(e.section->fp, vertices[i].avg, tol) || are_near(e.section->tp, vertices[i].avg, tol));
- assert(!are_near(e.section->fp, e.section->tp, tol));
- assert(e.section.get());
- unsigned oix = vertices[e.other].find_section(e.section);
- assert(oix != vertices[e.other].degree());
- }
- }
-}
-
-//near predicate utilized in process_splits
-template<typename T>
-struct NearPredicate { bool operator()(T x, T y) { return are_near(x, y); } };
-
-// ensures that f and t are elements of a vector, sorts and uniqueifies
-// also asserts that no values fall outside of f and t
-// if f is greater than t, the sort is in reverse
-void process_splits(std::vector<double> &splits, double f, double t) {
- splits.push_back(f);
- std::sort(splits.begin(), splits.end());
- while(are_near(splits.back(), t)) splits.erase(splits.end() - 1);
- splits.push_back(t);
- if(f > t) std::reverse(splits.begin(), splits.end());
-
- //remove any splits which fall outside t / f
- while(!splits.empty() && splits.front() != f) splits.erase(splits.begin());
- while(!splits.empty() && splits.back() != t) splits.erase(splits.end() - 1);
-
- std::vector<double>::iterator end = std::unique(splits.begin(), splits.end(), NearPredicate<double>());
- splits.resize(end - splits.begin());
-}
-
-// A little sugar for appending a list to another
-template<typename T>
-void concatenate(T &a, T const &b) { a.insert(a.end(), b.begin(), b.end()); }
-
-//returns a list of monotonic sections of a path
-//TODO: handle saddle points
-std::vector<boost::shared_ptr<Section> > mono_sections(PathVector const &ps, Dim2 d) {
- std::vector<boost::shared_ptr<Section> > monos;
- for(unsigned i = 0; i < ps.size(); i++) {
- //TODO: necessary? can we have empty paths?
- if(ps[i].size()) {
- for(unsigned j = 0; j < ps[i].size(); j++) {
- //find the points of 0 derivative
- Curve* deriv = ps[i][j].derivative();
- std::vector<double> splits = deriv->roots(0, X);
- concatenate(splits, deriv->roots(0, Y));
- delete deriv;
- process_splits(splits, 0, 1);
- //split on points of 0 derivative
- for(unsigned k = 1; k < splits.size(); k++)
- monos.push_back(boost::shared_ptr<Section>(new Section(CurveIx(i,j), splits[k-1], splits[k], ps, d)));
- }
- }
- }
- return monos;
-}
-
-//finds the t-value on a section, which corresponds to a particular horizontal or vertical line
-//d indicates the dimension along which the roots is performed.
-//-1 is returned if no root is found
-double section_root(Section const &s, PathVector const &ps, double v, Dim2 d) {
- std::vector<double> roots = s.curve.get(ps).roots(v, d);
- for(unsigned j = 0; j < roots.size(); j++)
- if(Interval(s.f, s.t).contains(roots[j])) return roots[j];
- return -1;
-}
-
-bool SectionSorter::section_order(Section const &a, double at, Section const &b, double bt) const {
- Point ap = a.curve.get(ps).pointAt(at);
- Point bp = b.curve.get(ps).pointAt(bt);
- if(are_near(ap[dim], bp[dim], tol)) {
- // since the sections are monotonic, if the endpoints are on opposite sides of this
- // coincidence, the order is determinable
- if(a.tp[dim] < ap[dim] && b.tp[dim] > bp[dim]) return true;
- if(a.tp[dim] > ap[dim] && b.tp[dim] < bp[dim]) return false;
- //TODO: sampling / higher derivatives when unit tangents match
- Point ad = a.curve.get(ps).unitTangentAt(a.f);
- Point bd = b.curve.get(ps).unitTangentAt(b.f);
- // tangent can point backwards
- if(ad[1-dim] < 0) ad = -ad;
- if(bd[1-dim] < 0) bd = -bd;
- return ad[dim] < bd[dim];
- }
- return ap[dim] < bp[dim];
-}
-
-bool SectionSorter::operator()(Section const &a, Section const &b) const {
- if(&a == &b) return false;
- Rect ra = a.bbox(), rb = b.bbox();
- //TODO: should we use tol in these conditions?
- if(ra[dim].max() <= rb[dim].min()) return true;
- if(rb[dim].max() <= ra[dim].min()) return false;
- //we know that the rects intersect on dim
- //by referencing f / t we are assuming that the section was constructed with 1-dim
- if(ra[1-dim].intersects(rb[1-dim])) {
- if(are_near(a.fp[1-dim], b.fp[1-dim], tol)) {
- return section_order(a, a.f > a.t ? a.f - 0.01 : a.f + 0.01,
- b, b.f > b.t ? b.f - 0.01 : b.f + 0.01);
- } else if(a.fp[1-dim] < b.fp[1-dim]) {
- //b inside a
- double ta = section_root(a, ps, b.fp[1-dim], Dim2(1-dim));
- //TODO: fix bug that necessitates this
- if(ta == -1) ta = (a.t + a.f) / 2;
- return section_order(a, ta, b, b.f);
- } else {
- //a inside b
- double tb = section_root(b, ps, a.fp[1-dim], Dim2(1-dim));
- //TODO: fix bug that necessitates this
- if(tb == -1) tb = (b.t + b.f) / 2;
- return section_order(a, a.f, b, tb);
- }
- }
-
- return Point::LexLessRt(dim)(a.fp, b.fp);
-}
-
-// splits a section into pieces, as specified by an array of doubles, mutating the section to
-// represent the first part, and returning the rest
-//TODO: output iterator?
-std::vector<boost::shared_ptr<Section> > split_section(boost::shared_ptr<Section> s, PathVector const &ps, std::vector<double> &cuts, Dim2 d) {
- std::vector<boost::shared_ptr<Section> > ret;
-
- process_splits(cuts, s->f, s->t);
- if(cuts.size() <= 2) return ret;
-
- s->t = cuts[1];
- s->tp = s->curve.get(ps)(cuts[1]);
- assert(Point::LexLessRt(d)(s->fp, s->tp));
-
- ret.reserve(cuts.size() - 2);
- for(int i = cuts.size() - 1; i > 1; i--) ret.push_back(boost::shared_ptr<Section>(new Section(s->curve, cuts[i-1], cuts[i], ps, d)));
- return ret;
-}
-
-//merges the sorted lists a and b according to comparison z
-template<typename X, typename Z>
-void merge(X &a, X const &b, Z const &z) {
- a.reserve(a.size() + b.size());
- unsigned start = a.size();
- concatenate(a, b);
- std::inplace_merge(a.begin(), a.begin() + start, a.end(), z);
-}
-
-//TODO: faster than linear
-unsigned find_vertex(std::vector<TopoGraph::Vertex> const &vertices, Point p, double tol) {
- for(unsigned i = 0; i < vertices.size(); i++)
- if(are_near(vertices[i].avg, p, tol)) return i;
- return vertices.size();
-}
-
-//takes a vector of T pointers, and returns a vector of T with copies
-template<typename T>
-std::vector<T> deref_vector(std::vector<boost::shared_ptr<T> > const &xs, unsigned from = 0) {
- std::vector<T> ret;
- ret.reserve(xs.size() - from);
- for(unsigned i = from; i < xs.size(); i++)
- ret.push_back(T(*xs[i]));
- return ret;
-}
-
-//used to create reversed sorting predicates
-template<typename C>
-struct ReverseAdapter {
- typedef typename C::second_argument_type first_argument_type;
- typedef typename C::first_argument_type second_argument_type;
- typedef typename C::result_type result_type;
- const C &comp;
- ReverseAdapter(const C &c) : comp(c) {}
- result_type operator()(const first_argument_type &a, const second_argument_type &b) const { return comp(b, a); }
-};
-
-//used to sort std::vector<Section*>
-template<typename C>
-struct DerefAdapter {
- typedef typename boost::shared_ptr<typename C::first_argument_type> first_argument_type;
- typedef typename boost::shared_ptr<typename C::second_argument_type> second_argument_type;
- typedef typename C::result_type result_type;
- const C &comp;
- DerefAdapter(const C &c) : comp(c) {}
- result_type operator()(const first_argument_type a, const second_argument_type b) const {
- if(!a) return false;
- if(!b) return true;
- return comp(*a, *b);
- }
-};
-
-struct EdgeSorter {
- typedef TopoGraph::Edge first_argument_type;
- typedef TopoGraph::Edge second_argument_type;
- typedef bool result_type;
- SectionSorter s;
- EdgeSorter(const PathVector &rs, Dim2 d, double t) : s(rs, d, t) {}
- bool operator()(TopoGraph::Edge const &e1, TopoGraph::Edge const &e2) const { return s(*e1.section, *e2.section); }
-};
-
-#ifdef SWEEP_GRAPH_DEBUG
-//used for debugging purposes - each element represents a subsequent iteration of the algorithm.
-std::vector<std::vector<Section> > monoss;
-std::vector<std::vector<Section> > chopss;
-std::vector<std::vector<Section> > contexts;
-#endif
-
-/*
- 1) take item off sweep sorted todo
- 2) find all of the to-values before the beginning of this section
- 3) sort these lexicographically, process them in order, grouping other sections in the context, and constructing a vertex in one fell swoop.
- 4) add our section into context, splitting on intersections
-
- 3 is novel, we perform it by storing
- */
-
-template<typename A, typename B, typename Z>
-struct MergeIterator {
- A const &a;
- B &b;
- Z const &z;
- unsigned ai;
- bool on_a;
- MergeIterator(A const &av, B &bv, Z const &zv) : a(av), b(bv), z(zv), ai(0), on_a(b.empty() || z(a[0], b.back())) {}
- MergeIterator &operator++() {
- if(!done()) {
- on_a = b.empty() ? true : (ai >= a.size() ? false : z(a[ai], b.back()));
- if(on_a) {
- ++ai;
- if(ai >= a.size()) on_a = false;
- } else {
- b.erase(b.end());
- if(b.empty()) on_a = true;
- }
- }
- return *this;
- }
- typename A::value_type operator*() {
- assert(!done());
- return on_a ? a[ai] : b.back();
- }
- bool done() { return b.empty() && ai >= a.size() - 1; }
- typename A::value_type operator->() { assert(!done()); return on_a ? a[ai] : b.back(); }
-};
-
-void modify_windings(std::vector<int> &windings, boost::shared_ptr<Section> sec, Dim2 d) {
- unsigned k = sec->curve.path;
- if(k >= windings.size() || sec->fp[d] == sec->tp[d]) return;
- if(sec->f < sec->t) windings[k]++;
- if(sec->f > sec->t) windings[k]--;
-}
-
-struct Context {
- boost::shared_ptr<Section> section;
- int from_vert;
- int to_vert;
- Context(boost::shared_ptr<Section> sect, int from) : section(sect), from_vert(from), to_vert(-1) {}
-};
-
-template<typename C>
-struct ContextAdapter {
- typedef Context first_argument_type;
- typedef typename C::second_argument_type second_argument_type;
- typedef typename C::result_type result_type;
- const C &comp;
- ContextAdapter(const C &c) : comp(c) {}
- result_type operator()(const Context &a, const second_argument_type &b) const { return comp(a.section, b); }
-};
-
-#define DINF std::numeric_limits<double>::infinity()
-
-TopoGraph::TopoGraph(PathVector const &ps, Dim2 d, double t) : dim(d), tol(t) {
- //s_sort = vertical section order
- ContextAdapter<DerefAdapter<SectionSorter> > s_sort = DerefAdapter<SectionSorter>(SectionSorter(ps, (Dim2)(1-d), tol));
- //sweep_sort = horizontal sweep order
- DerefAdapter<SweepSorter> sweep_sort = DerefAdapter<SweepSorter>(SweepSorter(d));
- //heap_sort = reverse horizontal sweep order
- ReverseAdapter<DerefAdapter<SweepSorter> > heap_sort = ReverseAdapter<DerefAdapter<SweepSorter> >(sweep_sort);
- //edge_sort = sorter for edges
- EdgeSorter edge_sort = EdgeSorter(ps, (Dim2)(1-d), tol);
-
- std::vector<boost::shared_ptr<Section> > input_sections = mono_sections(ps, d), chops;
- std::sort(input_sections.begin(), input_sections.end(), sweep_sort);
-
- std::vector<Context> context;
-
- vertices.reserve(input_sections.size());
-
- //std::vector<unsigned> to_process;
-
- std::vector<int> windings(ps.size(), 0);
- for(MergeIterator<Area, Area, DerefAdapter<SweepSorter> > iter(input_sections, chops, sweep_sort); ; ++iter) {
- //represents our position in the sweep, which controls what we finalize
- //if we have no more to process, finish the rest by setting our position to infinity
- Point lim;
- if(iter.done()) lim[X] = lim[Y] = DINF; else lim = iter->fp;
-
- /*
- //finalize vertices
- for(unsigned i = 0; i < to_process.size(); i++) {
- if(vertices[to_process[i]].avg[d] + tol < lim[d])
- for(unsigned j = 0; j < context.size(); j++) {
-
- }
- } */
-
- //find all sections to remove
- for(int i = context.size() - 1; i >= 0; i--) {
- boost::shared_ptr<Section> sec = context[i].section;
- if(Point::LexLessRt(d)(lim, sec->tp)) {
- //sec->tp is less than or equal to lim
- if(context[i].to_vert == -1) {
- //we need to create a new vertex; add everything that enters it
- //Point avg;
- //unsigned cnt;
- std::vector<Edge> enters;
- std::fill(windings.begin(), windings.end(), 0);
- for(unsigned j = 0; j < context.size(); j++) {
- modify_windings(windings, context[j].section, d);
- if(are_near(sec->tp, context[j].section->tp, tol)) {
- assert(-1 == context[j].to_vert);
- context[j].section->windings = windings;
- context[j].to_vert = vertices.size();
- enters.push_back(Edge(context[j].section, context[j].from_vert));
- //avg += context[j].section->tp;
- //cnt++;
- }
- }
- //Vertex &v(avg / (double)cnt);
- Vertex v(context[i].section->tp);
- v.enters = enters;
- vertices.push_back(v);
- //to_process.push_back(vertices.size() - 1);
- }
- context.erase(context.begin() + i);
- }
- }
-
- if(!iter.done()) {
- boost::shared_ptr<Section> s = *iter;
-
- //create a new context, associate a beginning vertex, and insert it in the proper location
- unsigned ix = find_vertex(vertices, s->fp, tol);
- if(ix == vertices.size()) {
- vertices.push_back(Vertex(s->fp));
- //to_process.push_back(vertices.size() - 1);
- }
- unsigned context_ix = std::lower_bound(context.begin(), context.end(), s, s_sort) - context.begin();
-
- context.insert(context.begin() + context_ix, Context(s, ix));
-
- Interval si = Interval(s->fp[1-d], s->tp[1-d]);
-
- // Now we intersect with neighbors - do a sweep!
- std::vector<double> this_splits;
- for(unsigned i = 0; i < context.size(); i++) {
- if(context[i].section == context[context_ix].section) continue;
-
- boost::shared_ptr<Section> sec = context[i].section;
-
- if(!si.intersects(Interval(sec->fp[1-d], sec->tp[1-d]))) continue;
-
- std::vector<double> other_splits;
- Crossings xs = mono_intersect(s->curve.get(ps), Interval(s->f, s->t),
- sec->curve.get(ps), Interval(sec->f, sec->t));
- if(xs.empty()) continue;
-
- for(unsigned j = 0; j < xs.size(); j++) {
- this_splits.push_back(xs[j].ta);
- other_splits.push_back(xs[j].tb);
- }
- merge(chops, split_section(sec, ps, other_splits, d), heap_sort);
- }
- if(!this_splits.empty())
- merge(chops, split_section(context[context_ix].section, ps, this_splits, d), heap_sort);
-
- std::sort(chops.begin(), chops.end(), heap_sort);
-
- if(context[context_ix].section->tp[d] - context[context_ix].section->fp[d] <= tol) {
- if(!are_near(context[context_ix].section->tp, context[context_ix].section->fp, tol)) {
- ix = find_vertex(vertices, context[context_ix].section->tp, tol);
- if(ix != vertices.size()) {
- boost::shared_ptr<Section> sec = context[context_ix].section;
- Edge e(sec, context[context_ix].from_vert);
-
- std::vector<Edge>::iterator it = std::lower_bound(vertices[ix].enters.begin(), vertices[ix].enters.end(), e, edge_sort);
-
- if(vertices[ix].enters.empty()) {
- std::fill(windings.begin(), windings.end(), 0);
- for(unsigned j = 0; j <= context_ix; j++) modify_windings(windings, context[j].section, d);
- } else if(it == vertices[ix].enters.end()) {
- windings = (it-1)->section->windings;
- modify_windings(windings, (it-1)->section, d);
- } else {
- windings = it->section->windings;
- }
-
- sec->windings = windings;
- modify_windings(windings, sec, d);
-
- for(std::vector<Edge>::iterator it2 = it; it2 != vertices[ix].enters.end(); ++it2) {
- it2->section->windings = windings;
- modify_windings(windings, it2->section, d);
- }
-
- vertices[ix].enters.insert(it, e);
- context.erase(context.begin() + context_ix);
- }
- } else context.erase(context.begin() + context_ix);
- }
- }
-
- #ifdef SWEEP_GRAPH_DEBUG
- std::vector<Section> rem;
- for(unsigned i = iter.ai + 1; i < iter.a.size(); i++) rem.push_back(*iter.a[i]);
- monoss.push_back(rem);
- chopss.push_back(deref_vector(iter.b));
- rem.clear();
- for(unsigned i = 0; i < context.size(); i++) rem.push_back(*context[i].section);
- contexts.push_back(rem);
- #endif
-
- if(iter.done() && context.empty()) return;
- }
-}
-
-void trim_whiskers(TopoGraph &g) {
- std::vector<unsigned> affected;
-
- for(unsigned i = 0; i < g.size(); i++)
- if(g[i].degree() == 1) affected.push_back(i);
-
- while(!affected.empty()) {
- unsigned j = 0;
- for(unsigned i = 0; i < affected.size(); i++)
- if(g[affected[i]].degree() == 1)
- affected[j++] = g.remove_edge(affected[i], 0).other;
- affected.resize(j);
- }
-}
-
-void add_edge_at(TopoGraph &g, unsigned ix, boost::shared_ptr<Section> s, TopoGraph::Edge jx, bool before = true) {
- TopoGraph::Vertex &v = g[ix];
- for(unsigned i = 0; i < v.enters.size(); i++) {
- if(v.enters[i].section == s) {
- v.enters.insert(v.enters.begin() + (before ? i : i + 1), jx);
- return;
- }
- }
- for(unsigned i = 0; i < v.exits.size(); i++) {
- if(v.exits[i].section == s) {
- v.exits.insert(v.exits.begin() + (before ? i : i + 1), jx);
- return;
- }
- }
- //TODO: fix the fall through to here
- //assert(false);
-}
-
-void double_whiskers(TopoGraph &g) {
- for(unsigned i = 0; i < g.size(); i++) {
- if(g[i].degree() == 1) {
- unsigned j = i;
- TopoGraph::Edge e = g[i][0];
- while(true) {
- TopoGraph::Edge next_edge = g[j][1 - g[j].find_section(e.section)];
- boost::shared_ptr<Section> new_section = boost::shared_ptr<Section>(new Section(*e.section));
- add_edge_at(g, j, e.section, TopoGraph::Edge(new_section, e.other), false);
- add_edge_at(g, e.other, e.section, TopoGraph::Edge(new_section, j), true);
-
- if(g[e.other].degree() == 3) {
- j = e.other;
- e = next_edge;
- } else break;
- }
- }
- }
-}
-
-/*
-void remove_degenerate(TopoGraph &g) {
- for(unsigned i = 0; i < g.size(); i++) {
- for(int j = g[i].degree(); j >= 0; j--) {
- if(g[i][j].other == i)
- }
- }
-}*/
-
-/*
-void remove_vestigial(TopoGraph &g) {
- for(unsigned i = 0; i < g.size(); i++) {
- if(g[i].enters.size() == 1 && g[i].exits.size() == 1) {
- TopoGraph::Edge &e1 = g[i][0], &e2 = g[i][1];
- if(e1.section == e2.section) {
- //vestigial vert
- Section *new_section = new Section(e1.section->curve,
- e1.section->f, e2.section->t,
- e1.section->fp, e2.section->tp);
-
- e1.other
-
- Vertex *v1 = e1.other, *v2 = e2.other;
- v1->lookup_section(e1.section) = Edge(new_section, v2);
- v2->lookup_section(e2.section) = Edge(new_section, v1);
- g.erase(g.begin() + i);
- }
- }
- }
-}*/
-
-//planar area finding
-//linear on number of edges
-Areas traverse_areas(TopoGraph const &g) {
- Areas ret;
-
- //stores which edges we've visited
- std::vector<std::vector<bool> > visited;
- for(unsigned i = 0; i < g.size(); i++) visited.push_back(std::vector<bool>(g[i].degree(), false));
-
- for(unsigned vix = 0; vix < g.size(); vix++) {
- while(true) {
- //find an unvisited edge to start on
-
- unsigned e_ix = std::find(visited[vix].begin(), visited[vix].end(), false) - visited[vix].begin();
- if(e_ix == g[vix].degree()) break;
-
- unsigned start = e_ix;
- unsigned cur = vix;
-
- Area area;
- //std::vector<std::vector<bool> > before(visited);
- while(cur < g.size() && !visited[cur][e_ix]) {
- visited[cur][e_ix] = true;
-
- TopoGraph::Edge e = g[cur][e_ix];
-
- area.push_back(e.section);
-
- //go to clockwise edge
- cur = e.other;
- unsigned deg = g[cur].degree();
- e_ix = g[cur].find_section(e.section);
-
- if(deg == 1 || e_ix == deg) {
- visited[cur][e_ix] = true;
- break;
- }
-
- e_ix = (e_ix + 1) % deg;
-
- if(cur == vix && start == e_ix) break;
- }
- //if(vix == cur && start == e_ix) {
- ret.push_back(area);
- //} else visited = before;
- }
- }
- return ret;
-}
-
-void remove_area_whiskers(Areas &areas) {
- for(int i = areas.size() - 1; i >= 0; i--)
- if(areas[i].size() == 2 && *areas[i][0] == *areas[i][1])
- areas.erase(areas.begin() + i);
-}
-
-Path area_to_path(PathVector const &ps, Area const &area) {
- Path ret;
- ret.setStitching(true);
- if(area.size() == 0) return ret;
- Point prev = area[0]->fp;
- for(unsigned i = 0; i < area.size(); i++) {
- bool forward = are_near(area[i]->fp, prev, 0.01);
- Curve *curv = area[i]->curve.get(ps).portion(
- forward ? area[i]->f : area[i]->t,
- forward ? area[i]->t : area[i]->f);
- ret.append(*curv);
- delete curv;
- prev = forward ? area[i]->tp : area[i]->fp;
- }
- ret.setStitching(false);
- return ret;
-}
-
-PathVector areas_to_paths(PathVector const &ps, Areas const &areas) {
- PathVector ret;
- //ret.reserve(areas.size());
- for(unsigned i = 0; i < areas.size(); ++i)
- ret.push_back(area_to_path(ps, areas[i]));
- return ret;
-}
-
-} // end namespace Geom
diff --git a/src/2geom/toposweep.h b/src/2geom/toposweep.h
deleted file mode 100644
index 7faf890e1..000000000
--- a/src/2geom/toposweep.h
+++ /dev/null
@@ -1,222 +0,0 @@
-/**
- * \file
- * \brief TopoSweep - topology / graph representation of a PathVector, for boolean operations and related tasks
- *//*
- * Authors:
- * Michael Sloan <mgsloan at gmail.com>
- * Nathan Hurst <njhurst at njhurst.com>
- *
- * Copyright 2007-2009 authors
- *
- * This library is free software; you can redistribute it and/or
- * modify it either under the terms of the GNU Lesser General Public
- * License version 2.1 as published by the Free Software Foundation
- * (the "LGPL") or, at your option, under the terms of the Mozilla
- * Public License Version 1.1 (the "MPL"). If you do not alter this
- * notice, a recipient may use your version of this file under either
- * the MPL or the LGPL.
- *
- * You should have received a copy of the LGPL along with this library
- * in the file COPYING-LGPL-2.1; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
- * You should have received a copy of the MPL along with this library
- * in the file COPYING-MPL-1.1
- *
- * The contents of this file are subject to the Mozilla Public License
- * Version 1.1 (the "License"); you may not use this file except in
- * compliance with the License. You may obtain a copy of the License at
- * http://www.mozilla.org/MPL/
- *
- * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
- * OF ANY KIND, either express or implied. See the LGPL or the MPL for
- * the specific language governing rights and limitations.
- */
-
-#ifndef LIB2GEOM_SEEN_TOPOSWEEP_H
-#define LIB2GEOM_SEEN_TOPOSWEEP_H
-
-#include <2geom/coord.h>
-#include <2geom/point.h>
-#include <2geom/pathvector.h>
-#include <2geom/rect.h>
-#include <2geom/path.h>
-#include <2geom/curve.h>
-
-#include <boost/shared_ptr.hpp>
-
-namespace Geom {
-
-// indicates a particular curve in a pathvector
-struct CurveIx {
- unsigned path, ix;
- CurveIx(unsigned p, unsigned i) : path(p), ix(i) {}
- // retrieves the indicated curve from the pathvector
- Curve const &get(PathVector const &ps) const {
- return ps[path][ix];
- }
- bool operator==(CurveIx const &other) const {
- return other.path == path && other.ix == ix;
- }
-};
-
-// represents a monotonic section of a path
-struct Section {
- CurveIx curve;
- double f, t;
- Point fp, tp;
- std::vector<int> windings;
- Section(CurveIx cix, double fd, double td, Point fdp, Point tdp) : curve(cix), f(fd), t(td), fp(fdp), tp(tdp) { }
- Section(CurveIx cix, double fd, double td, PathVector ps, Dim2 d) : curve(cix), f(fd), t(td) {
- fp = curve.get(ps).pointAt(f), tp = curve.get(ps).pointAt(t);
- if (Point::LexLessRt(d)(tp, fp)) {
- //swap from and to, since tp is left or above fp
- using std::swap;
- swap(f, t);
- swap(fp, tp);
- }
- }
- Rect bbox() const { return Rect(fp, tp); }
- bool operator==(Section const &other) const {
- return (curve == other.curve) && (f == other.f) && (t == other.t);
- }
-};
-
-class TopoGraph {
- public:
-
- // Represents an e double tol;dge on a vertex
- class Edge {
- public:
- boost::shared_ptr<Section> section; // section associated with this edge
- unsigned other; // index of the vertex this edge points to
- Edge(boost::shared_ptr<Section> s, unsigned o) : section(s), other(o) {}
- };
-
- // Represents a vertex in the graph, in terms of a point and edges which enter and exit.
- // A vertex has an "avg" point, which is a representative point for the vertex. All
- // edges have an endpoint tol away.
- class Vertex {
- public:
- std::vector<Edge> enters, exits; // indexes of the enter / exit edges
- Point avg;
- Vertex(Point p) : avg(p) {}
- inline unsigned degree() const { return enters.size() + exits.size(); }
- Edge operator[](unsigned ix) const;
- Edge &operator[](unsigned ix);
- void erase(unsigned ix);
- void insert(unsigned ix, Edge e);
- unsigned find_section(boost::shared_ptr<Section> section) const;
- };
-
- TopoGraph(PathVector const &ps, Dim2 d, double t);
-
- unsigned size() const { return vertices.size(); }
-
- Vertex &operator[](unsigned ix) { return vertices[ix]; }
- Vertex const &operator[](unsigned ix) const { return vertices[ix]; }
-
- //removes both edges, and returns the vertices[ix][jx] one
- Edge remove_edge(unsigned ix, unsigned jx);
-
- //returns a graph with all zero degree vertices and unused edges removed
- void cannonize();
-
- //checks invariants
- void assert_invariants() const;
-
- std::vector<Vertex> vertices;
- Dim2 dim;
- double tol;
-};
-
-//TODO: convert to classes
-typedef std::vector<boost::shared_ptr<Section> > Area;
-typedef std::vector<Area> Areas;
-
-//TopoGraph sweep_graph(PathVector const &ps, Dim2 d = X, double tol = 0.00001);
-
-void trim_whiskers(TopoGraph &g);
-void double_whiskers(TopoGraph &g);
-//void remove_degenerate(TopoGraph &g);
-//void remove_vestigial(TopoGraph &g);
-//Areas traverse_areas(TopoGraph const &g);
-
-
-void remove_area_whiskers(Areas &areas);
-PathVector areas_to_paths(PathVector const &ps, Areas const &areas);
-
-class SectionSorter {
- const PathVector &ps;
- Dim2 dim;
- double tol;
- bool section_order(Section const &a, double at, Section const &b, double bt) const;
- public:
- typedef Section first_argument_type;
- typedef Section second_argument_type;
- typedef bool result_type;
-
- SectionSorter(const PathVector &rs, Dim2 d, double t = 0.00001) : ps(rs), dim(d), tol(t) {}
- bool operator()(Section const &a, Section const &b) const;
-};
-
-//sorter used to create the initial sweep of sections, such that they are dealt with in order
-struct SweepSorter {
- typedef Section first_argument_type;
- typedef Section second_argument_type;
- typedef bool result_type;
- Dim2 dim;
- SweepSorter(Dim2 d) : dim(d) {}
- bool operator()(const Section &a, const Section &b) const {
- return Point::LexLessRt(dim)(a.fp, b.fp);
- }
-};
-
-struct UnionOp {
- unsigned ix;
- bool nz1, nz2;
- UnionOp(unsigned i, bool a, bool b) : ix(i), nz1(a), nz2(b) {}
- bool operator()(std::vector<int> const &windings) const {
- int w1 = 0, w2 = 0;
- for(unsigned j = 0; j < ix; j++) w1 += windings[j];
- for(unsigned j = ix; j < windings.size(); j++) w2 += windings[j];
- return (nz1 ? w1 : w1 % 2) != 0 || (nz2 ? w2 : w2 % 2) != 0;
- }
-};
-
-//returns all areas for which the winding -> bool function yields true
-template<class Z>
-Areas filter_areas(PathVector const &ps, Areas const & areas, Z const &z) {
- Areas ret;
- SweepSorter sorty = SweepSorter(Y);
- SectionSorter sortx = SectionSorter(ps, X);
- for(unsigned i = 0; i < areas.size(); i++) {
- if(areas[i].size() < 2) continue;
- //find a representative section
- unsigned rj = 0;
- //bool rev = are_near(areas[i][0]->fp, areas[i][1]->tp);
- for(unsigned j = 1; j < areas[i].size(); j++)
- if(sorty(*areas[i][rj], *areas[i][j])) rj = j;
- if(sortx(*areas[i][rj], *areas[i][(rj+areas[i].size() - 1) % areas[i].size()])) {
- rj = 0;
- for(unsigned j = 1; j < areas[i].size(); j++)
- if(sorty(*areas[i][j], *areas[i][rj])) rj = j;
- }
- if(z(areas[i][rj]->windings)) ret.push_back(areas[i]);
- }
- return ret;
-}
-
-} // end namespace Geom
-
-#endif // LIB2GEOM_SEEN_TOPOSWEEP_H
-
-/*
- Local Variables:
- mode:c++
- c-file-style:"stroustrup"
- c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
- indent-tabs-mode:nil
- fill-column:99
- End:
-*/
-// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
diff --git a/src/2geom/transforms.h b/src/2geom/transforms.h
index de4e6871f..cc55e2934 100644
--- a/src/2geom/transforms.h
+++ b/src/2geom/transforms.h
@@ -142,7 +142,7 @@ inline bool are_near(Translate const &a, Translate const &b, Coord eps=EPSILON)
}
/** @brief Scaling from the origin.
- * During scaling, the point (0,0) will not move. To obtain a scale with a different
+ * During scaling, the point (0,0) will not move. To obtain a scale with a different
* invariant point, combine with translation to the origin and back.
* @ingroup Transforms */
class Scale