路径高级操作进阶：性能优化与企业实践 ​

/**
 * 非零绕回规则的精确实现
 * @param {Array} vertices - 路径顶点数组 [{x, y}, ...]
 * @param {Object} point - 待测点 {x, y}
 * @returns {boolean} - 点是否在路径内
 */
function isPointInPathNonZero(vertices, point) {
  let windingNumber = 0;
  const n = vertices.length;
  
  for (let i = 0; i < n; i++) {
    const v1 = vertices[i];
    const v2 = vertices[(i + 1) % n];
    
    // 计算射线与边的交叉
    if (v1.y <= point.y) {
      if (v2.y > point.y) {  // 向上穿越
        if (isLeft(v1, v2, point) > 0) {
          windingNumber++;
        }
      }
    } else {
      if (v2.y <= point.y) {  // 向下穿越
        if (isLeft(v1, v2, point) < 0) {
          windingNumber--;
        }
      }
    }
  }
  
  return windingNumber !== 0;
}

/**
 * 计算点相对于直线的位置
 * 返回值 > 0: 点在直线左侧（逆时针）
 * 返回值 < 0: 点在直线右侧（顺时针）
 * 返回值 = 0: 点在直线上
 */
function isLeft(p1, p2, point) {
  return (p2.x - p1.x) * (point.y - p1.y) - 
         (point.x - p1.x) * (p2.y - p1.y);
}

/**
 * 奇偶规则的实现
 * @param {Array} vertices - 路径顶点数组
 * @param {Object} point - 待测点
 * @returns {boolean} - 点是否在路径内
 */
function isPointInPathEvenOdd(vertices, point) {
  let crossings = 0;
  const n = vertices.length;
  
  for (let i = 0; i < n; i++) {
    const v1 = vertices[i];
    const v2 = vertices[(i + 1) % n];
    
    // 检查射线与边是否相交
    if ((v1.y > point.y) !== (v2.y > point.y)) {
      // 计算交点的 x 坐标
      const intersectX = v1.x + (point.y - v1.y) * (v2.x - v1.x) / (v2.y - v1.y);
      
      if (point.x < intersectX) {
        crossings++;
      }
    }
  }
  
  return crossings % 2 === 1;
}

/**
 * 心形路径的 SVG 语法
 */
const heartPath = new Path2D(
  // 移动到顶部中心
  'M 50 30 ' +
  // 左侧曲线（三次贝塞尔曲线）
  'C 50 20, 40 10, 30 10 ' +
  'C 15 10, 10 20, 10 30 ' +
  'C 10 45, 20 55, 50 80 ' +
  // 右侧曲线
  'C 80 55, 90 45, 90 30 ' +
  'C 90 20, 85 10, 70 10 ' +
  'C 60 10, 50 20, 50 30 ' +
  // 闭合
  'Z'
);

ctx.fillStyle = '#e74c3c';
ctx.fill(heartPath);

/**
 * 简化的 SVG 路径解析器
 * 仅支持 M, L, C, Z 命令
 */
class SVGPathParser {
  constructor(pathString) {
    this.pathString = pathString;
    this.vertices = [];
    this.commands = [];
  }
  
  parse() {
    // 移除多余空格和逗号
    const normalized = this.pathString
      .replace(/,/g, ' ')
      .replace(/([MLCZmlcz])/g, ' $1 ')
      .trim();
    
    const tokens = normalized.split(/\s+/).filter(t => t);
    
    let currentX = 0, currentY = 0;
    let i = 0;
    
    while (i < tokens.length) {
      const command = tokens[i];
      
      switch (command) {
        case 'M':
          currentX = parseFloat(tokens[i + 1]);
          currentY = parseFloat(tokens[i + 2]);
          this.vertices.push({ x: currentX, y: currentY });
          this.commands.push({ type: 'moveTo', x: currentX, y: currentY });
          i += 3;
          break;
          
        case 'L':
          currentX = parseFloat(tokens[i + 1]);
          currentY = parseFloat(tokens[i + 2]);
          this.vertices.push({ x: currentX, y: currentY });
          this.commands.push({ type: 'lineTo', x: currentX, y: currentY });
          i += 3;
          break;
          
        case 'C': {
          const cp1x = parseFloat(tokens[i + 1]);
          const cp1y = parseFloat(tokens[i + 2]);
          const cp2x = parseFloat(tokens[i + 3]);
          const cp2y = parseFloat(tokens[i + 4]);
          currentX = parseFloat(tokens[i + 5]);
          currentY = parseFloat(tokens[i + 6]);
          
          this.commands.push({
            type: 'bezierCurveTo',
            cp1x, cp1y, cp2x, cp2y,
            x: currentX, y: currentY
          });
          
          // 简化：只记录终点
          this.vertices.push({ x: currentX, y: currentY });
          i += 7;
          break;
        }
          
        case 'Z':
        case 'z':
          this.commands.push({ type: 'closePath' });
          i++;
          break;
          
        default:
          console.warn('Unsupported command:', command);
          i++;
      }
    }
    
    return {
      vertices: this.vertices,
      commands: this.commands
    };
  }
  
  /**
   * 计算路径的包围盒
   */
  getBoundingBox() {
    if (this.vertices.length === 0) return null;
    
    let minX = Infinity, minY = Infinity;
    let maxX = -Infinity, maxY = -Infinity;
    
    this.vertices.forEach(v => {
      minX = Math.min(minX, v.x);
      minY = Math.min(minY, v.y);
      maxX = Math.max(maxX, v.x);
      maxY = Math.max(maxY, v.y);
    });
    
    return { minX, minY, maxX, maxY, width: maxX - minX, height: maxY - minY };
  }
}

// 使用示例
const parser = new SVGPathParser('M 10 10 L 50 10 L 50 50 Z');
const result = parser.parse();
console.log('顶点:', result.vertices);
console.log('命令:', result.commands);

const bbox = parser.getBoundingBox();
console.log('包围盒:', bbox);
// 输出: { minX: 10, minY: 10, maxX: 50, maxY: 50, width: 40, height: 40 }

/**
 * 路径缓存管理器
 */
class PathCache {
  constructor() {
    this.cache = new Map();
    this.stats = {
      hits: 0,
      misses: 0
    };
  }
  
  /**
   * 获取或创建路径
   * @param {string} key - 缓存键
   * @param {Function} factory - 路径创建函数
   */
  getOrCreate(key, factory) {
    if (this.cache.has(key)) {
      this.stats.hits++;
      return this.cache.get(key);
    }
    
    this.stats.misses++;
    const path = factory();
    this.cache.set(key, path);
    return path;
  }
  
  /**
   * 清除缓存
   */
  clear() {
    this.cache.clear();
  }
  
  /**
   * 获取缓存统计
   */
  getStats() {
    const total = this.stats.hits + this.stats.misses;
    const hitRate = total > 0 ? (this.stats.hits / total * 100).toFixed(2) : 0;
    return {
      ...this.stats,
      total,
      hitRate: `${hitRate}%`,
      cacheSize: this.cache.size
    };
  }
}

// 使用示例
const pathCache = new PathCache();

// 绘制 1000 个星星
for (let i = 0; i < 1000; i++) {
  const star = pathCache.getOrCreate('star-5', () => {
    const path = new Path2D();
    // 复杂的星形路径创建逻辑
    // ...
    return path;
  });
  
  ctx.save();
  ctx.translate(Math.random() * 800, Math.random() * 600);
  ctx.fill(star);
  ctx.restore();
}

console.log('缓存统计:', pathCache.getStats());
// 输出: { hits: 999, misses: 1, total: 1000, hitRate: "99.90%", cacheSize: 1 }

/**
 * Ramer-Douglas-Peucker 路径简化算法
 * @param {Array} points - 原始顶点数组
 * @param {number} epsilon - 容差值（越大越简化）
 * @returns {Array} - 简化后的顶点数组
 */
