00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035 #ifndef __VCGLIB_INTERSECTION_2
00036 #define __VCGLIB_INTERSECTION_2
00037 #include <vcg/space/line2.h>
00038 #include <vcg/space/ray2.h>
00039 #include <vcg/space/segment2.h>
00040 #include <vcg/space/point2.h>
00041 #include <vcg/space/triangle2.h>
00042 #include <vcg/space/box2.h>
00043
00044
00045
00046
00047 namespace vcg {
00055
00056 template<class SCALAR_TYPE>
00057 inline bool Convex(const Point2<SCALAR_TYPE> & p0,const Point2<SCALAR_TYPE> & p1,const Point2<SCALAR_TYPE> & p2)
00058 {
00059 const SCALAR_TYPE EPS= SCALAR_TYPE(1e-8);
00060 return (((p0-p1)^(p2-p1))<=EPS);
00061 }
00062
00065 template<class SCALAR_TYPE>
00066 inline bool LineLineIntersection(const vcg::Line2<SCALAR_TYPE> & l0,
00067 const vcg::Line2<SCALAR_TYPE> & l1,
00068 Point2<SCALAR_TYPE> &p)
00069 {
00070 const SCALAR_TYPE Eps= SCALAR_TYPE(1e-8);
00072 SCALAR_TYPE x1=l0.Origin().X();
00073 SCALAR_TYPE y1=l0.Origin().Y();
00074 SCALAR_TYPE x2=x1+l0.Direction().X();
00075 SCALAR_TYPE y2=y1+l0.Direction().Y();
00076
00078 SCALAR_TYPE x3=l1.Origin().X();
00079 SCALAR_TYPE y3=l1.Origin().Y();
00080 SCALAR_TYPE x4=x3+l1.Direction().X();
00081 SCALAR_TYPE y4=y3+l1.Direction().Y();
00082
00084
00086 SCALAR_TYPE den=((x1-x2)*(y3-y4))-((y1-y2)*(x3-x4));
00087 if (fabs(den)<Eps)
00088 return false;
00089
00090 SCALAR_TYPE d0=(x1*y2)-(y1*x2);
00091 SCALAR_TYPE d1=(x3*y4)-(y3*x4);
00092 SCALAR_TYPE numx=(d0*(x3-x4))-(d1*(x1-x2));
00093 SCALAR_TYPE numy=(d0*(y3-y4))-(d1*(y1-y2));
00094
00095 p.X()=numx/den;
00096 p.Y()=numy/den;
00097 return true;
00098 }
00099
00102 template<class SCALAR_TYPE>
00103 inline bool RayLineIntersection(const vcg::Line2<SCALAR_TYPE> & l,
00104 const vcg::Ray2<SCALAR_TYPE> & r,
00105 Point2<SCALAR_TYPE> &p)
00106 {
00108 vcg::Line2<SCALAR_TYPE> l_test;
00109 l_test.Set(r.Origin(),r.Direction());
00110 if (!LineLineIntersection(l,l_test,p))
00111 return false;
00112 Point2<SCALAR_TYPE> dir=p-r.Origin();
00113 dir.Normalize();
00114 return (dir*r.Direction()>0);
00115 }
00116
00117
00119 template<class SCALAR_TYPE>
00120 inline bool RaySegmentIntersection(const vcg::Ray2<SCALAR_TYPE> & r,
00121 const vcg::Segment2<SCALAR_TYPE> &seg,
00122 Point2<SCALAR_TYPE> &p_inters)
00123 {
00125 vcg::Line2<SCALAR_TYPE> line2;
00126 line2.SetOrigin(seg.P0());
00127 vcg::Point2<SCALAR_TYPE> dir=seg.P1()-seg.P0();
00128 dir.Normalize();
00129 line2.SetDirection(dir);
00130 if(!RayLineIntersection<SCALAR_TYPE>(line2,r,p_inters))
00131 return false;
00134 SCALAR_TYPE d0=(seg.P1()-p_inters).Norm();
00135 SCALAR_TYPE d1=(seg.P0()-p_inters).Norm();
00136 SCALAR_TYPE lenght=(seg.P0()-seg.P1()).Norm();
00137 return ((d0<lenght)&&(d1<lenght));
00138 }
00139
00141 template<class SCALAR_TYPE>
00142 inline bool LineSegmentIntersection(const vcg::Line2<SCALAR_TYPE> & line,
00143 const vcg::Segment2<SCALAR_TYPE> &seg,
00144 Point2<SCALAR_TYPE> &p_inters)
00145 {
00147 vcg::Line2<SCALAR_TYPE> line2;
00148 line2.SetOrigin(seg.P0());
00149 vcg::Point2<SCALAR_TYPE> dir=seg.P1()-seg.P0();
00150 dir.Normalize();
00151 line2.SetDirection(dir);
00152 if(!LineLineIntersection(line,line2,p_inters))
00153 return false;
00156 SCALAR_TYPE d0=(seg.P1()-p_inters).Norm();
00157 SCALAR_TYPE d1=(seg.P0()-p_inters).Norm();
00158 SCALAR_TYPE lenght=(seg.P0()-seg.P1()).Norm();
00159 return ((d0<lenght)&&(d1<lenght));
00160 }
00161
00163 template<class SCALAR_TYPE>
00164 inline bool SegmentSegmentIntersection(const vcg::Segment2<SCALAR_TYPE> &seg0,
00165 const vcg::Segment2<SCALAR_TYPE> &seg1,
00166 Point2<SCALAR_TYPE> &p_inters)
00167 {
00168 vcg::Line2<SCALAR_TYPE> l0,l1;
00169
00170 l0.SetOrigin(seg0.P0());
00171 vcg::Point2<SCALAR_TYPE> dir0=seg0.P1()-seg0.P0();
00172 dir0.Normalize();
00173 l0.SetDirection(dir0);
00174
00175 l1.SetOrigin(seg1.P0());
00176 vcg::Point2<SCALAR_TYPE> dir1=seg1.P1()-seg1.P0();
00177 dir1.Normalize();
00178 l1.SetDirection(dir1);
00179 LineLineIntersection(l0,l1,p_inters);
00180 SCALAR_TYPE len0=seg0.Length();
00181 SCALAR_TYPE len1=seg1.Length();
00182 SCALAR_TYPE d0=(seg0.P0()-p_inters).Norm();
00183 SCALAR_TYPE d1=(seg1.P0()-p_inters).Norm();
00184
00185 if ((d0>len0)||(d1>len1))
00186 return false;
00187
00188 vcg::Point2<SCALAR_TYPE> dir2=p_inters-seg0.P0();
00189 vcg::Point2<SCALAR_TYPE> dir3=p_inters-seg1.P0();
00190 if (((dir2*dir0)<0)||((dir3*dir1)<0))
00191 return false;
00192
00193 return true;
00194
00195 }
00197 template<class SCALAR_TYPE>
00198 inline bool IsInsideTrianglePoint( const Triangle2<SCALAR_TYPE> & t,const Point2<SCALAR_TYPE> & p)
00199 {
00200 Point2<SCALAR_TYPE> p0=t.P0(0);
00201 Point2<SCALAR_TYPE> p1=t.P0(1);
00202 Point2<SCALAR_TYPE> p2=t.P0(2);
00203
00205 vcg::Box2<SCALAR_TYPE> b2d;
00206 b2d.Add(p0);
00207 b2d.Add(p1);
00208 b2d.Add(p2);
00209 if (!b2d.IsIn(p))
00210 return false;
00211
00213 if (!Convex(p0,p1,p2))
00214 std::swap<Point2<SCALAR_TYPE> >(p1,p2);
00215 return((Convex(p,p0,p1))&&(Convex(p,p1,p2))&&(Convex(p,p2,p0)));
00216
00217 }
00218
00219
00220 template<class ScalarType>
00221 inline bool CircleLineIntersection(const vcg::Line2<ScalarType> & line,
00222 const vcg::Point2<ScalarType> ¢er,
00223 const ScalarType &radius,
00224 vcg::Point2<ScalarType> &p0,
00225 vcg::Point2<ScalarType> &p1)
00226 {
00228 ScalarType x1,x2,y1,y2;
00229 x1=line.Origin().X()-center.X();
00230 y1=line.Origin().Y()-center.Y();
00231 x2=x1+line.Direction().X();
00232 y2=y1+line.Direction().Y();
00233
00234 ScalarType dx,dy,dr,D,delta,sign;
00235 dx=x2-x1;
00236 dy=y2-y1;
00237 dr=sqrt(dx*dx+dy*dy);
00238 D=x1*y2-x2*y1;
00239 delta=radius*radius*dr*dr-D*D;
00240 if (dy>=0)
00241 sign=1;
00242 else
00243 sign=-1;
00244
00245 if (delta<0.000001)
00246 return false;
00247 else
00248 {
00249 p0.X()=(D*dy+sign*dx*sqrt(delta))/dr*dr;
00250 p0.Y()=(-D*dx+fabs(dy)*sqrt(delta))/dr*dr;
00251 p1.X()=(D*dy-sign*dx*sqrt(delta))/dr*dr;
00252 p1.Y()=(-D*dx-fabs(dy)*sqrt(delta))/dr*dr;
00253 p0+=center;
00254 p1+=center;
00255 return true;
00256 }
00257 }
00259 }
00260 #endif
