lemon/bits/bezier.h
changeset 135 6e7aee618f03
child 157 2ccc1afc2c52
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/lemon/bits/bezier.h	Thu Apr 17 15:54:30 2008 +0100
     1.3 @@ -0,0 +1,176 @@
     1.4 +/* -*- C++ -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library
     1.7 + *
     1.8 + * Copyright (C) 2003-2008
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#ifndef LEMON_BEZIER_H
    1.23 +#define LEMON_BEZIER_H
    1.24 +
    1.25 +///\ingroup misc
    1.26 +///\file
    1.27 +///\brief Classes to compute with Bezier curves.
    1.28 +///
    1.29 +///Up to now this file is used internally by \ref graph_to_eps.h
    1.30 +///
    1.31 +///\author Alpar Juttner
    1.32 +
    1.33 +#include<lemon/dim2.h>
    1.34 +
    1.35 +namespace lemon {
    1.36 +  namespace dim2 {
    1.37 +
    1.38 +class BezierBase {
    1.39 +public:
    1.40 +  typedef Point<double> Point;
    1.41 +protected:
    1.42 +  static Point conv(Point x,Point y,double t) {return (1-t)*x+t*y;}
    1.43 +};
    1.44 +
    1.45 +class Bezier1 : public BezierBase
    1.46 +{
    1.47 +public:
    1.48 +  Point p1,p2;
    1.49 +
    1.50 +  Bezier1() {}
    1.51 +  Bezier1(Point _p1, Point _p2) :p1(_p1), p2(_p2) {}
    1.52 +  
    1.53 +  Point operator()(double t) const
    1.54 +  {
    1.55 +    //    return conv(conv(p1,p2,t),conv(p2,p3,t),t);
    1.56 +    return conv(p1,p2,t);
    1.57 +  }
    1.58 +  Bezier1 before(double t) const
    1.59 +  {
    1.60 +    return Bezier1(p1,conv(p1,p2,t));
    1.61 +  }
    1.62 +  
    1.63 +  Bezier1 after(double t) const
    1.64 +  {
    1.65 +    return Bezier1(conv(p1,p2,t),p2);
    1.66 +  }
    1.67 +
    1.68 +  Bezier1 revert() const { return Bezier1(p2,p1);}
    1.69 +  Bezier1 operator()(double a,double b) const { return before(b).after(a/b); }
    1.70 +  Point grad() const { return p2-p1; }
    1.71 +  Point norm() const { return rot90(p2-p1); }
    1.72 +  Point grad(double) const { return grad(); }
    1.73 +  Point norm(double t) const { return rot90(grad(t)); }
    1.74 +};
    1.75 +
    1.76 +class Bezier2 : public BezierBase
    1.77 +{
    1.78 +public:
    1.79 +  Point p1,p2,p3;
    1.80 +
    1.81 +  Bezier2() {}
    1.82 +  Bezier2(Point _p1, Point _p2, Point _p3) :p1(_p1), p2(_p2), p3(_p3) {}
    1.83 +  Bezier2(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,.5)), p3(b.p2) {}
    1.84 +  Point operator()(double t) const
    1.85 +  {
    1.86 +    //    return conv(conv(p1,p2,t),conv(p2,p3,t),t);
    1.87 +    return ((1-t)*(1-t))*p1+(2*(1-t)*t)*p2+(t*t)*p3;
    1.88 +  }
    1.89 +  Bezier2 before(double t) const
    1.90 +  {
    1.91 +    Point q(conv(p1,p2,t));
    1.92 +    Point r(conv(p2,p3,t));
    1.93 +    return Bezier2(p1,q,conv(q,r,t));
    1.94 +  }
    1.95 +  
    1.96 +  Bezier2 after(double t) const
    1.97 +  {
    1.98 +    Point q(conv(p1,p2,t));
    1.99 +    Point r(conv(p2,p3,t));
   1.100 +    return Bezier2(conv(q,r,t),r,p3);
   1.101 +  }
   1.102 +  Bezier2 revert() const { return Bezier2(p3,p2,p1);}
   1.103 +  Bezier2 operator()(double a,double b) const { return before(b).after(a/b); }
   1.104 +  Bezier1 grad() const { return Bezier1(2.0*(p2-p1),2.0*(p3-p2)); }
   1.105 +  Bezier1 norm() const { return Bezier1(2.0*rot90(p2-p1),2.0*rot90(p3-p2)); }
   1.106 +  Point grad(double t) const { return grad()(t); }
   1.107 +  Point norm(double t) const { return rot90(grad(t)); }
   1.108 +};
   1.109 +
   1.110 +class Bezier3 : public BezierBase
   1.111 +{
   1.112 +public:
   1.113 +  Point p1,p2,p3,p4;
   1.114 +
   1.115 +  Bezier3() {}
   1.116 +  Bezier3(Point _p1, Point _p2, Point _p3, Point _p4)
   1.117 +    : p1(_p1), p2(_p2), p3(_p3), p4(_p4) {}
   1.118 +  Bezier3(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,1.0/3.0)), 
   1.119 +			      p3(conv(b.p1,b.p2,2.0/3.0)), p4(b.p2) {}
   1.120 +  Bezier3(const Bezier2 &b) : p1(b.p1), p2(conv(b.p1,b.p2,2.0/3.0)),
   1.121 +			      p3(conv(b.p2,b.p3,1.0/3.0)), p4(b.p3) {}
   1.122 +  
   1.123 +  Point operator()(double t) const 
   1.124 +    {
   1.125 +      //    return Bezier2(conv(p1,p2,t),conv(p2,p3,t),conv(p3,p4,t))(t);
   1.126 +      return ((1-t)*(1-t)*(1-t))*p1+(3*t*(1-t)*(1-t))*p2+
   1.127 +	(3*t*t*(1-t))*p3+(t*t*t)*p4;
   1.128 +    }
   1.129 +  Bezier3 before(double t) const
   1.130 +    {
   1.131 +      Point p(conv(p1,p2,t));
   1.132 +      Point q(conv(p2,p3,t));
   1.133 +      Point r(conv(p3,p4,t));
   1.134 +      Point a(conv(p,q,t));
   1.135 +      Point b(conv(q,r,t));
   1.136 +      Point c(conv(a,b,t));
   1.137 +      return Bezier3(p1,p,a,c);
   1.138 +    }
   1.139 +  
   1.140 +  Bezier3 after(double t) const
   1.141 +    {
   1.142 +      Point p(conv(p1,p2,t));
   1.143 +      Point q(conv(p2,p3,t));
   1.144 +      Point r(conv(p3,p4,t));
   1.145 +      Point a(conv(p,q,t));
   1.146 +      Point b(conv(q,r,t));
   1.147 +      Point c(conv(a,b,t));
   1.148 +      return Bezier3(c,b,r,p4);
   1.149 +    }
   1.150 +  Bezier3 revert() const { return Bezier3(p4,p3,p2,p1);}
   1.151 +  Bezier3 operator()(double a,double b) const { return before(b).after(a/b); }
   1.152 +  Bezier2 grad() const { return Bezier2(3.0*(p2-p1),3.0*(p3-p2),3.0*(p4-p3)); }
   1.153 +  Bezier2 norm() const { return Bezier2(3.0*rot90(p2-p1),
   1.154 +				  3.0*rot90(p3-p2),
   1.155 +				  3.0*rot90(p4-p3)); }
   1.156 +  Point grad(double t) const { return grad()(t); }
   1.157 +  Point norm(double t) const { return rot90(grad(t)); }
   1.158 +
   1.159 +  template<class R,class F,class S,class D>
   1.160 +  R recSplit(F &_f,const S &_s,D _d) const 
   1.161 +  {
   1.162 +    const Point a=(p1+p2)/2;
   1.163 +    const Point b=(p2+p3)/2;
   1.164 +    const Point c=(p3+p4)/2;
   1.165 +    const Point d=(a+b)/2;
   1.166 +    const Point e=(b+c)/2;
   1.167 +    const Point f=(d+e)/2;
   1.168 +    R f1=_f(Bezier3(p1,a,d,e),_d);
   1.169 +    R f2=_f(Bezier3(e,d,c,p4),_d);
   1.170 +    return _s(f1,f2);
   1.171 +  }
   1.172 +  
   1.173 +};
   1.174 +
   1.175 +
   1.176 +} //END OF NAMESPACE dim2
   1.177 +} //END OF NAMESPACE lemon
   1.178 +
   1.179 +#endif // LEMON_BEZIER_H