cpp-game-engine/math/src/common.cpp

//
//  common.cpp
//  math
//
//  Created by Sam Jaffe on 8/20/16.
//

#include "game/math/common.hpp"

#include <vector>

#include "game/math/angle.hpp"
#include "game/math/compare.hpp"
#include "game/math/shape.hpp"

namespace math {
  vec2 rotate(vec2 const & c, vec2 const & p, radian r) {
    vec2 trans = p - c;
    vec2 vcos = trans * static_cast<float>(cos(r));
    vec2 vsin = trans * static_cast<float>(sin(r));
    return {{vcos[0] - vsin[1] + c[0], vsin[0] - vcos[1] + c[1]}};
  }

  dim2::quad rotate(vec2 const & c, dim2::quad const & q, radian r) {
    return {rotate(c, q.ll, r), rotate(c, q.lr, r), rotate(c, q.ur, r),
            rotate(c, q.ul, r)};
  }

  orientation orient(dim2::line const & ln, dim2::point const & pt) {
    auto val = (ln.second[1] - ln.first[1]) * (pt[0] - ln.second[0]) -
               (ln.second[0] - ln.first[0]) * (pt[1] - ln.second[1]);

    if (val == 0) return colinear;
    return (val > 0) ? clockwise : anticlockwise;
  }

  bool contains(dim2::line const & ln, dim2::point const & pt) {
    auto xs = std::minmax(ln.first[0], ln.second[0]);
    auto ys = std::minmax(ln.first[1], ln.second[1]);
    return orient(ln, pt) == colinear && between(pt[0], xs.first, xs.second) &&
           between(pt[1], ys.first, ys.second);
  }

  bool contains(dim2::circle const & shape, dim2::point const & pt) {
    vec2 const delta = pt - shape.center;
    return delta.dot(delta) <= std::pow(shape.radius, 2);
  }

  static dim2::line ray_x(dim2::point const & pt, dim2::line const & l) {
    auto x_inf = std::max({l.first[0], l.second[0], pt[0]}) + 1;
    return {pt, {{x_inf, pt[1]}}};
  }

  static bool contains(std::vector<dim2::line> const & segments,
                       dim2::point const & pt) {
    int hits = 0;
    for (auto l : segments) {
      if (!intersects(l, ray_x(pt, l))) continue;
      if (orient(l, pt) == colinear) return contains(l, pt);
      ++hits;
    }
    return (hits & 1) == 1;
  }

  bool contains(dim2::quad const & shape, dim2::point const & pt) {
    return contains(shapes::segments(shape), pt);
  }

  bool intersects(dim2::line const & lhs, dim2::line const & rhs) {
    // https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
    // Find the four orientations needed for general and special cases
    orientation o1 = orient(lhs, rhs.first);
    orientation o2 = orient(lhs, rhs.second);
    orientation o3 = orient(rhs, lhs.first);
    orientation o4 = orient(rhs, lhs.second);

    // General Case: Lines cross through each other
    if (o1 != o2 && o3 != o4) return true;

    // Special Cases: one of the points exists on the other line
    return contains(lhs, rhs.first) || contains(lhs, rhs.second) ||
           contains(rhs, lhs.first) || contains(rhs, lhs.second);
  }

  bool intersects(dim2::line const & lhs, dim2::circle const & rhs) {
    if (contains(rhs, lhs.first) || contains(rhs, lhs.second)) { return true; }
    dim2::line const orth = lines::orthogonal(lhs, rhs.center);
    vec2 const delta = orth.second - orth.first;
    return delta.dot(delta) <= std::pow(rhs.radius, 2) && intersects(lhs, orth);
  }

  bool intersects(dim2::line const & lhs, dim2::quad const & rhs) {
    std::vector<dim2::line> segments = shapes::segments(rhs);
    auto lhs_intersects = [&lhs](dim2::line const & ln) {
      return intersects(lhs, ln);
    };
    return std::any_of(segments.begin(), segments.end(), lhs_intersects) ||
           contains(segments, lhs.first);
  }

  bool intersects(dim2::quad const & lhs, dim2::circle const & rhs) {
    std::vector<dim2::line> segments = shapes::segments(lhs);
    auto rhs_intersects = [&rhs](dim2::line const & ln) {
      return intersects(ln, rhs);
    };
    return std::any_of(segments.begin(), segments.end(), rhs_intersects) ||
           contains(lhs, rhs.center);
  }

  bool check_edges(dim2::line const & seg, dim2::triangle const & tri) {
    return orient(seg, tri.a) == clockwise && orient(seg, tri.b) == clockwise &&
           orient(seg, tri.c) == clockwise;
  }

  bool intersects(dim2::triangle const & lhs, dim2::triangle const & rhs) {
    if (check_edges({lhs.a, lhs.b}, rhs)) return false;
    if (check_edges({lhs.b, lhs.c}, rhs)) return false;
    if (check_edges({lhs.c, lhs.a}, rhs)) return false;
    if (check_edges({rhs.a, rhs.b}, lhs)) return false;
    if (check_edges({rhs.b, rhs.c}, lhs)) return false;
    if (check_edges({rhs.c, rhs.a}, lhs)) return false;
    return true;
  }

  bool intersects(dim2::quad const & lhs, dim2::quad const & rhs) {
    dim2::triangle l1{lhs.ll, lhs.lr, lhs.ul};
    dim2::triangle l2{lhs.ul, lhs.ur, lhs.ll};
    dim2::triangle r1{rhs.ll, rhs.lr, rhs.ul};
    dim2::triangle r2{rhs.ul, rhs.ur, rhs.ll};
    return intersects(l1, r1) || intersects(l2, r2) || intersects(l1, r2) ||
           intersects(l2, r1);
  }

  bool intersects(dim2::circle const & lhs, dim2::circle const & rhs) {
    vec2 const delta = rhs.center - lhs.center;
    return delta.dot(delta) <= std::pow(lhs.radius + rhs.radius, 2);
  }
}