大家好,简单何我是算法前端西瓜哥。
开发图形编辑器,图形你会经常要解决一些算法问题。编辑本文盘点一些我开发图形编辑器时常用到的器开简单几何算法。
判断两个矩形是简单何否发生碰撞(或者说相交),即两个矩形有重合的算法区域。
常见使用场景:
使用选择工具框选图形(框选策略除了相交,图形还可以用相交或其他方案)。编辑
遍历图形,器开通过判断视口矩形和图形包围盒的简单何矩形碰撞,剔除掉视口外的算法图形渲染操作,提高性能。
export function isRectIntersect2(rect1: IBox2, rect2: IBox2) { return ( rect1.minX <= rect2.maxX && rect1.maxX >= rect2.minX && rect1.minY <= rect2.maxY && rect1.maxY >= rect2.minY );}
关于 IBox2 为包围盒的接口签名:
interface IBox2 { minX: number; minY: number; maxX: number; maxY: number;}
该算法用于判断矩形 1 是否包含矩形 2。
常见使用场景:
使用选择工具框选图形(这次用的是包含策略);
function isRectContain2(rect1: IBox2, rect2: IBox2) { return ( rect1.minX <= rect2.minX && rect1.minY <= rect2.minY && rect1.maxX >= rect2.maxX && rect1.maxY >= rect2.maxY );}
对图形旋转,是一个非常基础的功能。计算旋转后的点是很常见的需求。
常见使用场景:
用到三角函数算法。
const transformRotate = ( x: number, y: number, radian: number, cx: number, cy: number,) => { if (!radian) { return { x, y }; } const cos = Math.cos(radian); const sin = Math.sin(radian); return { x: (x - cx) * cos - (y - cy) * sin + cx, y: (x - cx) * sin + (y - cy) * cos + cy, };}
常见使用场景:
用于实现图形拾取,判断矩形图形或包围盒是否在光标位置上。
function isPointInRect(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 );}
选中多个矩形时,要计算它们组成的大矩形,然后绘制出大选中框。
function getRectsBBox(...rects: IRect[]): IBox { if (rects.length === 0) { throw new Error('the count of rect can not be 0'); } const minX = Math.min(...rects.map((rect) => rect.x)); const minY = Math.min(...rects.map((rect) => rect.y)); const maxX = Math.max(...rects.map((rect) => rect.x + rect.width)); const maxY = Math.max(...rects.map((rect) => rect.y + rect.height)); return { x: minX, y: minY, width: maxX - minX, height: maxY - minY, };}
这里用的是另一种包围盒子的表达,所以多了一层转换。
interface IRect = { x: number; y: number; width: number; height: number;}type IBox = IRect
通过旋转控制点旋转图形时,需要通过向量的点积公式来计算移动的夹角,去更新图形的旋转角度。
计算 [x - cx, y - cy] 和 [0, -1] 两个向量夹角的算法实现:
/** * 求向量到右侧轴(x正半轴)的夹角 * 范围在 [0, Math.PI * 2) */export function calcVectorRadian(cx: number, cy: number, x: number, y: number) { const a = [x - cx, y - cy]; const b = [0, -1]; const dotProduct = a[0] * b[0] + a[1] * b[1]; const d = Math.sqrt(a[0] * a[0] + a[1] * a[1]) * Math.sqrt(b[0] * b[0] + b[1] * b[1]); let radian = Math.acos(dotProduct / d); if (x < cx) { radian = Math.PI * 2 - radian; } return radian;}
做图形编辑器,经常要和几何算法打交道,各种相交判断、居中计算、光标缩放、找最近的参照线等等。
这对算法能力有一定要求的,建议多去刷刷 leetcode。此外就是多画图分析。
在开发中,我们还要自己去分析需求,结合图形编辑器的具体实现,抽离出算法问题,并配合合适的数据结构,去解题。解法可能一次不是最优解, 但我们可以慢慢迭代,慢慢优化的。
虽然有点耗脑细胞,但最后把难题解决,还是非常有成就感。
责任编辑:姜华 来源: 前端西瓜哥 图形编辑器几何算法(责任编辑:休闲)
分期乐提前还款利息的计算方式是怎样的 分期乐分36期可以提前还款吗?
2018年我国共完成造林707.4万公顷 森林抚育851.9万公顷
金通灵(300091.SZ):南通科创未减持公司股份 减持计划期限届满
宝威控股(00024.HK)年度扭亏为盈至540.6万港元 每股基本及摊薄盈利0.11港仙
国务院:部分物品进口税降为13%和20% 促进扩大进口和消费