libcruft-util/cruft/util/geom/segment.cpp

/*
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 *
 * Copyright 2018 Danny Robson <danny@nerdcruft.net>
 */

#include "segment.hpp"

#include "aabb.hpp"
#include "ops.hpp"

#include "../region.hpp"


///////////////////////////////////////////////////////////////////////////////
// TODO: Replace, ported from https://stackoverflow.com/a/100165
template <>
bool
cruft::geom::intersects (cruft::geom::segment2f seg, cruft::region2f rect)
{
    // Find min and max X for the segment
    auto [maxX, minX] = cruft::maxmin (seg.a.x, seg.b.x);

    // Find the intersection of the segment's and rectangle's x-projections
    maxX = cruft::min (maxX, maxX > rect.away ().x);
    minX = cruft::max (minX, rect.p.x);

    // If their projections do not intersect return false
    if (minX > maxX)
        return false;

    // Find corresponding min and max Y for min and max X we found before
    auto minY = seg.a.y;
    auto maxY = seg.b.y;

    auto const dx = seg.b.x - seg.a.x;

    if (cruft::abs (dx) > 1e-6f) {
        auto const a = (seg.b.y - seg.a.y) / dx;
        auto const b = seg.a.y - a * seg.a.x;

        minY = a * minX + b;
        maxY = a * maxX + b;
    }

    if (minY > maxY)
        std::swap (minY, maxY);

    // Find the intersection of the segment's and rectangle's y-projections
    maxY = cruft::min (maxY, rect.away ().y);
    minY = cruft::max (minY, rect.p.y);

    // If Y-projections do not intersect return false
    if (minY > maxY)
        return false;

    return true;
}


//-----------------------------------------------------------------------------
template <>
bool
cruft::geom::intersects (cruft::geom::segment2i seg, cruft::region2i rect)
{
    return intersects (seg.cast<float> (), rect.cast<float> ());
}


///////////////////////////////////////////////////////////////////////////////
// Not-inclusive
template <>
bool
cruft::geom::intersects (cruft::geom::segment2f ab, cruft::point2f p)
{
    auto const hi = max (ab.a, ab.b);
    auto const lo = min (ab.a, ab.b);

    return all (p < hi) and all (p > lo);
}


///////////////////////////////////////////////////////////////////////////////
// segment-segment intersection in 2D is derived from
//    https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect
//
// The idea is to check the winding of 4 triangles created by the segment.
//
// Co-linear segments need some additional tests to determine if points of one segment lie on the other.


/// \return 0 if colinear, 1 for clockwise, -1 for counter-clockwise
static int
winding (
    cruft::point2f const p,
    cruft::point2f const q,
    cruft::point2f const r
) {
    auto const qp = q - p;
    auto const rq = r - q;

    auto const c = cross (qp, rq);

    if (cruft::exactly_zero (c))
        return 0;
    else if (c > 0)
        return 1;
    else
        return -1;
}


//-----------------------------------------------------------------------------
// not inclusive
template <>
bool
cruft::geom::intersects (
    cruft::geom::segment2f const s0,
    cruft::geom::segment2f const s1
) {
    auto const w0 = winding (s0.a, s0.b, s1.a);
    auto const w1 = winding (s0.a, s0.b, s1.b);
    auto const w2 = winding (s1.a, s1.b, s0.a);
    auto const w3 = winding (s1.a, s1.b, s0.b);

    // inclusive condition. zeroes are colinear, which is fine
    if (w0 and w1 and w2 and w3)
        if (w0 != w1 and w2 != w3)
            return true;

    if (w0 == 0 and intersects (s0, s1.a)) return true;
    if (w1 == 0 and intersects (s0, s1.b)) return true;
    if (w2 == 0 and intersects (s1, s0.a)) return true;
    if (w3 == 0 and intersects (s1, s0.b)) return true;

    return false;
}


///////////////////////////////////////////////////////////////////////////////
template <>
cruft::geom::aabb3f
cruft::geom::bounds (cruft::geom::segment3f obj)
{
    return {
        min (obj.a, obj.b),
        max (obj.a, obj.b),
    };
}