src/2geom/sbasis-curve.h

01d27eab5fca2dcb8e883011f8be77ae6b78a11cTed Gould/**
01d27eab5fca2dcb8e883011f8be77ae6b78a11cTed Gould * \file
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen * \brief Symmetric power basis curve
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen *//*
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * Authors:
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen *   MenTaLguY <mental@rydia.net>
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen *   Marco Cecchetti <mrcekets at gmail.com>
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen *   Krzysztof Kosiński <tweenk.pl@gmail.com>
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti *
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen * Copyright 2007-2009 Authors
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti *
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * This library is free software; you can redistribute it and/or
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * modify it either under the terms of the GNU Lesser General Public
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * License version 2.1 as published by the Free Software Foundation
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * (the "LGPL") or, at your option, under the terms of the Mozilla
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * Public License Version 1.1 (the "MPL"). If you do not alter this
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * notice, a recipient may use your version of this file under either
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * the MPL or the LGPL.
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti *
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * You should have received a copy of the LGPL along with this library
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * in the file COPYING-LGPL-2.1; if not, write to the Free Software
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * You should have received a copy of the MPL along with this library
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * in the file COPYING-MPL-1.1
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti *
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * The contents of this file are subject to the Mozilla Public License
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * Version 1.1 (the "License"); you may not use this file except in
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * compliance with the License. You may obtain a copy of the License at
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * http://www.mozilla.org/MPL/
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti *
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * OF ANY KIND, either express or implied. See the LGPL or the MPL for
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * the specific language governing rights and limitations.
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti */
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński#ifndef LIB2GEOM_SEEN_SBASIS_CURVE_H
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński#define LIB2GEOM_SEEN_SBASIS_CURVE_H
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti
8001ba81cb851b38d86650a2fef5817facffb763johanengelen#include <2geom/curve.h>
a16a494f042310ee849a6f717ffea70846f1f22cKrzysztof Kosiński#include <2geom/exception.h>
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#include <2geom/nearest-time.h>
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen#include <2geom/sbasis-geometric.h>
c9cce6b7800659b3bd0e56b5d7e1f7c1b29272fbJohan B. C. Engelen#include <2geom/transforms.h>
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti
6e16a663ee96cd1329e48518138efb415046d9f6mcecchettinamespace Geom
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti{
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen/** @brief Symmetric power basis curve.
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen *
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * Symmetric power basis (S-basis for short) polynomials are a versatile numeric
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * representation of arbitrary continuous curves. They are the main representation of curves
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen * in 2Geom.
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen *
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * S-basis is defined for odd degrees and composed of the following polynomials:
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * \f{align*}{
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński         P_k^0(t) &= t^k (1-t)^{k+1} \\
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński         P_k^1(t) &= t^{k+1} (1-t)^k \f}
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * This can be understood more easily with the help of the chart below. Each square
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * represents a product of a specific number of \f$t\f$ and \f$(1-t)\f$ terms. Red dots
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * are the canonical (monomial) basis, the green dots are the Bezier basis, and the blue
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * dots are the S-basis, all of them of degree 7.
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński *
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * @image html sbasis.png "Illustration of the monomial, Bezier and symmetric power bases"
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński *
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * The S-Basis has several important properties:
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * - S-basis polynomials are closed under multiplication.
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * - Evaluation is fast, using a modified Horner scheme.
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * - Degree change is as trivial as in the monomial basis. To elevate, just add extra
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński *   zero coefficients. To reduce the degree, truncate the terms in the highest powers.
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński *   Compare this with Bezier curves, where degree change is complicated.
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * - Conversion between S-basis and Bezier basis is numerically stable.
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński *
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * More in-depth information can be found in the following paper:
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * J Sanchez-Reyes, "The symmetric analogue of the polynomial power basis".
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * ACM Transactions on Graphics, Vol. 16, No. 3, July 1997, pages 319--357.
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * http://portal.acm.org/citation.cfm?id=256162
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński *
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen * @ingroup Curves
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen */
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetticlass SBasisCurve : public Curve {
6e16a663ee96cd1329e48518138efb415046d9f6mcecchettiprivate:
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    D2<SBasis> inner;
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti
6e16a663ee96cd1329e48518138efb415046d9f6mcecchettipublic:
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    explicit SBasisCurve(D2<SBasis> const &sb) : inner(sb) {}
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    explicit SBasisCurve(Curve const &other) : inner(other.toSBasis()) {}
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual Curve *duplicate() const { return new SBasisCurve(*this); }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual Point initialPoint() const    { return inner.at0(); }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual Point finalPoint() const      { return inner.at1(); }
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński    virtual bool isDegenerate() const     { return inner.isConstant(0); }
00f9ca0b3aa57e09f3c3f3632c5427fc03499df5Krzysztof Kosiński    virtual bool isLineSegment() const    { return inner[X].size() == 1; }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual Point pointAt(Coord t) const  { return inner.valueAt(t); }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const {
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen        return inner.valueAndDerivatives(t, n);
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual Coord valueAt(Coord t, Dim2 d) const { return inner[d].valueAt(t); }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual void setInitial(Point const &v) {
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen        for (unsigned d = 0; d < 2; d++) { inner[d][0][0] = v[d]; }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual void setFinal(Point const &v) {
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen        for (unsigned d = 0; d < 2; d++) { inner[d][0][1] = v[d]; }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual Rect boundsFast() const  { return *bounds_fast(inner); }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual Rect boundsExact() const { return *bounds_exact(inner); }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual OptRect boundsLocal(OptInterval const &i, unsigned deg) const {
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen        return bounds_local(inner, i, deg);
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual std::vector<Coord> roots(Coord v, Dim2 d) const { return Geom::roots(inner[d] - v); }
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński    virtual Coord nearestTime( Point const& p, Coord from = 0, Coord to = 1 ) const {
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński        return nearest_time(p, inner, from, to);
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    }
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński    virtual std::vector<Coord> allNearestTimes( Point const& p, Coord from = 0,
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen        Coord to = 1 ) const
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    {
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński        return all_nearest_times(p, inner, from, to);
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual Coord length(Coord tolerance) const { return ::Geom::length(inner, tolerance); }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual Curve *portion(Coord f, Coord t) const {
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen        return new SBasisCurve(Geom::portion(inner, f, t));
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    }
c9cce6b7800659b3bd0e56b5d7e1f7c1b29272fbJohan B. C. Engelen
e4369b05aaa20df73a37f4d319ce456865cc74f3Krzysztof Kosiński    using Curve::operator*=;
e4369b05aaa20df73a37f4d319ce456865cc74f3Krzysztof Kosiński    virtual void operator*=(Affine const &m) { inner = inner * m; }
c9cce6b7800659b3bd0e56b5d7e1f7c1b29272fbJohan B. C. Engelen
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual Curve *derivative() const {
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen        return new SBasisCurve(Geom::derivative(inner));
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual D2<SBasis> toSBasis() const { return inner; }
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński    virtual bool operator==(Curve const &c) const {
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński        SBasisCurve const *other = dynamic_cast<SBasisCurve const *>(&c);
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński        if (!other) return false;
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński        return inner == other->inner;
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński    }
a16a494f042310ee849a6f717ffea70846f1f22cKrzysztof Kosiński    virtual bool isNear(Curve const &/*c*/, Coord /*eps*/) const {
a16a494f042310ee849a6f717ffea70846f1f22cKrzysztof Kosiński        THROW_NOTIMPLEMENTED();
a16a494f042310ee849a6f717ffea70846f1f22cKrzysztof Kosiński        return false;
a16a494f042310ee849a6f717ffea70846f1f22cKrzysztof Kosiński    }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    virtual int degreesOfFreedom() const {
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen        return inner[0].degreesOfFreedom() + inner[1].degreesOfFreedom();
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen    }
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti};
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti} // end namespace Geom
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński#endif // LIB2GEOM_SEEN_SBASIS_CURVE_H
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti/*
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti  Local Variables:
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti  mode:c++
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti  c-file-style:"stroustrup"
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti  indent-tabs-mode:nil
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti  fill-column:99
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti  End:
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti*/
a4030d5ca449e7e384bc699cd249ee704faaeab0Chris Morgan// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :