多边形裁剪：polygon-clipping

Aditya2025-01-10图像渲染相关PolygonClipping 萨瑟兰-霍奇曼算法

引子

最近接手的需求和多边形裁剪相关，主要用了 polygon-clipping 这个JS库，这里简单记录一下该库方法用法及开发遇到的问题也简单了解了下萨瑟兰-霍奇曼算法实现原理，看过就忘。

polygon-clipping

该库总共有4个方法，可以实现多边形的 并集 (union)、交集 (intersection)、差集 (difference) 和 异或 (xor) 操作。

const polygonClipping = require('polygon-clipping')

const poly1 = [[[0,0],[2,0],[0,2],[0,0]]]
const poly2 = [[[-1,0],[1,0],[0,1],[-1,0]]]

polygonClipping.union       (poly1, poly2 /* , poly3, ... */)
polygonClipping.intersection(poly1, poly2 /* , poly3, ... */)
polygonClipping.xor         (poly1, poly2 /* , poly3, ... */)
polygonClipping.difference  (poly1, poly2 /* , poly3, ... */)

业务使用

这里主要通过绘制多边形与圆环内部交集增加、擦除病灶功能

添加

这里的实现思路分两种情况

一种是在添加不存在病灶，即先算添加轮廓（简称drawedRoi）与外圆（circle1）的交集（intersection）区域，然后再取上述结果与内圆（circle2）的差集（difference）即可；
另一种情况是已经存在了若干病灶，那么算添加轮廓（简称drawedRoi）与外圆（circle1）的交集（intersection）区域后要再算已存在轮廓的并集，然后再取上述结果与内圆（circle2）的差集（difference）即可。

import { union, difference, intersection } from "polygon-clipping"

const finalRoiArr = []
const circle1 = [...]
const circle2 = [...]                 

if(!finalRoiArr.length) finalRoiArr = intersection([drawedRoi], [circle1]);
else finalRoiArr = union(finalRoiArr, intersection([drawedRoi], [circle1]));

finalRoiArr = difference(finalRoiArr, [circle2])

擦除

擦除的实现主要求两个差集，一个是与已存在病灶的差集，一个是与外圆的差集。

...

finalRoiArr = difference(difference(finalRoiArr, [drawedRoi]), [circle2])

绘制镂空情况

擦除情况下，在圆环内部擦除一个多边形，这就导致出现镂空情况，按照已存在绘制方式，是不支持这种结构，所以在计算时要忽略这种情况。

if (type === "add") {
    if(!finalRoiArr.length) finalRoiArr = intersection([drawedRoi], [circle1]);
    else finalRoiArr = union(finalRoiArr, intersection([drawedRoi], [circle1]));

    finalRoiArr = difference(finalRoiArr, [circle2])
    for (let i = 0; i < finalRoiArr.length; i++) {
      if (finalRoiArr[0]) finalRoiArr[0] = [finalRoiArr[0][0]];
    }
} else if (type === 'eraser') {
  	const curves = difference(difference(finalRoiArr, [drawedRoi]), [circle2])
    // 特别处理：暂时不支持镂空的情况，只保留外轮廓
    // curves[0] = curves[0] ? [curves[0][0]] : []
  	finalRoiArr = curves;
    for (let i = 0; i < finalRoiArr.length; i++) {
      if (finalRoiArr[0]) finalRoiArr[0] = [finalRoiArr[0][0]];
    }
}

排除

排除跟擦除实现大致一样，但不同点在于排除工具会记录排除轮廓，不会直接修改 finalRoiArr，只是在渲染的时候再 "擦除" 掉排除轮廓区域

有交集的轮廓自动合并

