一线大厂高级前端编写,前端初中阶面试题,帮助初学者应聘,需要联系微信:javadudu

给定一个边与边可能相交的多边形,求它的轮廓线

大家好,我是前端西瓜哥。

最近遇到一个需求,给定一个多边形(边与边可能相交),求这个多边形的轮廓线

给定一个边与边可能相交的多边形,求它的轮廓线

需要注意的是,轮廓线多边形内不能有空洞,使用的不是常见的非零绕数规则(nonzero)以及奇偶规则(odd-even)。

整体思路

  1. 计算多边形各边的交点,求出一个有多边形点和交点信息的邻接表。

  2. 从最下方的点开始,找出与其相邻节点中夹角最小的点保存到路径中,不断重复这个行为,直到点又回到起点位置。这里部分借鉴了凸包算法的其中一种叫做 Jarvis步进法 的解法。

原理很简单,就是代码太多,容易写错,需要多调试。

给定一个边与边可能相交的多边形,求它的轮廓线

演示 demo

为了验证算法的正确性,我用 Canvas 写了个的简单交互 demo。

效果演示:

给定一个边与边可能相交的多边形,求它的轮廓线

项目地址:

github.com/F-star/poly…

Demo 地址:

f-star.github.io/polygon-alg…

下面我们看具体实现。

预处理

第一步是预处理。

目标多边形会使用点数组表示,比如:

const points = [
  { x0y0 },
  { x6y0 },
  { x0y10 },
  { x6y10 },
];

然后我们做去重,如果连续的多个点的位置 “相同”,其实就等价于一个,保留一个就好。

不然后面找路径的时候,会出现零向量的计算导致报错。

function dedup(points: Point[]) {
  const newPointsPoint[] = [];
  const size = points.length;
  for (let i = 0; i < size; i++) {
    const p = points[i];
    const nextP = points[(i + 1) % size];
    if (p.x !== nextP.x || p.y !== nextP.y) {
      newPoints.push(p);
    }
  }
  return newPoints;
}

接着我们需要基于这个点数组,计算邻接表。

邻接表是一种表示图(Graph)的数据结构,记录每个点相邻的点有哪些。

下面我们会以这个 “8” 字形多边形为例,进行讲解。

给定一个边与边可能相交的多边形,求它的轮廓线

观察图示,可以得邻接表为:

[
  /* 0 */ [31], // 表示 0 和 3、1 相连
  /* 1 */ [02],
  /* 2 */ [13],
  /* 3 */ [20],
];

求初始邻接表的算法实现为:

// 求多边形的邻接表,size 为多边形点的数量
function getAdjList(size: number) {
  const adjList: number[][] = [];
  for (let i = 0; i < size; i++) {
    const left = i - 1 < 0 ? size - 1 : i - 1;
    const right = (i + 1) % size;
    adjList.push([left, right]);
  }
  return adjList;
}

需要求解的轮廓线多边形的点不一定是目标多边形上的点,也有可能是交点

所以我们首先要做的是 求出目标多边形上的所有交点,并更新邻接表,得到一个额外带有交点信息的多边形邻接表

给定一个边与边可能相交的多边形,求它的轮廓线

我们来看看具体要怎么实现。

求交点以及更新邻接表

这里需要一个求两线段交点的算法。刚好我写过,思路是解二元一次方程组,请看这篇文章:《解析几何:计算两条线段的交点

用法为:

getLineSegIntersection(
  { x1, y1 }, { x4, y4 },
  { x1, y4 }, { x4, y1 }
);
// { x: 2.5, y: 2.5 }

我们需要遍历多边形的所有边,计算其和其他不相邻边的交点。

const size = points.length;

