138 lines
2.5 KiB
C++
138 lines
2.5 KiB
C++
#ifndef header_2d
|
|
#define header_2d
|
|
|
|
#include <array>
|
|
#include <complex>
|
|
#include <initializer_list>
|
|
|
|
namespace arras {
|
|
|
|
using Float = float;
|
|
using Vec2 = std::complex<Float>;
|
|
|
|
const Float eps = 1e-6;
|
|
|
|
inline Float cross(const Vec2& a, const Vec2& b) {
|
|
return a.real() * b.imag() - a.imag() * b.real();
|
|
}
|
|
|
|
inline Float dot(const Vec2& a, const Vec2& b) {
|
|
return a.real() * b.real() + a.imag() * b.imag();
|
|
}
|
|
|
|
inline Float asAngle(const Vec2& d) {
|
|
return std::atan2(d.imag(), d.real());
|
|
}
|
|
|
|
struct Circle {
|
|
Vec2 o;
|
|
Float r;
|
|
|
|
Circle() = delete;
|
|
Circle(const Vec2& o, Float r): o(o), r(r) {}
|
|
|
|
bool contain(const Vec2& a) const {
|
|
return abs(o - a) <= r;
|
|
}
|
|
};
|
|
|
|
template<int n>
|
|
struct Polygon {
|
|
static_assert(n >= 3, "Polygon must have at least 3 edges");
|
|
std::array<Vec2, n> vertex;
|
|
|
|
Polygon() = delete;
|
|
Polygon(const std::array<Vec2, n>& v): vertex(v) {}
|
|
Polygon(std::initializer_list<Vec2>&& v) {
|
|
int i = 0;
|
|
for (auto&& x : v) {
|
|
if (i >= n) {
|
|
break;
|
|
}
|
|
vertex[i] = x;
|
|
i += 1;
|
|
}
|
|
}
|
|
|
|
Vec2& operator[](int i) {
|
|
return vertex[i];
|
|
}
|
|
|
|
Vec2 operator[](int i) const {
|
|
return vertex[i];
|
|
}
|
|
|
|
bool contain(const Vec2& a) const {
|
|
Float s = 0;
|
|
for (int i = 0; i < n; i++) {
|
|
Vec2 u = vertex[i] - a, w = vertex[(i + 1) % n] - a;
|
|
s += atan2(cross(u, w), dot(u, w));
|
|
}
|
|
return abs(s) > eps;
|
|
}
|
|
};
|
|
|
|
inline bool intersect(const Circle& a, const Circle& b) {
|
|
return abs(a.o - b.o) <= a.r + b.r;
|
|
}
|
|
|
|
template<int n, int m>
|
|
inline bool intersect(const Polygon<n>& a, const Polygon<m>& b) {
|
|
for (int i = 0; i < n; i++) {
|
|
if (b.contain(a[i])) {
|
|
return true;
|
|
}
|
|
}
|
|
|
|
for (int i = 0; i < m; i++) {
|
|
if (a.contain(b[i])) {
|
|
return true;
|
|
}
|
|
}
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
for (int j = 0; j < m; j++) {
|
|
if (cross(b[j] - a[i], a[(i + 1) % n] - a[i])
|
|
* cross(b[(j + 1) % m] - a[i], a[(i + 1) % n] - a[i])
|
|
<= 0
|
|
&& cross(a[i] - b[j], b[(j + 1) % m] - b[j])
|
|
* cross(a[(i + 1) % n] - b[j], b[(j + 1) % m] - b[j])
|
|
<= 0) {
|
|
return true;
|
|
}
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
template<int n>
|
|
inline bool intersect(const Polygon<n>& a, const Circle& b) {
|
|
if (a.contain(b.o)) {
|
|
return true;
|
|
}
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
if (b.contain(a[i])) {
|
|
return true;
|
|
}
|
|
}
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
Vec2 u = b.o - a[i], v = a[(i + 1) % n] - a[i];
|
|
Float c = dot(u, v) / norm(v);
|
|
if (0 <= c && c <= 1 && abs(u - c * v) <= b.r) {
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
}
|
|
|
|
template<int n>
|
|
inline bool intersect(const Circle& b, const Polygon<n>& a) {
|
|
return intersect(a, b);
|
|
}
|
|
}
|
|
|
|
#endif
|