Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/bits/bezier.h
changeset 2207 75a29ac69c19
parent 2178 0d7c0f96a5ee
child 2391 14a343be7a5a
equal deleted inserted replaced
0:83687c6e27ef 1:11ecfa51c3da 
    25 ///
 
    25 ///
 
    26 ///Up to now this file is used internally by \ref graph_to_eps.h
 
    26 ///Up to now this file is used internally by \ref graph_to_eps.h
 
    27 ///
 
    27 ///
 
    28 ///\author Alpar Juttner
 
    28 ///\author Alpar Juttner
 
    29 
    29 
    30 #include<lemon/xy.h>
 
    30 #include<lemon/dim2.h>
 
    31 
    31 
    32 namespace lemon {
 
    32 namespace lemon {
 
       
    33   namespace dim2 {
 
    33 
    34 
    34 class BezierBase {
 
    35 class BezierBase {
 
    35 public:
 
    36 public:
 
    36   typedef xy<double> xy;
 
    37   typedef Point<double> Point;
 
    37 protected:
 
    38 protected:
 
    38   static xy conv(xy x,xy y,double t) {return (1-t)*x+t*y;}
 
    39   static Point conv(Point x,Point y,double t) {return (1-t)*x+t*y;}
 
    39 };
 
    40 };
 
    40 
    41 
    41 class Bezier1 : public BezierBase
 
    42 class Bezier1 : public BezierBase
 
    42 {
 
    43 {
 
    43 public:
 
    44 public:
 
    44   xy p1,p2;
 
    45   Point p1,p2;
 
    45 
    46 
    46   Bezier1() {}
 
    47   Bezier1() {}
 
    47   Bezier1(xy _p1, xy _p2) :p1(_p1), p2(_p2) {}
 
    48   Bezier1(Point _p1, Point _p2) :p1(_p1), p2(_p2) {}
 
    48   
    49   
    49   xy operator()(double t) const
 
    50   Point operator()(double t) const
 
    50   {
 
    51   {
 
    51     //    return conv(conv(p1,p2,t),conv(p2,p3,t),t);
 
    52     //    return conv(conv(p1,p2,t),conv(p2,p3,t),t);
 
    52     return conv(p1,p2,t);
 
    53     return conv(p1,p2,t);
 
    53   }
 
    54   }
 
    54   Bezier1 before(double t) const
 
    55   Bezier1 before(double t) const
 
    61     return Bezier1(conv(p1,p2,t),p2);
 
    62     return Bezier1(conv(p1,p2,t),p2);
 
    62   }
 
    63   }
 
    63 
    64 
    64   Bezier1 revert() const { return Bezier1(p2,p1);}
 
    65   Bezier1 revert() const { return Bezier1(p2,p1);}
 
    65   Bezier1 operator()(double a,double b) const { return before(b).after(a/b); }
 
    66   Bezier1 operator()(double a,double b) const { return before(b).after(a/b); }
 
    66   xy grad() const { return p2-p1; }
 
    67   Point grad() const { return p2-p1; }
 
    67   xy norm() const { return rot90(p2-p1); }
 
    68   Point norm() const { return rot90(p2-p1); }
 
    68   xy grad(double) const { return grad(); }
 
    69   Point grad(double) const { return grad(); }
 
    69   xy norm(double t) const { return rot90(grad(t)); }
 
    70   Point norm(double t) const { return rot90(grad(t)); }
 
    70 };
 
    71 };
 
    71 
    72 
    72 class Bezier2 : public BezierBase
 
    73 class Bezier2 : public BezierBase
 
    73 {
 
    74 {
 
    74 public:
 
    75 public:
 
    75   xy p1,p2,p3;
 
    76   Point p1,p2,p3;
 
    76 
    77 
    77   Bezier2() {}
 
    78   Bezier2() {}
 
    78   Bezier2(xy _p1, xy _p2, xy _p3) :p1(_p1), p2(_p2), p3(_p3) {}
 
    79   Bezier2(Point _p1, Point _p2, Point _p3) :p1(_p1), p2(_p2), p3(_p3) {}
 
    79   Bezier2(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,.5)), p3(b.p2) {}
 
    80   Bezier2(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,.5)), p3(b.p2) {}
 
    80   xy operator()(double t) const
 
    81   Point operator()(double t) const
 
    81   {
 
    82   {
 
    82     //    return conv(conv(p1,p2,t),conv(p2,p3,t),t);
 
    83     //    return conv(conv(p1,p2,t),conv(p2,p3,t),t);
 
    83     return ((1-t)*(1-t))*p1+(2*(1-t)*t)*p2+(t*t)*p3;
 
    84     return ((1-t)*(1-t))*p1+(2*(1-t)*t)*p2+(t*t)*p3;
 
    84   }
 
    85   }
 
    85   Bezier2 before(double t) const
 
    86   Bezier2 before(double t) const
 
    86   {
 
    87   {
 
    87     xy q(conv(p1,p2,t));
 
    88     Point q(conv(p1,p2,t));
 
    88     xy r(conv(p2,p3,t));
 
    89     Point r(conv(p2,p3,t));
 
    89     return Bezier2(p1,q,conv(q,r,t));
 
    90     return Bezier2(p1,q,conv(q,r,t));
 
    90   }
 
    91   }
 
    91   
    92   
    92   Bezier2 after(double t) const
 
    93   Bezier2 after(double t) const
 
    93   {
 
    94   {
 
    94     xy q(conv(p1,p2,t));
 
    95     Point q(conv(p1,p2,t));
 
    95     xy r(conv(p2,p3,t));
 
    96     Point r(conv(p2,p3,t));
 
    96     return Bezier2(conv(q,r,t),r,p3);
 
    97     return Bezier2(conv(q,r,t),r,p3);
 
    97   }
 
    98   }
 
    98   Bezier2 revert() const { return Bezier2(p3,p2,p1);}
 
    99   Bezier2 revert() const { return Bezier2(p3,p2,p1);}
 
    99   Bezier2 operator()(double a,double b) const { return before(b).after(a/b); }
 
   100   Bezier2 operator()(double a,double b) const { return before(b).after(a/b); }
 
   100   Bezier1 grad() const { return Bezier1(2.0*(p2-p1),2.0*(p3-p2)); }
 
   101   Bezier1 grad() const { return Bezier1(2.0*(p2-p1),2.0*(p3-p2)); }
 
   101   Bezier1 norm() const { return Bezier1(2.0*rot90(p2-p1),2.0*rot90(p3-p2)); }
 
   102   Bezier1 norm() const { return Bezier1(2.0*rot90(p2-p1),2.0*rot90(p3-p2)); }
 
   102   xy grad(double t) const { return grad()(t); }
 
   103   Point grad(double t) const { return grad()(t); }
 
   103   xy norm(double t) const { return rot90(grad(t)); }
 
   104   Point norm(double t) const { return rot90(grad(t)); }
 
   104 };
 
   105 };
 
   105 
   106 
   106 class Bezier3 : public BezierBase
 
   107 class Bezier3 : public BezierBase
 
   107 {
 
   108 {
 
   108 public:
 
   109 public:
 
   109   xy p1,p2,p3,p4;
 
   110   Point p1,p2,p3,p4;
 
   110 
   111 
   111   Bezier3() {}
 
   112   Bezier3() {}
 
   112   Bezier3(xy _p1, xy _p2, xy _p3, xy _p4) :p1(_p1), p2(_p2), p3(_p3), p4(_p4) {}
 
   113   Bezier3(Point _p1, Point _p2, Point _p3, Point _p4)
 
       
   114     : p1(_p1), p2(_p2), p3(_p3), p4(_p4) {}
 
   113   Bezier3(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,1.0/3.0)), 
   115   Bezier3(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,1.0/3.0)), 
   114 			      p3(conv(b.p1,b.p2,2.0/3.0)), p4(b.p2) {}
 
   116 			      p3(conv(b.p1,b.p2,2.0/3.0)), p4(b.p2) {}
 
   115   Bezier3(const Bezier2 &b) : p1(b.p1), p2(conv(b.p1,b.p2,2.0/3.0)),
 
   117   Bezier3(const Bezier2 &b) : p1(b.p1), p2(conv(b.p1,b.p2,2.0/3.0)),
 
   116 			      p3(conv(b.p2,b.p3,1.0/3.0)), p4(b.p3) {}
 
   118 			      p3(conv(b.p2,b.p3,1.0/3.0)), p4(b.p3) {}
 
   117   
   119   
   118   xy operator()(double t) const 
   120   Point operator()(double t) const 
   119     {
 
   121     {
 
   120       //    return Bezier2(conv(p1,p2,t),conv(p2,p3,t),conv(p3,p4,t))(t);
 
   122       //    return Bezier2(conv(p1,p2,t),conv(p2,p3,t),conv(p3,p4,t))(t);
 
   121       return ((1-t)*(1-t)*(1-t))*p1+(3*t*(1-t)*(1-t))*p2+
 
   123       return ((1-t)*(1-t)*(1-t))*p1+(3*t*(1-t)*(1-t))*p2+
 
   122 	(3*t*t*(1-t))*p3+(t*t*t)*p4;
 
   124 	(3*t*t*(1-t))*p3+(t*t*t)*p4;
 
   123     }
 
   125     }
 
   124   Bezier3 before(double t) const
 
   126   Bezier3 before(double t) const
 
   125     {
 
   127     {
 
   126       xy p(conv(p1,p2,t));
 
   128       Point p(conv(p1,p2,t));
 
   127       xy q(conv(p2,p3,t));
 
   129       Point q(conv(p2,p3,t));
 
   128       xy r(conv(p3,p4,t));
 
   130       Point r(conv(p3,p4,t));
 
   129       xy a(conv(p,q,t));
 
   131       Point a(conv(p,q,t));
 
   130       xy b(conv(q,r,t));
 
   132       Point b(conv(q,r,t));
 
   131       xy c(conv(a,b,t));
 
   133       Point c(conv(a,b,t));
 
   132       return Bezier3(p1,p,a,c);
 
   134       return Bezier3(p1,p,a,c);
 
   133     }
 
   135     }
 
   134   
   136   
   135   Bezier3 after(double t) const
 
   137   Bezier3 after(double t) const
 
   136     {
 
   138     {
 
   137       xy p(conv(p1,p2,t));
 
   139       Point p(conv(p1,p2,t));
 
   138       xy q(conv(p2,p3,t));
 
   140       Point q(conv(p2,p3,t));
 
   139       xy r(conv(p3,p4,t));
 
   141       Point r(conv(p3,p4,t));
 
   140       xy a(conv(p,q,t));
 
   142       Point a(conv(p,q,t));
 
   141       xy b(conv(q,r,t));
 
   143       Point b(conv(q,r,t));
 
   142       xy c(conv(a,b,t));
 
   144       Point c(conv(a,b,t));
 
   143       return Bezier3(c,b,r,p4);
 
   145       return Bezier3(c,b,r,p4);
 
   144     }
 
   146     }
 
   145   Bezier3 revert() const { return Bezier3(p4,p3,p2,p1);}
 
   147   Bezier3 revert() const { return Bezier3(p4,p3,p2,p1);}
 
   146   Bezier3 operator()(double a,double b) const { return before(b).after(a/b); }
 
   148   Bezier3 operator()(double a,double b) const { return before(b).after(a/b); }
 
   147   Bezier2 grad() const { return Bezier2(3.0*(p2-p1),3.0*(p3-p2),3.0*(p4-p3)); }
 
   149   Bezier2 grad() const { return Bezier2(3.0*(p2-p1),3.0*(p3-p2),3.0*(p4-p3)); }
 
   148   Bezier2 norm() const { return Bezier2(3.0*rot90(p2-p1),
 
   150   Bezier2 norm() const { return Bezier2(3.0*rot90(p2-p1),
 
   149 				  3.0*rot90(p3-p2),
 
   151 				  3.0*rot90(p3-p2),
 
   150 				  3.0*rot90(p4-p3)); }
 
   152 				  3.0*rot90(p4-p3)); }
 
   151   xy grad(double t) const { return grad()(t); }
 
   153   Point grad(double t) const { return grad()(t); }
 
   152   xy norm(double t) const { return rot90(grad(t)); }
 
   154   Point norm(double t) const { return rot90(grad(t)); }
 
   153 
   155 
   154   template<class R,class F,class S,class D>
 
   156   template<class R,class F,class S,class D>
 
   155   R recSplit(F &_f,const S &_s,D _d) const 
   157   R recSplit(F &_f,const S &_s,D _d) const 
   156   {
 
   158   {
 
   157     const xy a=(p1+p2)/2;
 
   159     const Point a=(p1+p2)/2;
 
   158     const xy b=(p2+p3)/2;
 
   160     const Point b=(p2+p3)/2;
 
   159     const xy c=(p3+p4)/2;
 
   161     const Point c=(p3+p4)/2;
 
   160     const xy d=(a+b)/2;
 
   162     const Point d=(a+b)/2;
 
   161     const xy e=(b+c)/2;
 
   163     const Point e=(b+c)/2;
 
   162     const xy f=(d+e)/2;
 
   164     const Point f=(d+e)/2;
 
   163     R f1=_f(Bezier3(p1,a,d,e),_d);
 
   165     R f1=_f(Bezier3(p1,a,d,e),_d);
 
   164     R f2=_f(Bezier3(e,d,c,p4),_d);
 
   166     R f2=_f(Bezier3(e,d,c,p4),_d);
 
   165     return _s(f1,f2);
 
   167     return _s(f1,f2);
 
   166   }
 
   168   }
 
   167   
   169   
   168 };
 
   170 };
 
   169 
   171 
   170 } //END OF NAMESPACE LEMON
 
   172 
       
   173 } //END OF NAMESPACE dim2
 
       
   174 } //END OF NAMESPACE lemon
 
   171 
   175 
   172 #endif // LEMON_BEZIER_H
 
   176 #endif // LEMON_BEZIER_H
lemon-0.x