计算几何简述

发表于   |  

简单记录本学期学习的计算几何知识，归类如下：

  • 点，线段
  • 点与直线，线段，矩形，多边形的位置关系
  • 线段/直线相交
  • 向量，向量叉积
  • 凸包

计算几何中的点和线一般封装为类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Point {
    int x, y;
    Point() {}
    Point(int a, int b) {
        x = a;
        y = b;
    }
}

class Seg {
    Point s, t;
    Seg() {}
    Seg(Point a, Point b) {
        s = a;
        t = b;
    }
    Seg(int x1, int y1, int x2, int y2) {
        s = new Point(x1, y1);
        t = new Point(x2, y2);
    }
}

点与直线的位置关系：点在/不在直线上
设点为P，直线上有两点A B，判断点P在直线AB上的依据是：(P - A) × (P - B) = 0

点与线段的位置关系：点在/不在线段上
若在点P在直线AB的前提下，满足P在以AB为对角顶点的矩形内， 则点P在线段AB上

点与多边形的位置关系：射线法
从点P开始，做任意一条射线，如果射线与多边形边的交点个数为偶数，则点在多边形外;交点个数为奇数，则点在多边形内。

线段/直线相交：向量叉积判断

另外可以通过向量叉积的结果(正负)判断折线段的拐向(左拐，大于零; 右拐，小于0)

1
2
3
4
5
6
7
8
// 向量AB 和向量AC 的叉积
int crossProduct(Point a, Point b, Point c) {
    int x1 = b.x - a.x;
    int y1 = b.y - a.y;
    int x2 = c.x - a.x;
    int y2 = c.y - a.y;
    return x1 * y2 - x2 * y1;
}

给定一些点，求凸包：

  1. (极角)排序(数组模拟/栈)
  2. Graham核心算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Point data[n +1]
// 极角排序(前提：data[0] 为基础点，位置在左下)
// Arrays.sort(data, 1, n, new Cmp());

class Cmp implements Comparator<Point> {

	@Override
	public int compare(Point a, Point b) {
		if (crossProduct(data[0], a, b) > 0) return -1;
		else if (crossProduct(data[0], a, b) < 0) return 1;
		else return 0;
	}
	
}

参考：计算几何算法概览