function simplifyPath(points, epsilon = 1.0) {
  if (points.length <= 2) return points;
  
  // 找到距离首尾连线最远的点
  let maxDistance = 0;
  let maxIndex = 0;
  const first = points[0];
  const last = points[points.length - 1];
  
  for (let i = 1; i < points.length - 1; i++) {
    const distance = perpendicularDistance(points[i], first, last);
    if (distance > maxDistance) {
      maxDistance = distance;
      maxIndex = i;
    }
  }
  
  // 如果最大距离大于容差，递归简化
  if (maxDistance > epsilon) {
    const left = simplifyPath(points.slice(0, maxIndex + 1), epsilon);
    const right = simplifyPath(points.slice(maxIndex), epsilon);
    return left.slice(0, -1).concat(right);
  } else {
    return [first, last];
  }
}

/**
 * 计算点到直线的垂直距离
 */
function perpendicularDistance(point, lineStart, lineEnd) {
  const dx = lineEnd.x - lineStart.x;
  const dy = lineEnd.y - lineStart.y;
  
  const norm = Math.sqrt(dx * dx + dy * dy);
  if (norm === 0) return Math.hypot(point.x - lineStart.x, point.y - lineStart.y);
  
  return Math.abs(
    dy * point.x - dx * point.y + lineEnd.x * lineStart.y - lineEnd.y * lineStart.x
  ) / norm;
}

// 使用示例
const originalPath = [
  { x: 0, y: 0 },
  { x: 1, y: 1 },
  { x: 2, y: 0.5 },
  { x: 3, y: 1 },
  { x: 4, y: 0 },
  { x: 5, y: 1 },
  { x: 6, y: 0 },
  { x: 7, y: 0.5 },
  { x: 8, y: 0 },
  { x: 9, y: 1 },
  { x: 10, y: 0 }
];

const simplified = simplifyPath(originalPath, 1.0);
console.log('原始顶点数:', originalPath.length);  // 11
console.log('简化后顶点数:', simplified.length);  // 3-5（取决于 epsilon）

// 绘制对比
function drawPath(ctx, points, color, y) {
  ctx.strokeStyle = color;
  ctx.lineWidth = 2;
  ctx.beginPath();
  ctx.moveTo(points[0].x * 20, points[0].y * 20 + y);
  points.forEach(p => ctx.lineTo(p.x * 20, p.y * 20 + y));
  ctx.stroke();
}

drawPath(ctx, originalPath, '#e74c3c', 50);    // 红色：原始路径
drawPath(ctx, simplified, '#3498db', 150);     // 蓝色：简化路径

/**
 * 路径渲染缓存器
 */
class PathRenderCache {
  constructor() {
    this.cache = new Map();
  }
  
  /**
   * 渲染路径到离屏 Canvas 并缓存
   */
  renderPath(key, path, width, height, renderFn) {
    if (!this.cache.has(key)) {
      const offscreen = document.createElement('canvas');
      offscreen.width = width;
      offscreen.height = height;
      const offCtx = offscreen.getContext('2d');
      
      renderFn(offCtx, path);
      
      this.cache.set(key, offscreen);
    }
    
    return this.cache.get(key);
  }
  
  /**
   * 绘制缓存的路径
   */
  drawCached(ctx, key, x, y) {
    const cached = this.cache.get(key);
    if (cached) {
      ctx.drawImage(cached, x, y);
      return true;
    }
    return false;
  }
}

// 使用示例
const renderCache = new PathRenderCache();

// 创建复杂路径（如 logo）
const complexPath = new Path2D(/* SVG 路径 */);

// 第一次渲染：缓存到离屏 Canvas
renderCache.renderPath('logo', complexPath, 200, 200, (ctx, path) => {
  ctx.fillStyle = '#3498db';
  ctx.fill(path);
  ctx.strokeStyle = '#2c3e50';
  ctx.lineWidth = 2;
  ctx.stroke(path);
});