for (let i = 0; i < size - 2; i++) {
  const line1Start = points[i];
  const line1End = points[i + 1];

  let j = i + 2;
  for (; j < size; j++) {
    const line2EndIdx = (j + 1) % size;
    if (i === line2EndIdx) {
      // 相邻点没有计算交点的意义
      continue;
    }
    const line2Start = points[j];
    const line2End = points[line2EndIdx];
    const crossPt = getLineSegIntersection(
      line1Start,
      line1End,
      line2Start,
      line2End
    );
    
    // 找到一个交点
    if (crossPt) {
      // ... 更新邻接表
      // ...
    }
  }
}

为记录新的交点在哪四个点之间,我们要维护一个表。

它的 key 代表某条线段,value 为一个有序数组,记录落在该线段上的点,以及它们到线段起点的距离。该数组按距离从小到排序。

// [某条线][到线起点的距离, 在 points 中的索引值]
// 如:{ '2-3', [[0, 2], [43, 5], [92, 3]] }
const map = new Map<string, [number, number][]>();

线段 1-2 初始化时,表为

{
  ‘1-2’: [
    [01], // 点 1,距离起点 0
    [962], // 点 2,距离起点 96
  ]
}

边 1-2 和 3-0 计算得到一个交点(我们记为点 4)。把交点存到 crossPts 数组中。

接着求交点 4 在 1-2 中距离起点(即点 1)的距离,基于它判断落在 1-2 中哪两个点之间。结果是在点 1 和 点 2 之间,更新这两个点的邻接点数组,将其中的 1 和 2 替换为 5

1: [0, 2] --> 1: [0, 4]
2: [1, 3] --> 2: [4, 3]

最后是更新 map 表:

{
  ‘1-2’: [
    [01], // 点 1,距离起点 0
    [04], // 点 4,距离起点 40
    [962], // 点 2,距离起点 96
  ]
}

另一条相交边 3-0 同理。

代码实现:

// [某条线]: [到线起点的距离, 在 points 中的索引值]
// 如:{ '2-3', [[0, 2], [43, 5], [92, 3]] }
const map = new Map<string, [number, number][]>();
const crossPtsPoint[] = [];
const size = points.length;

// ...
if (crossPt) {
  crossPts.push(crossPt);

  const crossPtAdjPoints: number[] = [];
  const crossPtIdx = size + crossPts.length - 1;

  /************ 计算 line1Dist 并更新 line1 两个点对应的邻接表 ********/
  {
    const line1Key = `${i}-${i + 1}`;
    if (!map.has(line1Key)) {
      map.set(line1Key, [
        [0, i],
        [distance(line1Start, line1End), i + 1],
      ]);
    }
    const line1Dists = map.get(line1Key)!;
    // 计算相对 line1Start 的距离
    const crossPtDist = distance(line1Start, crossPt);
    // 看看在哪两个点中间
    const [_left, _right] = getRange(
      line1Dists.map((item) => item[0]),
      crossPtDist
    );

    const left = line1Dists[_left][1];
    const right = line1Dists[_right][1];
    crossPtAdjPoints.push(left, right);

    // 更新邻接表
    const line1StartAdjPoints = adjList[left];
    replaceIdx(line1StartAdjPoints, left, crossPtIdx);
    replaceIdx(line1StartAdjPoints, right, crossPtIdx);

    const line1EndAdjPoints = adjList[right];
    replaceIdx(line1EndAdjPoints, left, crossPtIdx);
    replaceIdx(line1EndAdjPoints, right, crossPtIdx);

    // 更新 map[line1Key] 数组
    line1Dists.splice(_right, 0, [crossPtDist, crossPtIdx]);
  }
  /************ 计算 line2Dist 并更新 line2 两个点对应的邻接表 ********/
  {
    const line2Key = `${j}-${line2EndIdx}`;
    // ...这里和上面一样的,读者感兴趣可以把这两段代码复用为一个方法
  }

  // 更新邻接表
  adjList.push(crossPtAdjPoints);
}

步进法找路径

上面我们得到了带交点的多边形邻接表,必要的点的数据都准备好了,下一步就是一从一个点出发走出一条多边形的路径。

