582 字
3 分钟
光线投射算法
引入
如何快速判断一个点是否在一个多边形内部?
若当曲线定理(Jordan Curve Theorem)
这是一个很显然的定理(但很难证明),这条定理指出,每条平面上的简单封闭曲线总是将封面划分为两个部分.
光线投射算法(Ray casting algorithm)
我们考虑从一个点引出一条射线,显然射线一定会到达无穷远处,即对于任意的封闭曲线,射线的终点总是会在曲线外部. 我们考虑这条从曲线内部的一点引射线穿过这条封闭曲线的次数,显然每穿过曲线一次,射线都会由曲线内部/曲线外部->曲线外部/曲线内部.因此我们只需要判断这条射线穿过曲线的次数即可,次数为奇数则当前点在多边形内,否则在多边形外.
#include <algorithm>#include <bits/stdc++.h>#include <type_traits>#include <unordered_map>#include <utility>#define N 1000005#define pr pair<ll, ll>#define ll long long#define inf 100000000000using namespace std;ll n, m, ans, x;const ll mod = 1e9 + 7;class Point { public: ll x = 0, y = 0; ll operator*(const Point &oth) const { return x * oth.x + y * oth.y; } ll mul(const Point &oth) const { return x * oth.y - y * oth.x; } Point operator+(const Point &oth) const { return {x + oth.x, y + oth.y}; } Point operator-(const Point &oth) { return {x - oth.x, y - oth.y}; }};int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m; vector<Point> pol; for (int i = 1; i <= n; i++) { ll a, b; cin >> a >> b; pol.push_back({a, b}); } auto sgn = [](ll x) { if (!x) return 0; return x < 0 ? -1 : 1; }; auto check = [&](Point x) { auto check = [&](Point &a, Point &b, Point &c, Point d) { auto seg1 = b - a; auto seg2 = d - c; if (sgn(seg1.mul(c - a)) * sgn(seg1.mul(d - a)) <= 0 && sgn(seg2.mul(a - c)) * sgn(seg2.mul(b - c)) <= 0) return 1; return 0; }; Point tmp = {0, (ll)2e9 + 1000}; int cnt = 0; for (int i = 0; i < pol.size(); i++) { int pre = (i - 1 + n) % n; if ((pol[i] - pol[pre]).mul(pol[pre] - x) == 0 && (pol[i] - x) * (x - pol[pre]) >= 0) return -1; // 点在线段上 if (check(x, tmp, pol[i], pol[pre])) cnt++; ; } return cnt % 2; }; for (int i = 1; i <= m; i++) { ll x, y; cin >> x >> y; auto flag = check({x, y}); if (flag == -1) cout << "BOUNDARY\n"; else if (!flag) cout << "OUTSIDE\n"; else cout << "INSIDE\n"; } return 0;}分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 74 天
部分内容可能已过时