// 后续绘制：直接使用缓存的位图
for (let i = 0; i < 100; i++) {
  renderCache.drawCached(ctx, 'logo', i * 50, 100);
}

/**
 * Figma 风格的分层路径缓存
 */
class FigmaStylePathCache {
  constructor() {
    this.pathCache = new Map();        // Path2D 对象缓存
    this.renderCache = new Map();      // 渲染结果缓存（离屏 Canvas）
    this.geometryCache = new Map();    // 几何数据缓存（顶点、包围盒）
  }
  
  /**
   * Level 1: 几何数据缓存
   */
  getGeometry(shapeId, factory) {
    if (!this.geometryCache.has(shapeId)) {
      this.geometryCache.set(shapeId, factory());
    }
    return this.geometryCache.get(shapeId);
  }
  
  /**
   * Level 2: Path2D 对象缓存
   */
  getPath(shapeId, geometryFactory) {
    if (!this.pathCache.has(shapeId)) {
      const geometry = this.getGeometry(shapeId, geometryFactory);
      const path = this.geometryToPath(geometry);
      this.pathCache.set(shapeId, path);
    }
    return this.pathCache.get(shapeId);
  }
  
  /**
   * Level 3: 渲染结果缓存
   */
  getRenderResult(shapeId, width, height, renderFn) {
    const cacheKey = `${shapeId}_${width}_${height}`;
    
    if (!this.renderCache.has(cacheKey)) {
      const offscreen = new OffscreenCanvas(width, height);
      const ctx = offscreen.getContext('2d');
      renderFn(ctx);
      this.renderCache.set(cacheKey, offscreen);
    }
    
    return this.renderCache.get(cacheKey);
  }
  
  geometryToPath(geometry) {
    const path = new Path2D();
    geometry.commands.forEach(cmd => {
      switch (cmd.type) {
        case 'moveTo':
          path.moveTo(cmd.x, cmd.y);
          break;
        case 'lineTo':
          path.lineTo(cmd.x, cmd.y);
          break;
        case 'bezierCurveTo':
          path.bezierCurveTo(cmd.cp1x, cmd.cp1y, cmd.cp2x, cmd.cp2y, cmd.x, cmd.y);
          break;
        case 'closePath':
          path.closePath();
          break;
      }
    });
    return path;
  }
  
  /**
   * 智能失效：只清除受影响的缓存
   */
  invalidate(shapeId) {
    this.geometryCache.delete(shapeId);
    this.pathCache.delete(shapeId);
    
    // 清除所有相关的渲染缓存
    for (const [key, value] of this.renderCache.entries()) {
      if (key.startsWith(shapeId + '_')) {
        this.renderCache.delete(key);
      }
    }
  }
}

/**
 * 虚拟化路径渲染器
 */
class VirtualizedPathRenderer {
  constructor(viewport) {
    this.viewport = viewport;
    this.spatialIndex = new RBush();  // R-Tree 空间索引
    this.paths = [];
  }
  
  addPath(id, path, bounds) {
    const item = {
      id,
      path,
      minX: bounds.x,
      minY: bounds.y,
      maxX: bounds.x + bounds.width,
      maxY: bounds.y + bounds.height
    };
    
    this.spatialIndex.insert(item);
    this.paths.push(item);
  }
  
  render(ctx) {
    // 查询可见区域内的路径
    const visibleBounds = this.viewport.getVisibleBounds();
    const visiblePaths = this.spatialIndex.search(visibleBounds);
    
    console.log(`渲染 ${visiblePaths.length} / ${this.paths.length} 个路径`);
    
    // 只渲染可见路径
    visiblePaths.forEach(item => {
      ctx.fill(item.path);
    });
  }
}

// 性能对比（10000 个路径，只有 50 个可见）
// 全局渲染：~450ms
// 虚拟化渲染：~8ms（56倍提升）⭐