geom.cpp

Go to the documentation of this file.

 
#include <2geom/geom.h>
#include <2geom/point.h>
#include <algorithm>
#include <optional>
#include <2geom/rect.h>
 
using std::swap;
 
namespace Geom {
 
enum IntersectorKind {
    intersects = 0,
    parallel,
    coincident,
    no_intersection
};
enum IntersectorKind {…};
 
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;
}
line_intersection(Geom::Point const &n0, double const d0, {…}
 
 
 
/* 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
    }
}
intersector_ccw(const Geom::Point& p0, const Geom::Point& p1, {…}
 
bool
line_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;
 
    return ((intersector_ccw(p00, p01, p10) * intersector_ccw(p00, p01, p11)) <= 0 );
}
line_segment_intersectp(Geom::Point const &p00, Geom::Point const &p01, {…}
 
 
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 (line_segment_intersectp(p00, p01, p10, p11) &&
            line_segment_intersectp(p10, p11, p00, p01));
}
segment_intersectp(Geom::Point const &p00, Geom::Point const &p01, {…}
 
IntersectorKind
line_segment_intersect(Geom::Point const &p00, Geom::Point const &p01,
                       Geom::Point const &p10, Geom::Point const &p11,
                       Geom::Point &result)
{
    if(line_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;
    }
}
line_segment_intersect(Geom::Point const &p00, Geom::Point const &p01, {…}
 
 
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;
    }
}
segment_intersect(Geom::Point const &p00, Geom::Point const &p01, {…}
 
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);
}
line_twopoint_intersect(Geom::Point const &p00, Geom::Point const &p01, {…}
 
// this is used to compare points for std::sort below
static bool
is_less(Point const &A, Point const &B)
{
    if (A[X] < B[X]) {
        return true;
    } else if (A[X] == B[X] && A[Y] < B[Y]) {
        return true;
    } else {
        return false;
    }
}
is_less(Point const &A, Point const &B) {…}
 
// TODO: this can doubtlessly be improved
static void
eliminate_duplicates_p(std::vector<Point> &pts)
{
    unsigned int size = pts.size();
 
    if (size < 2)
        return;
 
    if (size == 2) {
        if (pts[0] == pts[1]) {
            pts.pop_back();
        }
    } else {
        std::sort(pts.begin(), pts.end(), &is_less);
        if (size == 3) {
            if (pts[0] == pts[1]) {
                pts.erase(pts.begin());
            } else if (pts[1] == pts[2]) {
                pts.pop_back();
            }
        } else {
            // we have size == 4
            if (pts[2] == pts[3]) {
                pts.pop_back();
            }
            if (pts[0] == pts[1]) {
                pts.erase(pts.begin());
            }
        }
    }
}
eliminate_duplicates_p(std::vector<Point> &pts) {…}
 
std::vector<Geom::Point>
rect_line_intersect(Geom::Point const &c0, Geom::Point const &c1,
                    Geom::Point const &p0, Geom::Point const &p1)
{
    using namespace Geom;
 
    std::vector<Point> results;
 
    Point A(c0);
    Point C(c1);
 
    Point B(A[X], C[Y]);
    Point D(C[X], A[Y]);
 
    Point res;
 
    if (line_segment_intersect(p0, p1, A, B, res) == intersects) {
        results.push_back(res);
    }
    if (line_segment_intersect(p0, p1, B, C, res) == intersects) {
        results.push_back(res);
    }
    if (line_segment_intersect(p0, p1, C, D, res) == intersects) {
        results.push_back(res);
    }
    if (line_segment_intersect(p0, p1, D, A, res) == intersects) {
        results.push_back(res);
    }
 
    eliminate_duplicates_p(results);
 
    if (results.size() == 2) {
        // sort the results so that the order is the same as that of p0 and p1
        Point dir1 (results[1] - results[0]);
        Point dir2 (p1 - p0);
        if (dot(dir1, dir2) < 0) {
            swap(results[0], results[1]);
        }
    }
 
    return results;
}
rect_line_intersect(Geom::Point const &c0, Geom::Point const &c1, {…}
 
std::optional<LineSegment>
rect_line_intersect(Geom::Rect &r,
                    Geom::LineSegment ls)
{
    std::vector<Point> results;
    
    results =  rect_line_intersect(r.min(), r.max(), ls[0], ls[1]);
    if(results.size() == 2) {
        return LineSegment(results[0], results[1]);
    } 
    return std::optional<LineSegment>();
}
rect_line_intersect(Geom::Rect &r, {…}
 
std::optional<LineSegment>
rect_line_intersect(Geom::Rect &r,
                    Geom::Line l)
{
    return rect_line_intersect(r, l.segment(0, 1));
}
rect_line_intersect(Geom::Rect &r, {…}
 
int centroid(std::vector<Geom::Point> const &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;
}
int centroid(std::vector<Geom::Point> const &p, Geom::Point& centroid, double &area) {…}
 
}
 
/*
  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:fileencoding=utf-8:textwidth=99 :