const mergeExcludeOutline = (drawedRoi) => {
    const roi = {
      id: uuidv4(),
      sliceIndex: state.sliceIndex,
      edge: drawedRoi,
      type: state.measureMethod.value
    };

    if (state.excludeGreyArea.length === 0) {
      // 如果没有已有多边形，直接添加
      state.excludeGreyArea.push(roi);
    } else {
      let mergedEdges = [drawedRoi];
      const intersectingIndices = [];

      // 查找所有与 drawedRoi 有交集的多边形索引
      state.excludeGreyArea.forEach((item, index) => {
        if (state.sliceIndex === item.sliceIndex && state.measureMethod.value === item.type) {
          const intersected = intersection([item.edge], [drawedRoi]);
          if (intersected && intersected.length > 0) {
            intersectingIndices.push(index);
          }
        }
      });

      if (intersectingIndices.length > 0) {
        // 合并所有有交集的多边形
        intersectingIndices.forEach((index) => {
          mergedEdges = union(mergedEdges, [state.excludeGreyArea[index].edge]);
        });

        // 移除旧的交集多边形
        intersectingIndices.reverse().forEach((index) => {
          state.excludeGreyArea.splice(index, 1);
        });

        // 添加合并后的新多边形
        state.excludeGreyArea.push({
          id: uuidv4(),
          sliceIndex: state.sliceIndex,
          edge: mergedEdges[0][0], // 取合并结果的主多边形
          type: state.measureMethod.value
        });
      } else {
        // 没有交集，直接添加
        state.excludeGreyArea.push(roi);
      }
    }
  }

轮廓删除

这里主要涉及点击排除轮廓后能够精准选中该轮廓

// 点击排除轮廓触发菜单
  const handleOutlineMouseDown = (e) => {
    const imageId = e.detail.image?.imageId;
      if (!imageId) return console.log('>>>imageId is null');
      if (imageId.includes('http')) return

      // 判断坐标是否在多边形内
      const currentRois = state.excludeGreyArea.filter(i => i.sliceIndex === state.sliceIndex && state.measureMethod.value === i.type)
      const point = e.detail.currentPoints.image
      state.selectNodeId.value = currentRois.find(i => isPointInSection([point.x, point.y], i.edge));
      console.log("selectNodeId", state.selectNodeId.value)
  }

  const removeOutline = () => {
    const idx = state.excludeGreyArea.findIndex(i => {
        return  state.sliceIndex === i.sliceIndex && i.id === state.selectNodeId.value.id
      })
      state.excludeGreyArea.splice(idx, 1)
      state.selectNodeId.value = null;
  }
  
  /**
 * 判断当前点击的点是否在当前轮廓内
 * 判断方法为：
 *  1、目标点和远端的一点连成线段
 *  2、使用目标线段和目标曲线求交点
 *  3、交点个数为偶数则点在区域外，否则点在区域内
 * @param point
 * @param points
 */
export function isPointInSection(point: Point, points: Array<Point>): boolean {
  const x = point[0];
  const y = point[1];
  let inside = false;
  for (let i = 0, j = points.length - 1; i < points.length; j = i++) {
    const xi = points[i][0],
      yi = points[i][1];
    const xj = points[j][0],
      yj = points[j][1];
    const intersect = yi > y !== yj > y && x < ((xj - xi) * (y - yi)) / (yj - yi) + xi;
    if (intersect) inside = !inside;
  }
  return inside;
}

这里踩坑比较严重的问题是单个排除轮廓能正常擦除，多个排除轮廓擦除异常。最后定位到是传参问题，difference 接收的参数都是类似 [[[0,0],[2,0],[0,2],[0,0]]] 这种三维数组，因为要处理镂空情况，将 difference 结果进行处理了，导致后面再进行擦除的时候，传参进去变成了 [[0,0],[2,0],[0,2],[0,0]]，一开始真没注意这种问题，卡了许久。

	const excludeRois = state.excludeGreyArea.filter(i => i.sliceIndex === state.sliceIndex && i.type === state.measureMethod.value)	
	if (arr.length !== 0 && excludeRois.length > 0) {
    for (let i = 0; i < arr.length; i++) {
      if (arr[i]) arr[i] = [arr[i]]
    }
    excludeRois.forEach((item, idx) => {
      arr = diffExcludeEdge(arr, item, idx)
    })
    // 特别处理：暂时不支持镂空的情况，只保留外轮廓
    // curves[0] = curves[0] ? [curves[0][0]] : []
    for (let i = 0; i < arr.length; i++) {
      if (arr[i]) arr[i] = arr[i][0];
    }
  }
  console.log(arr)

  state.finalRoiArr = [arr];

	const diffExcludeEdge = (edge, roi, idx) => {
    let curves = difference(difference(edge, [roi.edge]), [opt.filterRing.circle2])
    

    return curves;
  }

多边形裁剪：polygon-clipping

ON THIS PAGE