(1)取左下角点作为起点

找顶点(不包括交点)中最靠下的点,如果有多个,取最靠左的。这个点一定是轮廓多边形的一个点。

(2)步进,取角度最小的邻接点为路径的下一个点

计算当前点到上一个点的向量,和当前点到其他邻接点相邻点向量逆时针夹角。找出其中夹角最小的邻接点,作为下一个点,不断步进,直到当前点为路径起点。

对于起点,它没有前一个点,用一个向右向量  (1, 0) 参与计算。

给定一个边与边可能相交的多边形,求它的轮廓线

const allPoints = [...points, ...crossPts];

// 1. 找到最下边的点,如果有多个 y 相同的点,取最左边的点
let bottomPoint = points[0];
let bottomIndex = 0;
for (let i = 1; i < points.length; i++) {
  const p = points[i];
  if (p.y > bottomPoint.y || (p.y === bottomPoint.y && p.x < bottomPoint.x)) {
    bottomPoint = p;
    bottomIndex = i;
  }
}

const outlineIndices = [bottomIndex];

// 2. 遍历,找逆时针的下一个点
const MAX_LOOP = 9999;
for (let i = 0; i < MAX_LOOP; i++) {
  const prevIdx = outlineIndices[i - 1];
  const currIdx = outlineIndices[i];
  const prevPt = allPoints[prevIdx];
  const currPt = allPoints[currIdx];
  const baseVector =
    i == 0
      ? { x1y0 } // 对于起点,它没有前一个点,用向右的向量
      : {
          x: prevPt.x - currPt.x,
          y: prevPt.y - currPt.y,
        };

  const adjPtIndices = adjList[outlineIndices[i]];

  let minRad = Infinity;
  let minRadIdx = -1;
  for (const index of adjPtIndices) {
    if (index === prevIdx) {
      continue;
    }
    const p = allPoints[index];
    const rad = getVectorRadian(currPt.x, currPt.y, p.x, p.y, baseVector);
    if (rad < minRad) {
      minRad = rad;
      minRadIdx = index;
    }
  }

  if (minRadIdx === outlineIndices[0]) {
    break// 回到了起点,结束
  }

  outlineIndices.push(minRadIdx);
}
if (outlineIndices.length >= MAX_LOOP) {
  console.error(`轮廓多边形计算失败,超过最大循环次数 ${MAX_LOOP}`);
}

// outlineIndices 为我们需要的轮廓线多边形

这里有个求两向量夹角的方法要实现,这里不具体展开了。

简单来说就是通过点积公式计算夹角,但夹角只在 0 到 180 之间,这里需要再利用叉积的特性判断顺时针还是逆时针,将顺时针的夹角用 360 减去。

结尾

算法的整体思路大概就是这样。

这里有几个优化点。

首先判断大小的场景可进行优化,比如求距离时使用了开方,其实没必要开方。

因为 a^2 < b^2 是可以推导出 a < b 的,所以可直接对比距离的平方,我这里是为了让读者方便理解,故意简化了。对比夹角的大小同理,可改为对比投影加夹角方向。

此外还有一些边缘情况没有测试和处理。

比如多个交点的位置是 “相同” 的,最好做一个合并操作(否则在一些非常特定的场景可能会有问题)。

我是前端西瓜哥,欢迎关注我,学习更多平面解析几何知识。


相关阅读,

解析几何:计算两条线段的交点

几何算法:判断两条线段是否相交

图形编辑器开发:一些会用到的简单几何算法

几何算法:矩形碰撞和包含检测算法

在容器内显示图片的五种方案:contain、cover、fill、none、scale-down

计算机图形学:变换矩阵

求向量的角度

原文链接:https://juejin.cn/post/7327478228188987418 作者:前端西瓜哥

(0)
上一篇 2024年1月24日 下午5:13
下一篇 2024年1月25日 上午10:05

相关推荐

发表评论

登录后才能评论