平面几何：求内接或外切于圆的正多边形

前端西瓜哥

发布于 2024-04-03 20:26:21

930

发布于 2024-04-03 20:26:21

文章被收录于专栏：前端西瓜哥的前端文章前端西瓜哥的前端文章

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

如题，今天来看两个算法实现。

求和圆内接的正多边形

方法参数有：

center：圆心位置；
start：正多边形上的一个点，和 center 的距离即圆的半径；
count：多边形边数。

返回值为多边形上连续的点数组。

思路是，让起点基于圆心旋转 PI * 2 / count 度数的倍数，执行 count - 1 次，拿到所有的点。

算法实现：

/**
 * 计算和圆内接的正多边形
 * @param center 圆心
 * @param start 起点
 * @param count 边数
 */
export const getInternalTanRegularPolygon = (
  center: Point,
  start: Point,
  count: number,
) => {
  const points: Point[] = [{ ...start }];
  const step = (Math.PI * 2) / count;
  for (let i = 1; i < count; i++) {
    points.push(rotate(start, center, step * i));
  }
  return points;
};

这里用到一个辅助方法 rotate：计算一个点以另一个点为旋转中心，旋转特定弧度后的点。

const rotate = (p: Point, center: Point, rad: number) => {
  const dx = p.x - center.x;
  const dy = p.y - center.y;
  const cos = Math.cos(rad);
  const sin = Math.sin(rad);
  return {
    x: center.x + dx * cos - dy * sin,
    y: center.y + dx * sin + dy * cos,
  };
};

上面这个写法是很朴实的解析几何推导出来的。

或者用矩阵的方式表达，可读性更好，但通常需要引入一个矩阵库，下面是 pixi.js 的写法：

const rotate = (p: Point, center: Point, rad: number) => {
  const matrix = new Matrix()
    .translate(-center.x, -center.y) // (3) 坐标轴回到原来位置
    .rotate(rad) // (2) 旋转
    .translate(center.x, center.y); // (1) 坐标轴原点移动到 center

  return matrix.apply(p);
};

这里所有的点都是基于起点 start 旋转不同的度数得到的。

也可以基于旋转后的点，继续旋转，这样可以复用旋转矩阵，计算量会少一点。

二者的结果不完全相同，因为各自的实现有各自的误差，但很小，可以忽略不计。

求和圆外切的正多边形

外切要求的效果如下，start 为多边形其中一边的中点，其他同上。

思路是计算一个新的起点 start，然后应用前的的外切方法。

首先 start 基于 center 旋转 PI / count 。

然后计算 外切时半径 和 距离<center, start> 的比值 t，为 1 / cos(PI / count)

基于 t 使用 线性插值，计算出外切时的 start。

如果你不知道线性插值是什么，可以看我的这篇文章：《平面几何算法：求点到直线和圆的最近点》

算法实现：

/**
 * 计算和圆外切的正多边形
 * @param center 圆心
 * @param start 起点
 * @param count 边数
 */
export const getExternalTanRegularPolygon = (
  center: Point,
  start: Point,
  count: number,
) => {
  // 转换为内接多边形，计算新的 start
  const offsetAngle = Math.PI / count;
  start = rotate(start, center, offsetAngle);
  const t = 1 / Math.cos(offsetAngle);
  start = {
    x: center.x + (start.x - center.x) * t,
    y: center.y + (start.y - center.y) * t,
  };

  return getInternalTanRegularPolygon(center, start, count);
};