通过凸包算法简化svg碰撞检测

在前端图形交互、游戏开发、数据可视化等场景中，SVG元素的碰撞检测是高频需求。但复杂的SVG路径（如包含贝塞尔曲线、圆弧或大量顶点的形状）直接进行碰撞检测，计算复杂度高、性能开销大。

凸包（Convex Hull）算法是解决这一问题的核心方案：它能将任意复杂的SVG形状，简化为包围该形状的“最小凸多边形”，在保留碰撞检测核心边界的同时，大幅减少顶点数量，显著提升碰撞检测效率。

本文将完整梳理从「SVG形状/路径转坐标点集」→「凸包算法简化顶点」→「生成简化多边形」→「碰撞检测实现」的全流程，并提供实用工具与代码示例。

一、SVG路径/形状转坐标点集

要使用凸包算法，首先需要将SVG的<path>、<rect>、<circle>等元素，转换为离散的坐标点集（[[x1,y1], [x2,y2], ...]格式）。以下是主流的转换方案：

方案一：path-to-polygon（在线快速转换）

官方地址：https://betravis.github.io/shape-tools/path-to-polygon/
这是一款轻量的在线工具，专门用于将SVG路径转换为适合CSS Shapes或碰撞检测使用的多边形点集。

• 核心功能：支持上传SVG文件或直接粘贴路径数据，可通过divideXBy/divideYBy调整采样密度，通过precision控制坐标精度；
• 输出格式：直接生成CSS polygon()函数格式的点集，如 polygon(0.000 0.000, 100.000 0.000, ...)，也可手动提取为数组格式；
• 适用场景：快速验证、简单形状的一次性转换。

方案二：wilderness-dom-node（代码级转换SVG DOM）

仓库地址：https://github.com/colinmeinke/wilderness-dom-node
这是一个npm库，可直接在代码中将SVG DOM节点转换为结构化的点集（Frame Shape格式），适合工程化项目。

• 核心API：
  • frameShape(node)：将SVG DOM节点转换为包含attributes和points的Frame Shape对象，points数组中每个点包含x/y坐标，以及moveTo标记；
  • plainShapeObject(node)：将SVG DOM节点转换为Plain Shape Object，保留节点的所有HTML属性；
  • node(frameShape) / updateNode(node, frameShape)：支持从Frame Shape反向生成/更新SVG DOM节点。
• 代码示例：

  import { frameShape } from 'wilderness-dom-node';
  
  // 获取SVG元素并转换为点集
  const svgElement = document.getElementById('your-svg-shape');
  const frameData = frameShape(svgElement);
  console.log('转换后的点集：', frameData.points);
  // 输出示例：
  // {
  //   attributes: { fill: 'yellow' },
  //   points: [
  //     { x: 20, y: 20, moveTo: true },
  //     { x: 80, y: 20 },
  //     { x: 80, y: 80 },
  //     { x: 20, y: 80 },
  //     { x: 20, y: 20 }
  //   ]
  // }

方案三：svg-points（SVG形状与点集/路径互转）

仓库地址：https://github.com/colinmeinke/svg-points
这是与wilderness-dom-node配套的库，专注于SVG形状对象、点集、路径字符串（d属性）之间的相互转换。

• 核心API：
  • toPoints(shapeObject)：将SVG形状对象（如{type:'circle', cx:50, cy:50, r:20}）转换为点集；
  • toPath(shapeOrPoints)：将形状对象或点集转换为SVG路径的d属性字符串；
  • valid(shapeObject)：校验SVG形状对象的合法性。
• 代码示例：

  import { toPoints, toPath } from 'svg-points';
  
  // 1. 将圆形形状对象转换为点集
  const circleShape = { type: 'circle', cx: 50, cy: 50, r: 20 };
  const circlePoints = toPoints(circleShape);
  console.log('圆形点集：', circlePoints);
  
  // 2. 将点集转换回SVG路径字符串
  const pathD = toPath(circlePoints);
  console.log('SVG路径：', pathD); // 输出类似 'M50,30A20,20,0,0,1,50,70...'

方案四：PathToPoints（多格式输出在线工具）

仓库地址：https://github.com/Shinao/PathToPoints
这是另一款功能丰富的在线工具，支持从SVG文件提取路径点，或从文本生成路径，提供多种输出格式。

• 核心功能：支持拖拽SVG文件、调整点采样步长、可视化展示提取的点；
• 输出格式：
  • 独立路径点集（分颜色标识）；
  • 所有路径合并点集（用#分隔）；
  • JSON格式（支持元组[[x1,y1],...]或扁平数组[x1,y1,x2,y2,...]）；
• 适用场景：需要多格式点集输出、批量处理SVG路径。

补充：SVG元素统一转Path

如果原始SVG是<rect>、<circle>、<ellipse>等基础元素，可先通过工具统一转换为<path>元素，再进行点集提取：

• 推荐工具：张鑫旭的SVG图形转路径工具 https://www.zhangxinxu.com/sp/path.html
• 使用方法：粘贴SVG元素代码（如<circle cx="150" cy="75" r="60"></circle>），点击转换即可得到对应的<path>元素。

---

二、凸包算法（Convex Hull）计算简化顶点

什么是凸包？

在几何中，凸（Convex） 指形状的所有内角均≤180°，不存在凹陷部分；包（Hull） 指物体的外边界。因此，一组点或一个形状的凸包，是包围这些点/形状的“最紧密拟合凸边界”。

对于复杂的SVG形状，凸包的价值在于：

• 凹形的凸包是包围它的最小凸多边形，顶点数远少于原始形状的离散点；
• 凸多边形的碰撞检测算法复杂度远低于凹多边形，性能提升显著。

主流凸包算法简介

