介绍
最近业务中遇到了如下需求 —— 有一系列半径不同的圆,需要通过鼠标的框选操作将这些圆以选中状态标示出来:
项目是基于 d3 的项目,也就是说所有的圆都在一个 svg
的 g
图层上;框选操作用的是 d3-brush,会在 svg
上生成一个新的图层 g
,然后在这个新的 g
图层上根据鼠标的拖拽生成一个矩形选框。
框选图层和圆所在图层是两个独立的图层。本来以为 d3 会把选中与否的状态一并给出,结果发现并没有… 已知的只有这些信息:
- 所有圆的圆心坐标和半径;
- 矩形选框两个对角线顶点的坐标;
于是问题就变成了,如何判断矩形与圆是否相交?
调研
通过 Google 搜索可以发现 StackOverflow 上有相关问题
可以把矩形和圆相交的情况分为两种:
- 圆心在矩形内
- 矩形任意一条边(线段)和圆相交
建模
基础类型
通过以上调研可知需要以下要素:点、线段、直线、矩形、圆。通过代码(TypeScript)来声明类型。
点
1 | export interface Point { |
线段
1 | export interface LineSegment { |
直线
1 | export interface Line { // f(x) = kx + b |
矩形
1 | /** |
圆
1 | export interface Circle { |
基础方法
有了基础类型,还需要一些基础方法,下面将依次介绍。
两点是否相同
1 | export function isTwoPointEqual(a: Point, b: Point) { |
两点间距离的平方
没有看错,是平方。这里为了减少后续的计算量就不开根号了…
1 | export function distanceSquare(p: Point, q: Point) { |
两点确定一条直线
1 | /** |
考虑到有三种可能的特殊情况:
第一种特殊情况,两个点是相同的点,这个时候无法确定唯一的直线,因此返回 undefined
;
第二种情况,通过两点的直线是平行于 y 轴的直线,如果按照常规公式计算是求不出斜率的(无穷大),这里设定平行于 y 轴的直线斜率为无穷大(k=∞);
第三种情况,通过两点的直线是平行于 x 轴的直线,这时候按照常规公式计算可以得出斜率为 0
,因此这里不做特殊处理。
通过直线上某点的坐标
1 | export function LineFun(x: number, line: Line): number | undefined { |
判断某个点是否在直线上
1 | export function isPointOnLine({x, y}: Point, line: Line) { |
判断某个点是否在线段上
1 | export function isPointOnLineSegment(p: Point, ls: LineSegment) { |
找到直线上距离某点最近的点
不考虑特殊情况(已知点在已知直线上),如果要求已知直线上距离直线外已知点最近的那个点,若垂直于已知直线 l
过已知点 p
做直线 l'
交直线 l
于点 q
,则点 q
就是所求的那个点。
若直线 l
与直线 l'
的斜率分别为 k
与 k2
,则 k
、k2
相乘结果为 -1
;再分别根据通过点 p
的直线 l
的方程 y = k * x + b
,通过点 p
与点 q
的直线 l'
的方程 y = k2 * x + b
列出方程组求解即可。
(解决这个方程组倒是挺累的… 高考之后就没碰过这些了)
1 | export function findTheNearestPointOnLineToPoint(p: Point, l: Line) { |
进阶方法
根据基础方法可以组合出进阶方法。
判断某个点是否在圆内
实际上是判断这个点和圆心的距离(的平方)是否小于等于圆的半径(的平方)。
1 | export function isPointInCircle(point: Point, circle: Circle) { |
判断某个点是否在矩形内
1 | export function isPointInRectangle(p0: Point, { p, q }: Rectangle) { |
判断线段是否和圆相交
线段和圆相交时也可以分为两种情况:
- 线段的某个端点(
p
或者q
)在圆内 - 线段的两个端点都不在圆内,但是通过线段的两个端点(
p
和q
)的直线上,距离圆心距离最近的那个点,在圆内
1 | /** |
求解
根据这些类型和方法,可以最终求解:
1 | export function isRectangleOverlapCircle(rectangle: Rectangle, circle: Circle) { |
后记
这个问题感觉还挺有意思的,有点像是 rts 游戏里选中单位的操作。根据这些建模还可以拓展出很多东西来。
某些地方其实还考虑复杂了,比如拖选操作拖出来的矩形选框的四条边实际上就是平行于 x 轴和 y 轴的…