大家好，我是前端西瓜哥。
开发图形编辑器，你会经常要解决一些算法问题。本文盘点一些我开发图形编辑器时常用到的简单几何算法。
矩形碰撞检测判断两个矩形是否发生碰撞（或者说相交），即两个矩形有重合的区域。
常见使用场景：
- 使用选择工具框选图形（框选策略除了相交，还可以用相交或其他方案）；
- 遍历图形，通过判断视口矩形和图形包围盒的矩形碰撞，剔除掉视口外的图形渲染操作，提高性能。
exportfunctionisRectIntersect2(rect1:IBox2,rect2:IBox2){
return(
rect1.minX<=rect2.maxX&&
rect1.maxX>=rect2.minX&&
rect1.minY<=rect2.maxY&&
rect1.maxY>=rect2.minY
);
}
关于 IBox2 为包围盒的接口签名：
interfaceIBox2{
minX:number;
minY:number;
maxX:number;
maxY:number;
}
该算法用于判断矩形 1 是否包含矩形 2。
常见使用场景：
- 使用选择工具框选图形（这次用的是包含策略）；
functionisRectContain2(rect1:IBox2,rect2:IBox2){
return(
rect1.minX<=rect2.minX&&
rect1.minY<=rect2.minY&&
rect1.maxX>=rect2.maxX&&
rect1.maxY>=rect2.maxY
);
}
计算旋转后坐标
对图形旋转，是一个非常基础的功能。计算旋转后的点是很常见的需求。
常见使用场景：
- 计算包围盒旋转后的坐标，绘制缩放控制点；
- 计算光标位置是否落在一个旋转的矩形上，因为旋转的矩形并不是一个正交的矩形，计算出来后判断有点复杂。所以通常我们会将光标给予矩形的中点反过来旋转一下，然后判断点是否在矩形中。
用到三角函数算法。
consttransformRotate=(
x:number,
y:number,
radian:number,
cx:number,
cy:number,
)=>{
if(!radian){
return{x,y};
}
constcos=Math.cos(radian);
constsin=Math.sin(radian);
return{
x:(x-cx)*cos-(y-cy)*sin cx,
y:(x-cx)*sin (y-cy)*cos cy,
};
}
点是否在矩形中
常见使用场景：
- 用于实现图形拾取，判断矩形图形或包围盒是否在光标位置上。
functionisPointInRect(point:IPoint,rect:IRect){
return(
point.x>=rect.x&&
point.y>=rect.y&&
point.x<=rect.x rect.width&&
point.y<=rect.y rect.height
);
}
多个矩形组成的大矩形
选中多个矩形时，要计算它们组成的大矩形，然后绘制出大选中框。
functiongetRectsBBox(...rects:IRect[]):IBox{
if(rects.length===0){
thrownewError('thecountofrectcannotbe0');
}
constminX=Math.min(...rects.map((rect)=>rect.x));
constminY=Math.min(...rects.map((rect)=>rect.y));
constmaxX=Math.max(...rects.map((rect)=>rect.x rect.width));
constmaxY=Math.max(...rects.map((rect)=>rect.y rect.height));
return{
x:minX,
y:minY,
width:maxX-minX,
height:maxY-minY,
};
}
这里用的是另一种包围盒子的表达，所以多了一层转换。
interfaceIRect={
x:number;
y:number;
width:number;
height:number;
}
typeIBox=IRect
计算向量夹角
通过旋转控制点旋转图形时，需要通过向量的点积公式来计算移动的夹角，去更新图形的旋转角度。
计算 [x - cx, y - cy] 和 [0, -1] 两个向量夹角的算法实现：
/**
*求向量到右侧轴(x正半轴)的夹角
*范围在[0,Math.PI*2)
*/
exportfunctioncalcVectorRadian(cx:number,cy:number,x:number,y:number){
consta=[x-cx,y-cy];
constb=[0,-1];
constdotProduct=a[0]*b[0] a[1]*b[1];
constd=
Math.sqrt(a[0]*a[0] a[1]*a[1])*Math.sqrt(b[0]*b[0] b[1]*b[1]);
letradian=Math.acos(dotProduct/d);
if(x<cx){
radian=Math.PI*2-radian;
}
returnradian;
}
结尾
做图形编辑器，经常要和几何算法打交道，各种相交判断、居中计算、光标缩放、找最近的参照线等等。
这对算法能力有一定要求的，建议多去刷刷 leetcode。此外就是多画图分析。
在开发中，我们还要自己去分析需求，结合图形编辑器的具体实现，抽离出算法问题，并配合合适的数据结构，去解题。解法可能一次不是最优解， 但我们可以慢慢迭代，慢慢优化的。
虽然有点耗脑细胞，但最后把难题解决，还是非常有成就感。
我是前端西瓜哥，欢迎关注我，学习更多图形编辑器知识。