常见的凸包算法包括：

1. Jarvis March（礼品包装算法）：时间复杂度O(nh)（n为输入点数，h为凸包点数），适合凸包点数较少的场景；
2. Graham扫描法：时间复杂度O(n log n)，通过极角排序和栈操作实现，是最常用的通用算法；
3. Chan算法：结合前两者的优化算法，时间复杂度O(n log h)，性能更优。

在前端开发中，我们无需手动实现算法，可直接使用成熟的库。

使用d3-polygon计算凸包

仓库地址：https://www.npmjs.com/package/d3-polygon
d3-polygon是D3.js生态中专注于二维多边形几何操作的轻量库，其中polygonHull方法可快速计算点集的凸包。

• 安装与引入：

  npm install d3-polygon

  <!-- 或通过CDN引入（ES Module） -->
  <script type="module">
    import { polygonHull } from "https://cdn.skypack.dev/d3-polygon@3";
    // ...
  </script>

• 核心API（除凸包外，还支持其他多边形操作）：
  • polygonHull(points)：计算点集的凸包，返回按逆时针排列的凸包顶点数组，若点数少于3个返回null；
  • polygonContains(polygon, point)：判断点是否在多边形内部；
  • polygonArea(polygon)：计算多边形的有向面积；
  • polygonCentroid(polygon)：计算多边形的质心；
  • polygonLength(polygon)：计算多边形的周长。
• 完整代码示例：

  import { polygonHull } from 'd3-polygon';
  
  // 1. 假设我们从SVG转换得到了原始点集（凹形示例）
  const originalPoints = [
    [0, 0], [100, 0], [100, 100], [50, 50], [0, 100]
  ];
  
  // 2. 计算凸包
  const convexHull = polygonHull(originalPoints);
  console.log('原始点集：', originalPoints);
  console.log('简化后的凸包顶点：', convexHull);
  // 输出示例：[[0,0], [100,0], [100,100], [0,100]]（自动剔除了凹陷的[50,50]点）

---

三、生成简化后的SVG多边形

得到凸包顶点后，我们可以将其生成新的SVG <polygon>元素，用于可视化展示或后续碰撞检测。

• 代码示例：

  // 凸包顶点（来自d3-polygon的输出）
  const convexHull = [[0,0], [100,0], [100,100], [0,100]];
  
  // 1. 将顶点数组转换为polygon的points属性字符串
  const pointsString = convexHull.map(point => point.join(',')).join(' ');
  
  // 2. 创建SVG polygon元素
  const svgNS = "http://www.w3.org/2000/svg";
  const polygonElement = document.createElementNS(svgNS, "polygon");
  polygonElement.setAttribute("points", pointsString);
  polygonElement.setAttribute("fill", "rgba(0,100,255,0.3)");
  polygonElement.setAttribute("stroke", "#0066ff");
  polygonElement.setAttribute("stroke-width", "2");
  
  // 3. 插入到SVG容器中
  const svgContainer = document.getElementById('your-svg-container');
  svgContainer.appendChild(polygonElement);

---

四、基于简化多边形的碰撞检测

有了简化的凸多边形，我们就可以高效地实现碰撞检测。核心场景包括「点与多边形的碰撞」和「多边形与多边形的碰撞」。

场景一：点与多边形的碰撞检测

使用d3-polygon的polygonContains方法，可快速判断一个点是否在凸包内部：

import { polygonHull, polygonContains } from 'd3-polygon';

const convexHull = [[0,0], [100,0], [100,100], [0,100]];
const testPoint1 = [50, 50]; // 多边形内部
const testPoint2 = [150, 50]; // 多边形外部

console.log(polygonContains(convexHull, testPoint1)); // 输出：true
console.log(polygonContains(convexHull, testPoint2)); // 输出：false

场景二：多边形与多边形的碰撞检测

对于两个凸多边形的相交检测，可使用polygon-clipping库，它支持多边形的交集、并集、差集运算，可通过判断交集是否存在来检测碰撞。

• 仓库地址：https://www.npmjs.com/package/polygon-clipping
• 代码示例（示意）：

  import polygonClipping from 'polygon-clipping';
  
  const polygonA = [[[0,0], [100,0], [100,100], [0,100]]];
  const polygonB = [[[50,50], [150,50], [150,150], [50,150]]];
  
  // 计算两个多边形的交集
  const intersection = polygonClipping.intersection(polygonA, polygonB);
  
  // 判断是否碰撞：若交集不为空，则发生碰撞
  const isColliding = intersection.length > 0;
  console.log('是否碰撞：', isColliding); // 输出：true

补充：碰撞面积计算

若需要计算碰撞的重叠面积，可结合polygon-clipping的交集结果和d3-polygon的polygonArea方法：

import polygonClipping from 'polygon-clipping';
import { polygonArea } from 'd3-polygon';

// 假设intersection是polygon-clipping返回的交集结果
const intersection = polygonClipping.intersection(polygonA, polygonB);

if (intersection.length > 0) {
  // polygon-clipping返回的是MultiPolygon格式，需提取单个多边形的顶点
  const collidingPolygon = intersection[0][0];
  const collidingArea = Math.abs(polygonArea(collidingPolygon));
  console.log('碰撞重叠面积：', collidingArea);
}

---

相关资料

1. 凸包算法（Convex Hull）原理与OpenCV实现
2. Path to Polygon Converter（在线路径转多边形工具）
3. PathToPoints（SVG路径点提取工具）
4. wilderness-dom-node（SVG DOM节点转点集库）
5. svg-points（SVG形状与点集/路径互转库）
6. SVG图形转路径工具（张鑫旭）
7. d3-polygon（多边形几何操作库）
8. polygon-clipping（多边形布尔运算库）