diff options
Diffstat (limited to 'src/2geom/path-intersection.cpp')
| -rw-r--r-- | src/2geom/path-intersection.cpp | 107 |
1 files changed, 9 insertions, 98 deletions
diff --git a/src/2geom/path-intersection.cpp b/src/2geom/path-intersection.cpp index 63a29423d..07e38ba9e 100644 --- a/src/2geom/path-intersection.cpp +++ b/src/2geom/path-intersection.cpp @@ -12,98 +12,9 @@ namespace Geom { -/** - * This function computes the winding of the path, given a reference point. - * Positive values correspond to counter-clockwise in the mathematical coordinate system, - * and clockwise in screen coordinates. This particular implementation casts a ray in - * the positive x direction. It iterates the path, checking for intersection with the - * bounding boxes. If an intersection is found, the initial/final Y value of the curve is - * used to derive a delta on the winding value. If the point is within the bounding box, - * the curve specific winding function is called. - */ -int winding(Path const &path, Point p) { - //start on a segment which is not a horizontal line with y = p[y] - Path::const_iterator start; - for(Path::const_iterator iter = path.begin(); ; ++iter) { - if(iter == path.end_closed()) { return 0; } - if(iter->initialPoint()[Y]!=p[Y]) { start = iter; break; } - if(iter->finalPoint()[Y]!=p[Y]) { start = iter; break; } - if(iter->boundsFast().height()!=0.){ start = iter; break; } - } - int wind = 0; - unsigned cnt = 0; - bool starting = true; - for (Path::const_iterator iter = start; iter != start || starting - ; ++iter, iter = (iter == path.end_closed()) ? path.begin() : iter ) - { - cnt++; - if(cnt > path.size()) return wind; //some bug makes this required - starting = false; - Rect bounds = (iter->boundsFast()); - Coord x = p[X], y = p[Y]; - - if(x > bounds.right() || !bounds[Y].contains(y)) continue; //ray doesn't intersect box - - Point final = iter->finalPoint(); - Point initial = iter->initialPoint(); - Cmp final_to_ray = cmp(final[Y], y); - Cmp initial_to_ray = cmp(initial[Y], y); - - // if y is included, these will have opposite values, giving order. - Cmp c = cmp(final_to_ray, initial_to_ray); - if(x < bounds.left()) { - // ray goes through bbox - // winding delta determined by position of endpoints - if(final_to_ray != EQUAL_TO) { - wind += int(c); // GT = counter-clockwise = 1; LT = clockwise = -1; EQ = not-included = 0 - //std::cout << int(c) << " "; - goto cont; - } - } else { - //inside bbox, use custom per-curve winding thingie - int delt = iter->winding(p); - wind += delt; - //std::cout << "n" << delt << " "; - } - //Handling the special case of an endpoint on the ray: - if(final[Y] == y) { - //Traverse segments until it breaks away from y - //99.9% of the time this will happen the first go - Path::const_iterator next = iter; - ++next; - for(; ; ++next) { - if(next == path.end_closed()) next = path.begin(); - Rect bnds = (next->boundsFast()); - //TODO: X considerations - if(bnds.height() > 0) { - //It has diverged - if(bnds.contains(p)) { - const double fudge = 0.01; - if(cmp(y, next->valueAt(fudge, Y)) == initial_to_ray) { - wind += int(c); - //std::cout << "!!!!!" << int(c) << " "; - } - iter = next; // No increment, as the rest of the thing hasn't been counted. - } else { - Coord ny = next->initialPoint()[Y]; - if(cmp(y, ny) == initial_to_ray) { - //Is a continuation through the ray, so counts windingwise - wind += int(c); - //std::cout << "!!!!!" << int(c) << " "; - } - iter = ++next; - } - goto cont; - } - if(next==start) return wind; - } - //Looks like it looped, which means everything's flat - return 0; - } - - cont:(void)0; - } - return wind; +/// Compute winding number of the path at the specified point +int winding(Path const &path, Point const &p) { + return path.winding(p); } /** @@ -162,7 +73,7 @@ void append(T &a, T const &b) { * indicates if the time values are within their proper range on the line segments. */ bool -linear_intersect(Point A0, Point A1, Point B0, Point B1, +linear_intersect(Point const &A0, Point const &A1, Point const &B0, Point const &B1, double &tA, double &tB, double &det) { bool both_lines_non_zero = (!are_near(A0, A1)) && (!are_near(B0, B1)); @@ -521,7 +432,7 @@ std::vector<double> path_mono_splits(Path const &p) { * Applies path_mono_splits to multiple paths, and returns the results such that * time-set i corresponds to Path i. */ -std::vector<std::vector<double> > paths_mono_splits(std::vector<Path> const &ps) { +std::vector<std::vector<double> > paths_mono_splits(PathVector const &ps) { std::vector<std::vector<double> > ret; for(unsigned i = 0; i < ps.size(); i++) ret.push_back(path_mono_splits(ps[i])); @@ -533,7 +444,7 @@ std::vector<std::vector<double> > paths_mono_splits(std::vector<Path> const &ps) * Each entry i corresponds to path i of the input. The number of rects in each entry is guaranteed to be the * number of splits for that path, subtracted by one. */ -std::vector<std::vector<Rect> > split_bounds(std::vector<Path> const &p, std::vector<std::vector<double> > splits) { +std::vector<std::vector<Rect> > split_bounds(PathVector const &p, std::vector<std::vector<double> > splits) { std::vector<std::vector<Rect> > ret; for(unsigned i = 0; i < p.size(); i++) { std::vector<Rect> res; @@ -553,7 +464,7 @@ std::vector<std::vector<Rect> > split_bounds(std::vector<Path> const &p, std::ve * This function does two sweeps, one on the bounds of each path, and after that cull, one on the curves within. * This leads to a certain amount of code complexity, however, most of that is factored into the above functions */ -CrossingSet MonoCrosser::crossings(std::vector<Path> const &a, std::vector<Path> const &b) { +CrossingSet MonoCrosser::crossings(PathVector const &a, PathVector const &b) { if(b.empty()) return CrossingSet(a.size(), Crossings()); CrossingSet results(a.size() + b.size(), Crossings()); if(a.empty()) return results; @@ -596,7 +507,7 @@ CrossingSet MonoCrosser::crossings(std::vector<Path> const &a, std::vector<Path> /* This function is similar codewise to the MonoCrosser, the main difference is that it deals with * only one set of paths and includes self intersection -CrossingSet crossings_among(std::vector<Path> const &p) { +CrossingSet crossings_among(PathVector const &p) { CrossingSet results(p.size(), Crossings()); if(p.empty()) return results; @@ -780,7 +691,7 @@ void flip_crossings(Crossings &crs) { crs[i] = Crossing(crs[i].tb, crs[i].ta, crs[i].b, crs[i].a, !crs[i].dir); } -CrossingSet crossings_among(std::vector<Path> const &p) { +CrossingSet crossings_among(PathVector const &p) { CrossingSet results(p.size(), Crossings()); if(p.empty()) return results; |
