diff options
Diffstat (limited to 'src/2geom/geom.cpp')
| -rw-r--r-- | src/2geom/geom.cpp | 218 |
1 files changed, 218 insertions, 0 deletions
diff --git a/src/2geom/geom.cpp b/src/2geom/geom.cpp new file mode 100644 index 000000000..d2f2ef29b --- /dev/null +++ b/src/2geom/geom.cpp @@ -0,0 +1,218 @@ +/** + * \file src/geom.cpp + * \brief Various geometrical calculations. + */ + +#ifdef HAVE_CONFIG_H +# include <config.h> +#endif +#include "geom.h" +#include "point.h" + +/** + * Finds the intersection of the two (infinite) lines + * defined by the points p such that dot(n0, p) == d0 and dot(n1, p) == d1. + * + * If the two lines intersect, then \a result becomes their point of + * intersection; otherwise, \a result remains unchanged. + * + * This function finds the intersection of the two lines (infinite) + * defined by n0.X = d0 and x1.X = d1. The algorithm is as follows: + * To compute the intersection point use kramer's rule: + * \verbatim + * convert lines to form + * ax + by = c + * dx + ey = f + * + * ( + * e.g. a = (x2 - x1), b = (y2 - y1), c = (x2 - x1)*x1 + (y2 - y1)*y1 + * ) + * + * In our case we use: + * a = n0.x d = n1.x + * b = n0.y e = n1.y + * c = d0 f = d1 + * + * so: + * + * adx + bdy = cd + * adx + aey = af + * + * bdy - aey = cd - af + * (bd - ae)y = cd - af + * + * y = (cd - af)/(bd - ae) + * + * repeat for x and you get: + * + * x = (fb - ce)/(bd - ae) \endverbatim + * + * If the denominator (bd-ae) is 0 then the lines are parallel, if the + * numerators are then 0 then the lines coincide. + * + * \todo Why not use existing but outcommented code below + * (HAVE_NEW_INTERSECTOR_CODE)? + */ +IntersectorKind +line_intersection(Geom::Point const &n0, double const d0, + Geom::Point const &n1, double const d1, + Geom::Point &result) +{ + double denominator = dot(Geom::rot90(n0), n1); + double X = n1[Geom::Y] * d0 - + n0[Geom::Y] * d1; + /* X = (-d1, d0) dot (n0[Y], n1[Y]) */ + + if (denominator == 0) { + if ( X == 0 ) { + return coincident; + } else { + return parallel; + } + } + + double Y = n0[Geom::X] * d1 - + n1[Geom::X] * d0; + + result = Geom::Point(X, Y) / denominator; + + return intersects; +} + + + + +/* ccw exists as a building block */ +int +intersector_ccw(const Geom::Point& p0, const Geom::Point& p1, + const Geom::Point& p2) +/* Determine which way a set of three points winds. */ +{ + Geom::Point d1 = p1 - p0; + Geom::Point d2 = p2 - p0; + /* compare slopes but avoid division operation */ + double c = dot(Geom::rot90(d1), d2); + if(c > 0) + return +1; // ccw - do these match def'n in header? + if(c < 0) + return -1; // cw + + /* Colinear [or NaN]. Decide the order. */ + if ( ( d1[0] * d2[0] < 0 ) || + ( d1[1] * d2[1] < 0 ) ) { + return -1; // p2 < p0 < p1 + } else if ( dot(d1,d1) < dot(d2,d2) ) { + return +1; // p0 <= p1 < p2 + } else { + return 0; // p0 <= p2 <= p1 + } +} + +/** Determine whether two line segments intersect. This doesn't find + the point of intersection, use the line_intersect function above, + or the segment_intersection interface below. + + \pre neither segment is zero-length; i.e. p00 != p01 and p10 != p11. +*/ +static bool +segment_intersectp(Geom::Point const &p00, Geom::Point const &p01, + Geom::Point const &p10, Geom::Point const &p11) +{ + if(p00 == p01) return false; + if(p10 == p11) return false; + + /* true iff ( (the p1 segment straddles the p0 infinite line) + * and (the p0 segment straddles the p1 infinite line) ). */ + return ((intersector_ccw(p00,p01, p10) + *intersector_ccw(p00, p01, p11)) <=0 ) + && + ((intersector_ccw(p10,p11, p00) + *intersector_ccw(p10, p11, p01)) <=0 ); +} + + +/** Determine whether \& where two line segments intersect. + +If the two segments don't intersect, then \a result remains unchanged. + +\pre neither segment is zero-length; i.e. p00 != p01 and p10 != p11. +**/ +IntersectorKind +segment_intersect(Geom::Point const &p00, Geom::Point const &p01, + Geom::Point const &p10, Geom::Point const &p11, + Geom::Point &result) +{ + if(segment_intersectp(p00, p01, p10, p11)) { + Geom::Point n0 = (p01 - p00).ccw(); + double d0 = dot(n0,p00); + + Geom::Point n1 = (p11 - p10).ccw(); + double d1 = dot(n1,p10); + return line_intersection(n0, d0, n1, d1, result); + } else { + return no_intersection; + } +} + +/** Determine whether \& where two line segments intersect. + +If the two segments don't intersect, then \a result remains unchanged. + +\pre neither segment is zero-length; i.e. p00 != p01 and p10 != p11. +**/ +IntersectorKind +line_twopoint_intersect(Geom::Point const &p00, Geom::Point const &p01, + Geom::Point const &p10, Geom::Point const &p11, + Geom::Point &result) +{ + Geom::Point n0 = (p01 - p00).ccw(); + double d0 = dot(n0,p00); + + Geom::Point n1 = (p11 - p10).ccw(); + double d1 = dot(n1,p10); + return line_intersection(n0, d0, n1, d1, result); +} + +/** + * polyCentroid: Calculates the centroid (xCentroid, yCentroid) and area of a polygon, given its + * vertices (x[0], y[0]) ... (x[n-1], y[n-1]). It is assumed that the contour is closed, i.e., that + * the vertex following (x[n-1], y[n-1]) is (x[0], y[0]). The algebraic sign of the area is + * positive for counterclockwise ordering of vertices in x-y plane; otherwise negative. + + * Returned values: + 0 for normal execution; + 1 if the polygon is degenerate (number of vertices < 3); + 2 if area = 0 (and the centroid is undefined). + + * for now we require the path to be a polyline and assume it is closed. +**/ + +int centroid(std::vector<Geom::Point> p, Geom::Point& centroid, double &area) { + const unsigned n = p.size(); + if (n < 3) + return 1; + Geom::Point centroid_tmp(0,0); + double atmp = 0; + for (unsigned i = n-1, j = 0; j < n; i = j, j++) { + const double ai = -cross(p[j], p[i]); + atmp += ai; + centroid_tmp += (p[j] + p[i])*ai; // first moment. + } + area = atmp / 2; + if (atmp != 0) { + centroid = centroid_tmp / (3 * atmp); + return 0; + } + return 2; +} + +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 : |