582 字
3 分钟
光线投射算法

引入#

如何快速判断一个点是否在一个多边形内部?

若当曲线定理(Jordan Curve Theorem)#

这是一个很显然的定理(但很难证明),这条定理指出,每条平面上的简单封闭曲线总是将封面划分为两个部分.

光线投射算法(Ray casting algorithm)#

我们考虑从一个点引出一条射线,显然射线一定会到达无穷远处,即对于任意的封闭曲线,射线的终点总是会在曲线外部. 我们考虑这条从曲线内部的一点引射线穿过这条封闭曲线的次数,显然每穿过曲线一次,射线都会由曲线内部/曲线外部->曲线外部/曲线内部.因此我们只需要判断这条射线穿过曲线的次数即可,次数为奇数则当前点在多边形内,否则在多边形外.


CSES Point in Polygon

#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 100000000000
using 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;
}
光线投射算法
https://sanzenin.top/posts/obsidian/光线投射算法/
作者
Sanzenin 凪
发布于
2026-09-03
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取