#define INKSCAPE_LPE_KNOT_CPP

#include "live_effects/lpe-knot.h"

#include <2geom/path.h>

#include <2geom/d2.h>

#include <2geom/crossing.h>

#include <2geom/path-intersection.h>

namespace Inkscape {

namespace LivePathEffect {

LPEKnot::LPEKnot(LivePathEffectObject *lpeobject) :

Effect(lpeobject),

// initialise your parameters here:

interruption_width(_("Gap width"), _("The width of the gap in the path where it self-intersects"), "interruption_width", &wr, this, 10)

{

// register all your parameters here, so Inkscape knows which parameters this effect has:

registerParameter( dynamic_cast<Parameter *>(&interruption_width) );

}

LPEKnot::~LPEKnot()

{

}

std::vector<Geom::Interval> complementOf(Geom::Interval I, std::vector<Geom::Interval> domain){

std::vector<Geom::Interval> ret;

double min = domain.front().min();

double max = domain.back().max();

Geom::Interval I1 = Geom::Interval(min,I.min());

Geom::Interval I2 = Geom::Interval(I.max(),max);

for (unsigned i = 0; i<domain.size(); i++){

boost::optional<Geom::Interval> I1i = intersect(domain.at(i),I1);

if (I1i) ret.push_back(I1i.get());

boost::optional<Geom::Interval> I2i = intersect(domain.at(i),I2);

if (I2i) ret.push_back(I2i.get());

}

return ret;

}

Geom::Interval

findShadowedTime(Geom::Path &patha,

Geom::Path &pathb,

Geom::Crossing crossing,

unsigned idx, double width){

using namespace Geom;

double curveidx, timeoncurve = modf(crossing.getOtherTime(idx),&curveidx);

if(curveidx == pathb.size() && timeoncurve == 0) { curveidx--; timeoncurve = 0.99999;}

assert(curveidx >= 0 && curveidx < pathb.size());

std::vector<Point> MV = pathb[unsigned(curveidx)].pointAndDerivatives(timeoncurve,1);

Point T = unit_vector(MV.at(1));

Point N = T.cw();

Point A = MV.at(0)-10*width*T, B = MV.at(0)+10*width*T;

std::vector<Geom::Path> cutter;

Geom::Path cutterLeft = Geom::Path();

Geom::Path cutterRight = Geom::Path();

cutterLeft.append (LineSegment (A-width*N, B-width*N));

cutterRight.append(LineSegment (A+width*N, B+width*N));

cutter.push_back(cutterLeft);

cutter.push_back(cutterRight);

std::vector<Geom::Path> patha_as_vect = std::vector<Geom::Path>(1,patha);

CrossingSet crossingTable = crossings (patha_as_vect, cutter);

double t0 = crossing.getTime(idx);

double tmin = 0,tmax = patha.size()-0.0001;

assert(crossingTable.size()>=1);

for (unsigned c=0; c<crossingTable.front().size(); c++){

double t = crossingTable.front().at(c).ta;

assert(crossingTable.front().at(c).a==0);

if (t>tmin and t<t0) tmin = t;

if (t<tmax and t>t0) tmax = t;

}

//return Interval(t0-0.1,t0+0.1);

return Interval(tmin,tmax);

}

std::vector<Geom::Path>

split_loopy_bezier (std::vector<Geom::Path> const & path_in){

std::vector<Geom::Path> ret;

std::vector<Geom::Path>::const_iterator pi=path_in.begin();

for(; pi != path_in.end(); pi++) {

ret.push_back(Geom::Path());

for (Geom::Path::const_iterator curve(pi->begin()),end(pi->end()); curve != end; ++curve){

//is the current curve a cubic bezier?

if(Geom::CubicBezier const *cubic_bezier = dynamic_cast<Geom::CubicBezier const *>(&(*curve))){

Geom::CubicBezier theCurve = *cubic_bezier;

std::vector<Geom::Point> A = theCurve.points();

//is there a crossing in the polygon?

if( cross(A[2]-A[0],A[1]-A[0])*cross(A[3]-A[0],A[1]-A[0])<0 &&

cross(A[0]-A[3],A[2]-A[3])*cross(A[1]-A[3],A[2]-A[3])<0){

//split the curve where the tangent is parallel to the chord through end points.

double a = cross(A[3]-A[0],A[1]-A[2]);

double c = cross(A[3]-A[0],A[1]-A[0]);

double t; //where to split; solution of 3*at^2-(a+c)t +c = 0.

//TODO: don't we have a clean deg 2 equation solver?...

if (fabs(a)<.0001){

t = .5;

}else{

double delta = a*a-a*c+c*c;

t = ((a+c)-sqrt(delta))/2/a;

if ( t<0 || t>1 ) {t = ((a+c)+sqrt(delta))/2/a;}

}

//TODO: shouldn't Path have subdivide method?

std::pair<Geom::BezierCurve<3>, Geom::BezierCurve<3> > splitCurve;

splitCurve = theCurve.subdivide(t);

ret.back().append(splitCurve.first);

ret.back().append(splitCurve.second);

}else{//cubic bezier but no crossing.

ret.back().append(*curve);

}

}else{//not cubic bezier.

ret.back().append(*curve);

}

}

}

return ret;

}

std::vector<Geom::Path>

LPEKnot::doEffect_path (std::vector<Geom::Path> const & input_path)

{

using namespace Geom;

std::vector<Geom::Path> path_out;

double width = interruption_width;

std::vector<Geom::Path> path_in = split_loopy_bezier(input_path);

CrossingSet crossingTable = crossings_among(path_in);

for (unsigned i = 0; i < crossingTable.size(); i++){

std::vector<Interval> dom;

dom.push_back(Interval(0.,path_in.at(i).size()-0.00001));

//TODO: handle closed curves...

for (unsigned crs = 0; crs < crossingTable.at(i).size(); crs++){

Crossing crossing = crossingTable.at(i).at(crs);

unsigned j = crossing.getOther(i);

//TODO: select dir according to a parameter...

if ((crossing.dir and crossing.a==i) or (not crossing.dir and crossing.b==i) or (i==j)){

if (i==j and not crossing.dir) {

double temp = crossing.ta;

crossing.ta = crossing.tb;

crossing.tb = temp;

crossing.dir = not crossing.dir;

}

Interval hidden = findShadowedTime(path_in.at(i),path_in.at(j),crossing,i,width);

dom = complementOf(hidden,dom);

}

}

for (unsigned comp = 0; comp < dom.size(); comp++){

assert(dom.at(comp).min() >=0 and dom.at(comp).max() < path_in.at(i).size());

path_out.push_back(path_in.at(i).portion(dom.at(comp)));

}

}

return path_out;

}

} //namespace LivePathEffect (setq default-directory "c:/Documents And Settings/jf/Mes Documents/InkscapeSVN")

} /* namespace Inkscape */