line-geometry.cpp

Go to the documentation of this file.

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * Routines for dealing with lines (intersections, etc.)
 *
 * Authors:
 *   Maximilian Albert <Anhalter42@gmx.de>
 *
 * Copyright (C) 2007 authors
 *
 * Released under GNU GPL v2+, read the file 'COPYING' for more information.
 */
 
#include "line-geometry.h"
#include "desktop.h"
 
namespace Box3D {
 
Line::Line(Geom::Point const &start, Geom::Point const &vec, bool is_endpoint):
    pt(start)
{
    if (is_endpoint)
        v_dir = vec - start;
    else
        v_dir = vec;
    normal = v_dir.ccw();
    d0 = Geom::dot(normal, pt);
}
Line::Line(Geom::Point const &start, Geom::Point const &vec, bool is_endpoint): {…}
 
Line::Line(Line const &line)
= default;
 
Line &Line::operator=(Line const &line) = default;
 
std::optional<Geom::Point> Line::intersect(Line const &line) {
    Geom::Coord denom = Geom::dot(v_dir, line.normal);
    std::optional<Geom::Point> no_point;
    if (fabs(denom) < 1e-6)
        return no_point;
 
    Geom::Coord lambda = (line.d0 - Geom::dot(pt, line.normal)) / denom;
    return pt + lambda * v_dir;
}
std::optional<Geom::Point> Line::intersect(Line const &line) {…}
 
void Line::set_direction(Geom::Point const &dir)
{
    v_dir = dir;
    normal = v_dir.ccw();
    d0 = Geom::dot(normal, pt);
}
void Line::set_direction(Geom::Point const &dir) {…}
 
Geom::Point Line::closest_to(Geom::Point const &pt)
{
    /* return the intersection of this line with a perpendicular line passing through pt */ 
    std::optional<Geom::Point> result = this->intersect(Line(pt, (this->v_dir).ccw(), false));
    g_return_val_if_fail (result, Geom::Point (0.0, 0.0));
    return *result;
}
Geom::Point Line::closest_to(Geom::Point const &pt) {…}
 
double Line::lambda (Geom::Point const pt)
{
    double sign = (Geom::dot (pt - this->pt, this->v_dir) > 0) ? 1.0 : -1.0;
    double lambda = sign * Geom::L2 (pt - this->pt);
    // FIXME: It may speed things up (but how much?) if we assume that
    //        pt lies on the line and thus skip the following test
    Geom::Point test = point_from_lambda (lambda);
    if (!pts_coincide (pt, test)) {
        g_warning ("Point does not lie on line.\n");
        return 0;
    }
    return lambda;
}
double Line::lambda (Geom::Point const pt) {…}
 
/* The coordinates of w with respect to the basis {v1, v2} */
std::pair<double, double> coordinates (Geom::Point const &v1, Geom::Point const &v2, Geom::Point const &w)
{
    double det = determinant (v1, v2);;
    if (fabs (det) < epsilon) {
        // vectors are not linearly independent; we indicate this in the return value(s)
        return std::make_pair (HUGE_VAL, HUGE_VAL);
    }
 
    double lambda1 = determinant (w, v2) / det;
    double lambda2 = determinant (v1, w) / det;
    return std::make_pair (lambda1, lambda2);
}
std::pair<double, double> coordinates (Geom::Point const &v1, Geom::Point const &v2, Geom::Point const &w) {…}
 
/* whether w lies inside the sector spanned by v1 and v2 */
bool lies_in_sector (Geom::Point const &v1, Geom::Point const &v2, Geom::Point const &w)
{
    std::pair<double, double> coords = coordinates (v1, v2, w);
    if (coords.first == HUGE_VAL) {
        // catch the case that the vectors are not linearly independent
        // FIXME: Can we assume that it's safe to return true if the vectors point in different directions?
        return (Geom::dot (v1, v2) < 0);
    }
    return (coords.first >= 0 && coords.second >= 0);
}
bool lies_in_sector (Geom::Point const &v1, Geom::Point const &v2, Geom::Point const &w) {…}
 
bool lies_in_quadrangle (Geom::Point const &A, Geom::Point const &B, Geom::Point const &C, Geom::Point const &D, Geom::Point const &pt)
{
    return (lies_in_sector (D - A, B - A, pt - A) && lies_in_sector (D - C, B - C, pt - C));
}
bool lies_in_quadrangle (Geom::Point const &A, Geom::Point const &B, Geom::Point const &C, Geom::Point const &D, Geom::Point const &pt) {…}
 
static double pos_angle (Geom::Point v, Geom::Point w)
{
    return fabs (Geom::atan2 (v) - Geom::atan2 (w));
}
static double pos_angle (Geom::Point v, Geom::Point w) {…}
 
/*
 * Returns the two corners of the quadrangle A, B, C, D spanning the edge that is hit by a semiline
 * starting at pt and going into direction dir.
 * If none of the sides is hit, it returns a pair containing two identical points.
 */
std::pair<Geom::Point, Geom::Point>
side_of_intersection (Geom::Point const &A, Geom::Point const &B, Geom::Point const &C, Geom::Point const &D,
                      Geom::Point const &pt, Geom::Point const &dir)
{
    Geom::Point dir_A (A - pt);
    Geom::Point dir_B (B - pt);
    Geom::Point dir_C (C - pt);
    Geom::Point dir_D (D - pt);
 
    std::pair<Geom::Point, Geom::Point> result;
    double angle = -1;
    double tmp_angle;
 
    if (lies_in_sector (dir_A, dir_B, dir)) {
        result = std::make_pair (A, B);
        angle = pos_angle (dir_A, dir_B);
    }
    if (lies_in_sector (dir_B, dir_C, dir)) {
        tmp_angle = pos_angle (dir_B, dir_C);
        if (tmp_angle > angle) {
            angle = tmp_angle;
            result = std::make_pair (B, C);
        }
    }
    if (lies_in_sector (dir_C, dir_D, dir)) {
        tmp_angle = pos_angle (dir_C, dir_D);
        if (tmp_angle > angle) {
            angle = tmp_angle;
            result = std::make_pair (C, D);
        }
    }
    if (lies_in_sector (dir_D, dir_A, dir)) {
        tmp_angle = pos_angle (dir_D, dir_A);
        if (tmp_angle > angle) {
            angle = tmp_angle;
            result = std::make_pair (D, A);
        }
    }
    if (angle == -1) {
        // no intersection found; return a pair containing two identical points
        return std::make_pair (A, A);
    } else {
        return result;
    }
}
side_of_intersection (Geom::Point const &A, Geom::Point const &B, Geom::Point const &C, Geom::Point const &D, {…}
 
std::optional<Geom::Point> Line::intersection_with_viewbox (SPDesktop *desktop)
{
    auto vb = desktop->get_display_area();
 
    std::pair <Geom::Point, Geom::Point> e = side_of_intersection (vb.corner(0), vb.corner(1), vb.corner(2), vb.corner(3), this->pt, this->v_dir);
    if (e.first == e.second) {
        // perspective line lies outside the canvas
        return std::optional<Geom::Point>();
    }
 
    Line line (e.first, e.second);
    return this->intersect (line);
}
std::optional<Geom::Point> Line::intersection_with_viewbox (SPDesktop *desktop) {…}
 
} // namespace Box3D 
 
/*
  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 :