二维计算几何基础
大约 6 分钟
二维计算几何基础
- OI Wiki: https://oi-wiki.org/geometry/2d/
| 题目 | 难度 | |
|---|---|---|
| DD-2019009. 交通轨迹分析 | 简单 | 快速排斥实验与跨立实验 |
| 顺丰 04. 顺丰中转场车辆入场识别-电子围栏 | pnpoly 法 光线投射算法 |
判断一个点在直线的哪边
我们有直线上的一点 P 的直线的方向向量 v，想知道某个点 Q 在直线的哪边。
我们利用向量积的性质，算出 PQ · v。如果向量积为负，则 Q 在直线上方，如果向量积为 0，则 Q 在直线上，如果向量积为正，则 Q 在直线下方。
快速排斥实验与跨立实验
我们现在想判断两条线段是否相交。
首先特判一些特殊情况。如果两线段平行，自然不能相交。这种情况通过判断线段所在直线的斜率是否相等即可。
当然，如果两线段重合或部分重合，只需要判断是否有三点共线的情况即可。
如果两线段的交点为其中一条线段的端点，仍然判断是否有三点共线的情况即可。
还有些显然不相交的情况，我们口头上称之为「两条线段离着太远了」。可什么是「离着远」，怎么判断它呢？
规定「一条线段的区域」为以这条线段为对角线的，各边均与某一坐标轴平行的矩形所占的区域，那么可以发现，如果两条线段没有公共区域，则这两条线段一定不相交。
DD-2019009. 交通轨迹分析
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class DD2019009 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in, StandardCharsets.UTF_8);
int t = scanner.nextInt();
for (int i = 0; i < t; i++) {
int n = scanner.nextInt();
String[] lines = new String[n];
scanner.nextLine();
for (int j = 0; j < n; j++) {
lines[j] = scanner.nextLine();
}
List<String> res = solve(n, lines);
for (String re : res) {
System.out.println(re);
}
System.out.println();
}
}
private static final int MAX_N = 1000;
private static List<String> solve(int n, String[] lines) {
List<String> resList = new ArrayList<>();
int id = 0;
Segment[] segments = new Segment[MAX_N + 1];
// 并查集
DSU dsu = new DSU(MAX_N + 1);
for (int i = 0; i < n; i++) {
if (lines[i].startsWith("T")) {
String[] tuple = lines[i].split(" ");
double x1 = Double.parseDouble(tuple[1]);
double y1 = Double.parseDouble(tuple[2]);
double x2 = Double.parseDouble(tuple[3]);
double y2 = Double.parseDouble(tuple[4]);
Segment segment = new Segment(x1, y1, x2, y2);
for (int j = 1; j <= id; j++) {
if (isCross(segments[j], segment)) {
dsu.union(j, id + 1);
}
}
segments[++id] = segment;
} else {
String[] tuple = lines[i].split(" ");
int qId = Integer.parseInt(tuple[1]);
int sz = dsu.sz[dsu.find(qId)];
resList.add(String.valueOf(sz));
}
}
return resList;
}
private static class DSU {
// 父节点数组/祖先数组
int[] fa;
int[] sz;
// 初始化
public DSU(int n) {
fa = new int[n];
for (int i = 0; i < n; i++) {
fa[i] = i;
}
sz = new int[n];
Arrays.fill(sz, 1);
}
// 查找
int find(int x) {
// 路径压缩
if (x != fa[x]) {
fa[x] = find(fa[x]);
}
return fa[x];
}
// 合并
void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
// 合并到更小的节点
if (rootP < rootQ) {
fa[rootQ] = rootP;
sz[rootP] += sz[rootQ];
} else {
fa[rootP] = rootQ;
sz[rootQ] += sz[rootP];
}
}
}
// 判断两线段是否相交
// https://oi-wiki.org/geometry/2d/#%E5%BF%AB%E9%80%9F%E6%8E%92%E6%96%A5%E5%AE%9E%E9%AA%8C%E4%B8%8E%E8%B7%A8%E7%AB%8B%E5%AE%9E%E9%AA%8C
private static boolean isCross(Segment l1, Segment l2) {
// 快速排斥实验: 如果两条线段所在的矩形区域没有公共区域，则这两条线段一定不相交。
double[] rectangle1 = l1.getRectangle();
double[] rectangle2 = l2.getRectangle();
if (rectangle1[0] > rectangle2[2] || rectangle1[1] > rectangle2[3] || rectangle2[0] > rectangle1[2] || rectangle2[1] > rectangle1[3]) {
return false;
}
// 跨立实验: 判断一个点在直线的哪边，如果线段两点均在另一线段所在直线的同一侧，则这两条线段不相交。
// 直线上的一点 P 的直线的方向向量 v，想知道某个点 Q 在直线的哪边。
double[] v = l1.getVector();
// Q1 = [x1,y1], Q2 = [x2,y2]
double[] pQ1 = {l2.x1 - l1.x1, l2.y1 - l1.y1};
double[] pQ2 = {l2.x2 - l1.x1, l2.y2 - l1.y1};
if ((pQ1[0] * v[1] - pQ1[1] * v[0]) * (pQ2[0] * v[1] - pQ2[1] * v[0]) > 0) {
return false;
}
v = l2.getVector();
pQ1 = new double[]{l1.x1 - l2.x1, l1.y1 - l2.y1};
pQ2 = new double[]{l1.x2 - l2.x1, l1.y2 - l2.y1};
if ((pQ1[0] * v[1] - pQ1[1] * v[0]) * (pQ2[0] * v[1] - pQ2[1] * v[0]) > 0) {
return false;
}
return true;
}
private static class Segment {
double x1, y1, x2, y2;
public Segment(double x1, double y1, double x2, double y2) {
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
}
// 获取线段所在矩形区域 左下角坐标点
double[] getRectangle() {
return new double[]{Math.min(x1, x2), Math.min(y1, y2), Math.max(x1, x2), Math.max(y1, y2)};
}
// 获取线段向量
double[] getVector() {
return new double[]{x2 - x1, y2 - y1};
}
}
}
判断一点是否在任意多边形内部
光线投射算法 (Ray casting algorithm)
我们先特判一些特殊情况，比如「这个点离多边形太远了」。考虑一个能够完全覆盖该多边形的最小矩形，如果这个点不在这个矩形范围内，那么这个点一定不在多边形内。这样的矩形很好求，只需要知道多边形横坐标与纵坐标的最小值和最大值，坐标两两组合成四个点，就是这个矩形的四个顶点了。
还有点在多边形的某一边或某顶点上，这种情况十分容易判断（留作课后作业）。
我们考虑以该点为端点引出一条射线，如果这条射线与多边形有奇数个交点，则该点在多边形内部，否则该点在多边形外部，我们简记为 奇内偶外。这个算法同样被称为奇偶规则 (Even-odd rule)。
由于 Jordan curve theorem，我们知道，这条射线每次与多边形的一条边相交，就切换一次与多边形的内外关系，所以统计交点数的奇偶即可。
这样的射线怎么取？可以随机取这条射线所在直线的斜率，建议为无理数以避免出现射线与多边形某边重合的情况。
在原版代码中，使用的是记录多边形的数组中最后一个点作为射线上一点，这样统计时，如果出现射线过多边形某边或某顶点时，可以规定射线经过的点同在射线一侧，进而做跨立实验即可。
顺丰 04. 顺丰中转场车辆入场识别-电子围栏
import java.util.Arrays;
public class SfTech220619T4 {
public boolean isPointInPolygon(double x, double y, double[] coords) {
int n = coords.length / 2;
double[] vx = new double[n];
double[] vy = new double[n];
for (int i = 0; i < n; i++) {
vx[i] = coords[i * 2];
vy[i] = coords[i * 2 + 1];
}
// pnpoly
double maxX = Arrays.stream(vx).max().getAsDouble();
double minX = Arrays.stream(vx).min().getAsDouble();
double maxY = Arrays.stream(vy).max().getAsDouble();
double minY = Arrays.stream(vy).min().getAsDouble();
if (x < minX || x > maxX || y < minY || y > maxY) {
return false;
}
boolean res = false;
for (int i = 0, j = n - 1; i < n; j = i++) {
if ((vy[i] > y) != (vy[j] > y)
&& (x < (vx[j] - vx[i]) * (y - vy[i]) / (vy[j] - vy[i]) + vx[i])) {
res = !res;
}
}
return res;
}
}
（全文完）