diff --git a/src/helper/geom.cpp b/src/helper/geom.cpp
index 39dd2414aafa097d73961f873bed1850d5e9c774..cc9064451f833004f8ac979673c8f99d3aa6137f 100644 (file)
--- a/src/helper/geom.cpp
+++ b/src/helper/geom.cpp
*/
#include "helper/geom.h"
+#include "helper/geom-curves.h"
#include <typeinfo>
#include <2geom/pathvector.h>
#include <2geom/path.h>
+#include <2geom/bezier-curve.h>
+#include <2geom/hvlinesegment.h>
#include <2geom/transforms.h>
#include <2geom/rect.h>
#include <2geom/coord.h>
bbox[0].extendTo(x111);
bbox[1].extendTo(y111);
+ // It already contains (x000,y000) and (x111,y111)
+ // All points of the Bezier lie in the convex hull of (x000,y000), (x001,y001), (x011,y011) and (x111,y111)
+ // So, if it also contains (x001,y001) and (x011,y011) we don't have to compute anything else!
+ // Note that we compute it for the X and Y range separately to make it easier to use them below
+ bool containsXrange = bbox[0].contains(x001) && bbox[0].contains(x011);
+ bool containsYrange = bbox[1].contains(y001) && bbox[1].contains(y011);
+
/*
* xttt = s * (s * (s * x000 + t * x001) + t * (s * x001 + t * x011)) + t * (s * (s * x001 + t * x011) + t * (s * x011 + t * x111))
* xttt = s * (s2 * x000 + s * t * x001 + t * s * x001 + t2 * x011) + t * (s2 * x001 + s * t * x011 + t * s * x011 + t2 * x111)
@@ -57,101 +67,103 @@ cubic_bbox (Geom::Coord x000, Geom::Coord y000, Geom::Coord x001, Geom::Coord y0
* ( 3 * x011 - 3 * x111)
*/
- a = 3 * x000 - 9 * x001 + 9 * x011 - 3 * x111;
- b = 6 * x001 - 12 * x011 + 6 * x111;
- c = 3 * x011 - 3 * x111;
-
- /*
- * s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a;
- */
- if (fabs (a) < Geom::EPSILON) {
- /* s = -c / b */
- if (fabs (b) > Geom::EPSILON) {
- double s, t, xttt;
- s = -c / b;
- if ((s > 0.0) && (s < 1.0)) {
- t = 1.0 - s;
- xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;
- bbox[0].extendTo(xttt);
- }
- }
- } else {
- /* s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a; */
- D = b * b - 4 * a * c;
- if (D >= 0.0) {
- Geom::Coord d, s, t, xttt;
- /* Have solution */
- d = sqrt (D);
- s = (-b + d) / (2 * a);
- if ((s > 0.0) && (s < 1.0)) {
- t = 1.0 - s;
- xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;
- bbox[0].extendTo(xttt);
+ if (!containsXrange) {
+ a = 3 * x000 - 9 * x001 + 9 * x011 - 3 * x111;
+ b = 6 * x001 - 12 * x011 + 6 * x111;
+ c = 3 * x011 - 3 * x111;
+
+ /*
+ * s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a;
+ */
+ if (fabs (a) < Geom::EPSILON) {
+ /* s = -c / b */
+ if (fabs (b) > Geom::EPSILON) {
+ double s, t, xttt;
+ s = -c / b;
+ if ((s > 0.0) && (s < 1.0)) {
+ t = 1.0 - s;
+ xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;
+ bbox[0].extendTo(xttt);
+ }
}
- s = (-b - d) / (2 * a);
- if ((s > 0.0) && (s < 1.0)) {
- t = 1.0 - s;
- xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;
- bbox[0].extendTo(xttt);
+ } else {
+ /* s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a; */
+ D = b * b - 4 * a * c;
+ if (D >= 0.0) {
+ Geom::Coord d, s, t, xttt;
+ /* Have solution */
+ d = sqrt (D);
+ s = (-b + d) / (2 * a);
+ if ((s > 0.0) && (s < 1.0)) {
+ t = 1.0 - s;
+ xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;
+ bbox[0].extendTo(xttt);
+ }
+ s = (-b - d) / (2 * a);
+ if ((s > 0.0) && (s < 1.0)) {
+ t = 1.0 - s;
+ xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;
+ bbox[0].extendTo(xttt);
+ }
}
}
}
- a = 3 * y000 - 9 * y001 + 9 * y011 - 3 * y111;
- b = 6 * y001 - 12 * y011 + 6 * y111;
- c = 3 * y011 - 3 * y111;
-
- if (fabs (a) < Geom::EPSILON) {
- /* s = -c / b */
- if (fabs (b) > Geom::EPSILON) {
- double s, t, yttt;
- s = -c / b;
- if ((s > 0.0) && (s < 1.0)) {
- t = 1.0 - s;
- yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;
- bbox[1].extendTo(yttt);
- }
- }
- } else {
- /* s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a; */
- D = b * b - 4 * a * c;
- if (D >= 0.0) {
- Geom::Coord d, s, t, yttt;
- /* Have solution */
- d = sqrt (D);
- s = (-b + d) / (2 * a);
- if ((s > 0.0) && (s < 1.0)) {
- t = 1.0 - s;
- yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;
- bbox[1].extendTo(yttt);
+ if (!containsYrange) {
+ a = 3 * y000 - 9 * y001 + 9 * y011 - 3 * y111;
+ b = 6 * y001 - 12 * y011 + 6 * y111;
+ c = 3 * y011 - 3 * y111;
+
+ if (fabs (a) < Geom::EPSILON) {
+ /* s = -c / b */
+ if (fabs (b) > Geom::EPSILON) {
+ double s, t, yttt;
+ s = -c / b;
+ if ((s > 0.0) && (s < 1.0)) {
+ t = 1.0 - s;
+ yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;
+ bbox[1].extendTo(yttt);
+ }
}
- s = (-b - d) / (2 * a);
- if ((s > 0.0) && (s < 1.0)) {
- t = 1.0 - s;
- yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;
- bbox[1].extendTo(yttt);
+ } else {
+ /* s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a; */
+ D = b * b - 4 * a * c;
+ if (D >= 0.0) {
+ Geom::Coord d, s, t, yttt;
+ /* Have solution */
+ d = sqrt (D);
+ s = (-b + d) / (2 * a);
+ if ((s > 0.0) && (s < 1.0)) {
+ t = 1.0 - s;
+ yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;
+ bbox[1].extendTo(yttt);
+ }
+ s = (-b - d) / (2 * a);
+ if ((s > 0.0) && (s < 1.0)) {
+ t = 1.0 - s;
+ yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;
+ bbox[1].extendTo(yttt);
+ }
}
}
}
}
-Geom::Rect
+Geom::OptRect
bounds_fast_transformed(Geom::PathVector const & pv, Geom::Matrix const & t)
{
return bounds_exact_transformed(pv, t); //use this as it is faster for now! :)
// return Geom::bounds_fast(pv * t);
}
-Geom::Rect
+Geom::OptRect
bounds_exact_transformed(Geom::PathVector const & pv, Geom::Matrix const & t)
{
- Geom::Rect bbox;
-
if (pv.empty())
- return bbox;
+ return Geom::OptRect();
Geom::Point initial = pv.front().initialPoint() * t;
- bbox = Geom::Rect(initial, initial); // obtain well defined bbox as starting point to unionWith
+ Geom::Rect bbox(initial, initial); // obtain well defined bbox as starting point to unionWith
for (Geom::PathVector::const_iterator it = pv.begin(); it != pv.end(); ++it) {
bbox.expandTo(it->initialPoint() * t);
for (Geom::Path::const_iterator cit = it->begin(); cit != it->end_open(); ++cit) {
Geom::Curve const &c = *cit;
- if( dynamic_cast<Geom::LineSegment const*>(&c) ||
- dynamic_cast<Geom::HLineSegment const*>(&c) ||
- dynamic_cast<Geom::VLineSegment const*>(&c) )
+ if( is_straight_curve(c) )
{
bbox.expandTo( c.finalPoint() * t );
}
Geom::Coord tolerance, Geom::Rect const *viewbox,
Geom::Point &p0) // pass p0 through as it represents the last endpoint added (the finalPoint of last curve)
{
- if( dynamic_cast<Geom::LineSegment const*>(&c) ||
- dynamic_cast<Geom::HLineSegment const*>(&c) ||
- dynamic_cast<Geom::VLineSegment const*>(&c) )
+ if( is_straight_curve(c) )
{
Geom::Point pe = c.finalPoint() * m;
if (bbox) {
@@ -451,38 +459,78 @@ pathv_matrix_point_bbox_wind_distance (Geom::PathVector const & pathv, Geom::Mat
}
}
-// temporary wrapper
-void
-pathv_matrix_point_bbox_wind_distance (Geom::PathVector const & pathv, NR::Matrix const &m, NR::Point const &pt,
- NR::Rect *bbox, int *wind, NR::Coord *dist,
- NR::Coord tolerance, NR::Rect const *viewbox)
+//#################################################################################
+
+/*
+ * Converts all segments in all paths to Geom::LineSegment or Geom::HLineSegment or
+ * Geom::VLineSegment or Geom::CubicBezier.
+ */
+Geom::PathVector
+pathv_to_linear_and_cubic_beziers( Geom::PathVector const &pathv )
{
- Geom::Rect _bbox;
- if (bbox)
- _bbox = to_2geom(*bbox);
- Geom::Coord _dist;
- if (dist)
- _dist = *dist;
- Geom::Rect _viewbox;
- if (viewbox)
- _viewbox = to_2geom(*viewbox);
-
- pathv_matrix_point_bbox_wind_distance( pathv, to_2geom(m), to_2geom(pt),
- bbox ? &_bbox : NULL,
- wind,
- dist ? &_dist : NULL,
- tolerance,
- viewbox ? &_viewbox : NULL );
-
- if (bbox)
- *bbox = from_2geom(_bbox);
- if (dist)
- *dist = _dist;
+ Geom::PathVector output;
+
+ for (Geom::PathVector::const_iterator pit = pathv.begin(); pit != pathv.end(); ++pit) {
+ output.push_back( Geom::Path() );
+ output.back().start( pit->initialPoint() );
+ output.back().close( pit->closed() );
+
+ for (Geom::Path::const_iterator cit = pit->begin(); cit != pit->end_open(); ++cit) {
+ if( dynamic_cast<Geom::CubicBezier const*>(&*cit) ||
+ is_straight_curve(*cit) )
+ {
+ output.back().append(*cit);
+ }
+ else {
+ // convert all other curve types to cubicbeziers
+ Geom::Path cubicbezier_path = Geom::cubicbezierpath_from_sbasis(cit->toSBasis(), 0.1);
+ output.back().append(cubicbezier_path);
+ }
+ }
+ }
+
+ return output;
+}
+
+
+/**
+ * rounds all corners of the rectangle 'outwards', i.e. x0 and y0 are floored, x1 and y1 are ceiled.
+ */
+void round_rectangle_outwards(Geom::Rect & rect) {
+ Geom::Interval ints[2];
+ for (int i=0; i < 2; i++) {
+ ints[i] = Geom::Interval(std::floor(rect[i][0]), std::ceil(rect[i][1]));
+ }
+ rect = Geom::Rect(ints[0], ints[1]);
}
-//#################################################################################
+namespace Geom {
+bool transform_equalp(Geom::Matrix const &m0, Geom::Matrix const &m1, Geom::Coord const epsilon) {
+ return
+ NR_DF_TEST_CLOSE(m0[0], m1[0], epsilon) &&
+ NR_DF_TEST_CLOSE(m0[1], m1[1], epsilon) &&
+ NR_DF_TEST_CLOSE(m0[2], m1[2], epsilon) &&
+ NR_DF_TEST_CLOSE(m0[3], m1[3], epsilon);
+}
+
+
+bool translate_equalp(Geom::Matrix const &m0, Geom::Matrix const &m1, Geom::Coord const epsilon) {
+ return NR_DF_TEST_CLOSE(m0[4], m1[4], epsilon) && NR_DF_TEST_CLOSE(m0[5], m1[5], epsilon);
+}
+
+
+bool matrix_equalp(Geom::Matrix const &m0, Geom::Matrix const &m1, Geom::Coord const epsilon) {
+ return transform_equalp(m0, m1, epsilon) && translate_equalp(m0, m1, epsilon);
+}
+
+} //end namespace Geom
+/*
+The following predefined objects are for reference
+and comparison.
+*/
+Geom::Matrix GEOM_MATRIX_IDENTITY = Geom::identity();
/*
Local Variables:
@@ -493,4 +541,4 @@ pathv_matrix_point_bbox_wind_distance (Geom::PathVector const & pathv, NR::Matri
fill-column:99
End:
*/
-// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :