介绍

最近业务中遇到了如下需求 —— 有一系列半径不同的圆,需要通过鼠标的框选操作将这些圆以选中状态标示出来:

项目是基于 d3 的项目,也就是说所有的圆都在一个 svgg 图层上;框选操作用的是 d3-brush,会在 svg 上生成一个新的图层 g,然后在这个新的 g 图层上根据鼠标的拖拽生成一个矩形选框。

框选图层和圆所在图层是两个独立的图层。本来以为 d3 会把选中与否的状态一并给出,结果发现并没有… 已知的只有这些信息:

  1. 所有圆的圆心坐标和半径;
  2. 矩形选框两个对角线顶点的坐标;

于是问题就变成了,如何判断矩形与圆是否相交?

调研

通过 Google 搜索可以发现 StackOverflow 上有相关问题

可以把矩形和圆相交的情况分为两种:

  1. 圆心在矩形内
  2. 矩形任意一条边(线段)和圆相交

建模

基础类型

通过以上调研可知需要以下要素:点、线段、直线、矩形、圆。通过代码(TypeScript)来声明类型。

1
2
3
4
export interface Point {
x: number;
y: number;
}
线段
1
2
3
4
export interface LineSegment {
p: Point;
q: Point;
}
直线
1
2
3
4
export interface Line { // f(x) = kx + b
k: number;
b: number;
}
矩形
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* p
* -----------------
* | |
* | |
* | |
* -----------------
* q
**/
export interface Rectangle {
p: Point;
q: Point;
}
1
2
3
4
export interface Circle {
p: Point;
r: number;
}

基础方法

有了基础类型,还需要一些基础方法,下面将依次介绍。

两点是否相同
1
2
3
export function isTwoPointEqual(a: Point, b: Point) {
return (a.x === b.x) && (a.y === b.y);
}
两点间距离的平方

没有看错,是平方。这里为了减少后续的计算量就不开根号了…

1
2
3
export function distanceSquare(p: Point, q: Point) {
return (p.x - q.x) ** 2 + (p.y - q.y) ** 2;
}
两点确定一条直线
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* if there is a line f(x) = k * x + b go through two points p(x0, y0) and q(x1, y1),
* then there must be:
* y0 = k * x0 + b,
* y1 = k * x1 + b
**/
export function getLineByTwoPoints(p: Point, q: Point) {
if (isTwoPointEqual(p, q)) { // two points must not be the same point
return undefined;
}

// this is the line x = b
if (p.x === q.x) {
return {
k: Infinity,
b: p.x,
};
}

return {
k: (q.y - p.y) / (q.x - p.x),
b: (p.y * q.x - q.y * p.x) / (q.x - p.x)
};
}

考虑到有三种可能的特殊情况:

第一种特殊情况,两个点是相同的点,这个时候无法确定唯一的直线,因此返回 undefined

第二种情况,通过两点的直线是平行于 y 轴的直线,如果按照常规公式计算是求不出斜率的(无穷大),这里设定平行于 y 轴的直线斜率为无穷大(k=∞)

第三种情况,通过两点的直线是平行于 x 轴的直线,这时候按照常规公式计算可以得出斜率为 0,因此这里不做特殊处理。

通过直线上某点的坐标
1
2
3
4
5
6
7
export function LineFun(x: number, line: Line): number | undefined {
if (!Number.isFinite(line.k)) { // k is Infinity, means line is x = b
return undefined;
}

return line.k * x + line.b;
}
判断某个点是否在直线上
1
2
3
4
5
6
7
export function isPointOnLine({x, y}: Point, line: Line) {
if (!Number.isFinite(line.k)) { // x = b
return x === line.b;
}

return LineFun(x, line) === y;
}
判断某个点是否在线段上
1
2
3
4
5
6
7
export function isPointOnLineSegment(p: Point, ls: LineSegment) {
const line = getLineByTwoPoints(ls.p, ls.q);

return (p.x >= Math.min(ls.p.x, ls.q.x)) && (p.x <= Math.max(ls.p.x, ls.q.x)) &&
(p.y >= Math.min(ls.p.y, ls.q.y)) && (p.y <= Math.max(ls.p.y, ls.q.y)) &&
isPointOnLine(p, line);
}
找到直线上距离某点最近的点

不考虑特殊情况(已知点在已知直线上),如果要求已知直线上距离直线外已知点最近的那个点,若垂直于已知直线 l 过已知点 p 做直线 l' 交直线 l 于点 q,则点 q 就是所求的那个点。

若直线 l 与直线 l' 的斜率分别为 kk2,则 kk2 相乘结果为 -1;再分别根据通过点 p 的直线 l 的方程 y = k * x + b,通过点 p 与点 q 的直线 l' 的方程 y = k2 * x + b 列出方程组求解即可。

解决这个方程组倒是挺累的… 高考之后就没碰过这些了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
export function findTheNearestPointOnLineToPoint(p: Point, l: Line) {
if (isPointOnLine(p, l)) {
return p;
}

if (!Number.isFinite(l.k)) { // x = b
return { x: l.b, y: p.y };
}

if (l.k === 0) { // y = b
return { x: p.x, y: l.b };
}

/**
* imagine the nearest point q on the line is (x1, y1), it satisfy y1 = k * x1 + b,
* and the line2 go through both p(x0, y0) and q, and line2 has k2 and b2, it must satisfy k * k2 = -1
* because line and line2 are vertical, so:
* y1 = k * x1 + b,
* y1 = k2 * x1 + b2,
* y0 = k2 * x0 + b2,
* k * k2 = -1
*
* and at least we can get that:
* x1 = (x0 - k * b) / (k ** 2 + 1)
* y1 = k * x1 + b
**/
const x = (p.x - l.k * l.b) / (l.k ** 2 + 1);
return {
x,
y: l.k * x + l.b,
};
}

进阶方法

根据基础方法可以组合出进阶方法。

判断某个点是否在圆内

实际上是判断这个点和圆心的距离(的平方)是否小于等于圆的半径(的平方)。

1
2
3
export function isPointInCircle(point: Point, circle: Circle) {
return distanceSquare(point, circle.p) <= (circle.r ** 2);
}
判断某个点是否在矩形内
1
2
3
export function isPointInRectangle(p0: Point, { p, q }: Rectangle) {
return (p0.x > p.x) && (p0.y > p.y) && (p0.x < q.x) && (p0.y < q.y);
}
判断线段是否和圆相交

线段和圆相交时也可以分为两种情况:

  1. 线段的某个端点(p 或者 q)在圆内
  2. 线段的两个端点都不在圆内,但是通过线段的两个端点(pq)的直线上,距离圆心距离最近的那个点,在圆内
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* if a line segment which has two points ls.p and ls.q on it's end
* is intersect with a circle which have point c.p on it's center and have c.r radius, it must
*
* ls.p or ls.q is in circle OR the nearest point q on line segment to circle center point, is in circle
**/
export function isLineSegmentIntersectCircle(ls: LineSegment, c: Circle) {
if (isTwoPointEqual(ls.p, ls.q)) {
return isPointInCircle(ls.p, c);
}

const np = findTheNearestPointOnLineToPoint(c.p, getLineByTwoPoints(ls.p, ls.q));
return isPointInCircle(ls.p, c) ||
isPointInCircle(ls.q, c) ||
(isPointInCircle(np, c) && isPointOnLineSegment(np, ls));
}

求解

根据这些类型和方法,可以最终求解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
export function isRectangleOverlapCircle(rectangle: Rectangle, circle: Circle) {
const { p, q } = rectangle;

// single node
if (isTwoPointEqual(p, q)) {
return isPointInCircle(p, circle);
}

/**
* There are only two cases when the circle intersects with the rectangle:
* - Either the circle's centre lies inside the rectangle, or
* - One of the edges of the rectangle has a point in the circle.
*
* https://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection
**/
const a = p;
const b = { x: p.x, y: q.y };
const c = q;
const d = { x: q.x, y: p.y };

return isPointInRectangle(circle.p, rectangle) ||
isLineSegmentIntersectCircle({ p: a, q: b}, circle) ||
isLineSegmentIntersectCircle({ p: b, q: c}, circle) ||
isLineSegmentIntersectCircle({ p: c, q: d}, circle) ||
isLineSegmentIntersectCircle({ p: d, q: a}, circle);
}

后记

这个问题感觉还挺有意思的,有点像是 rts 游戏里选中单位的操作。根据这些建模还可以拓展出很多东西来。

某些地方其实还考虑复杂了,比如拖选操作拖出来的矩形选框的四条边实际上就是平行于 x 轴和 y 轴的…