#line 2 "Mylib/Geometry/Float/geometry_template.cpp"
#include <cmath>
#include <iostream>
#include <vector>
namespace haar_lib {
template <typename T>
struct vec {
T x, y;
vec() {}
vec(T x, T y) : x(x), y(y) {}
friend auto operator+(const vec &a, const vec &b) { return vec(a.x + b.x, a.y + b.y); }
friend auto operator-(const vec &a, const vec &b) { return vec(a.x - b.x, a.y - b.y); }
friend auto operator-(const vec &a) { return vec(-a.x, -a.y); }
friend bool operator==(const vec &a, const vec &b) { return a.x == b.x and a.y == b.y; }
friend bool operator!=(const vec &a, const vec &b) { return !(a == b); }
friend bool operator<(const vec &a, const vec &b) { return a.x < b.x or (a.x == b.x and a.y < b.y); }
friend std::istream &operator>>(std::istream &s, vec &a) {
s >> a.x >> a.y;
return s;
}
};
template <typename T, typename U>
auto operator*(const vec<T> &a, const U &k) { return vec<T>(a.x * k, a.y * k); }
template <typename T, typename U>
auto operator*(const U &k, const vec<T> &a) { return vec<T>(a.x * k, a.y * k); }
template <typename T, typename U>
auto operator/(const vec<T> &a, const U &k) { return vec<T>(a.x / k, a.y / k); }
template <typename T>
using point = vec<T>;
template <typename T>
T abs(const vec<T> &a) { return sqrt(a.x * a.x + a.y * a.y); }
template <typename T>
T abs_sq(const vec<T> &a) { return a.x * a.x + a.y * a.y; }
template <typename T>
T dot(const vec<T> &a, const vec<T> &b) { return a.x * b.x + a.y * b.y; }
template <typename T>
T cross(const vec<T> &a, const vec<T> &b) { return a.x * b.y - a.y * b.x; }
template <typename T>
auto unit(const vec<T> &a) { return a / abs(a); }
template <typename T>
auto normal(const vec<T> &p) { return vec<T>(-p.y, p.x); }
template <typename T>
auto polar(const T &r, const T &ang) { return vec<T>(r * cos(ang), r * sin(ang)); }
template <typename T>
T angle(const vec<T> &a, const vec<T> &b) { return atan2(b.y - a.y, b.x - a.x); }
template <typename T>
T phase(const vec<T> &a) { return atan2(a.y, a.x); }
template <typename T>
T angle_diff(const vec<T> &a, const vec<T> &b) {
T r = phase(b) - phase(a);
if (r < -M_PI)
return r + 2 * M_PI;
else if (r > M_PI)
return r - 2 * M_PI;
return r;
}
template <typename T>
struct line {
point<T> from, to;
line() : from(), to() {}
line(const point<T> &from, const point<T> &to) : from(from), to(to) {}
};
template <typename T>
using segment = line<T>;
template <typename T>
auto unit(const line<T> &a) { return unit(a.to - a.from); }
template <typename T>
auto normal(const line<T> &a) { return normal(a.to - a.from); }
template <typename T>
auto diff(const segment<T> &a) { return a.to - a.from; }
template <typename T>
T abs(const segment<T> &a) { return abs(diff(a)); }
template <typename T>
T dot(const line<T> &a, const line<T> &b) { return dot(diff(a), diff(b)); }
template <typename T>
T cross(const line<T> &a, const line<T> &b) { return cross(diff(a), diff(b)); }
template <typename T>
using polygon = std::vector<point<T>>;
template <typename T>
struct circle {
point<T> center;
T radius;
circle() : center(), radius(0) {}
circle(const point<T> ¢er, T radius) : center(center), radius(radius) {}
};
template <typename T>
std::ostream &operator<<(std::ostream &s, const vec<T> &a) {
s << "(" << a.x << ", " << a.y << ")";
return s;
}
template <typename T>
std::ostream &operator<<(std::ostream &s, const line<T> &a) {
s << "(" << a.from << " -> " << a.to << ")";
return s;
}
template <typename T>
std::ostream &operator<<(std::ostream &s, const circle<T> &a) {
s << "("
<< "center: " << a.center << ", "
<< "radius: " << a.radius << ")";
return s;
}
} // namespace haar_lib
#line 3 "Mylib/Geometry/Float/ccw.cpp"
namespace haar_lib {
namespace ccw_impl {
enum status {
ONLINE_BACK = -2,
COUNTER_CLOCKWISE = -1,
ON_SEGMENT = 0,
CLOCKWISE = 1,
ONLINE_FRONT = 2
};
}
struct ccw {
ccw_impl::status value;
bool operator==(const ccw &that) const { return value == that.value; };
bool operator!=(const ccw &that) const { return value != that.value; };
bool is_online_back() const { return value == ccw_impl::status::ONLINE_BACK; }
bool is_counter_clockwise() const { return value == ccw_impl::status::COUNTER_CLOCKWISE; }
bool is_on_segment() const { return value == ccw_impl::status::ON_SEGMENT; }
bool is_clockwise() const { return value == ccw_impl::status::CLOCKWISE; }
bool is_online_front() const { return value == ccw_impl::status::ONLINE_FRONT; }
};
template <typename T>
ccw check_ccw(const point<T> &p0, const point<T> &p1, const point<T> &p2) {
using namespace ccw_impl;
const T cr = cross(p1 - p0, p2 - p0);
const T d = dot(p1 - p0, p2 - p0);
if (cr == 0) {
if (d < 0)
return ccw({ONLINE_BACK});
else if (abs(p2 - p0) > abs(p1 - p0))
return ccw({ONLINE_FRONT});
else
return ccw({ON_SEGMENT});
} else if (cr > 0) {
return ccw({COUNTER_CLOCKWISE});
} else {
return ccw({CLOCKWISE});
}
}
} // namespace haar_lib
#line 4 "Mylib/Geometry/Float/is_point_in_polygon.cpp"
namespace haar_lib {
namespace point_in_polygon_impl {
enum class status { INCLUSION,
ON_SEGMENT,
OUTSIDE };
struct result {
status s;
bool is_inclusion() const { return s == status::INCLUSION; }
bool is_on_segment() const { return s == status::ON_SEGMENT; }
bool is_outside() const { return s == status::OUTSIDE; }
};
} // namespace point_in_polygon_impl
template <typename T>
auto point_in_polygon(const point<T> &p, const polygon<T> &polygon) {
using namespace point_in_polygon_impl;
const int n = polygon.size();
T d = 0;
for (int i = 0; i < n; ++i) {
if (check_ccw(polygon[i], polygon[(i + 1) % n], p).is_on_segment()) {
return result({status::ON_SEGMENT});
}
T a = angle(polygon[i], p);
T b = angle(polygon[(i + 1) % n], p);
if (a < 0) a += 2 * M_PI;
if (b < 0) b += 2 * M_PI;
T ang = b - a;
if (abs(ang) > M_PI) {
if (ang <= 0)
ang += 2 * M_PI;
else
ang -= 2 * M_PI;
}
d += ang;
}
if (abs(abs(d) - 2 * M_PI) == 0) return result({status::INCLUSION});
return result({status::OUTSIDE});
}
} // namespace haar_lib
Check if a point is in a polygon
Geometry template
(Mylib/Geometry/Float/geometry_template.cpp)