问题描述

我正在寻找一种将四边形分割成网格的方法。例如：

最终我需要能够将生成的形状转换为 SVG，但我很乐意处理与另一个库或坐标系之间的转换。我正在寻找的是如何进行计算。

假设该形状是按二次方绘制的四边形状，其中每边可以是凹的或凸的，但没有边缘与其他边缘或自身重叠，并且四个边中的任何一个都可以弯曲。

对于四边多边形（具有直边的形状很简单），同样的方法，如果两个相对的边是直线，很容易找到相交点，因为它们将位于相对边的细分之间绘制的直线上. 从那里可以相对容易地计算将它们连接到沿替代轴的前一个点所需的曲线：

但是，当没有两个直的、相对的边时（如上面的第三个示例），我不确定如何找到这些点，因为不再确定这些点位于一条直线上。

我花了很长时间寻找有记录的方法，但无济于事。

这是一个使用SVG来描述它的起始形状的例子（它不必在SVG中处理，只要我可以输出到SVG。

<svg version="1.1" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" x="0px" y="0px"
     viewBox="0 0 406.4 233.4" xml:space="preserve">
  <path class="st0" d="M394.3,232.7c-106-37.8-353.7,0-353.7,0s-90.4-151.2,0-207.3s353.7,0,353.7,0S420.3,154.7,394.3,232.7z"/>
</svg>

编辑：我在 Stack Exchange Maths 上问了一个类似的问题，其中一个答案描述了一种方法 - 使用Coons Patch。Quora解释在这里。

标签： javascriptsvggridquadraticcubic-bezier

解决方案

您可以在此处查看 Codepen 上的实时示例和完整代码。

数据表示

下图最简单的数据表示使用三次贝塞尔曲线。我相信这也将涵盖您的所有用例。为了不让各种特殊情况污染我们的代码，我们将要求输入始终采用四个后续三次 Bézier 曲线的格式，就像我们绘制它们一样。这意味着我们不能使用：

二次贝塞尔曲线（通过镜像另一个控制点可转换为三次）
段（通过将控制点等距放置在线上的端点之间，可转换为三次贝塞尔曲线）
关闭路径[ ZSVG 命令]（通过计算给定的段然后从那里获取它可以转换为三次贝塞尔曲线）

更多关于 SVG 中的路径主题

它的 SVG 表示

<path d=" M50 50
     C 100 100 400 100 450 50
     C 475 250 475 250 450 450
     C 250 300 250 300 50 450
     C 150 100 150 250 50 50"
 fill="transparent"
 stroke="black"
/>

但是，为方便起见，我们将定义自己的数据结构。

Point只是一个普通的老Vector2D班。

class Point {
  constructor (x, y) {
    this.x = x
    this.y = y
  }
}

Curve是三次贝塞尔曲线。

class Curve {
  constructor (
    startPointX, startPointY,
    controlPointAX, controlPointAY,
    controlPointBX, controlPointBY,
    endPointX, endPointY) {
    this.start = new Point(startPointX, startPointY)
    this.controlA = new Point(controlPointAX, controlPointAY)
    this.controlB = new Point(controlPointBX, controlPointBY)
    this.end = new Point(endPointX, endPointY)
  }

}

Grid只是曲线的容器。

class Grid {
  constructor (topSide, rightSide, bottomSide, leftSide, horizontalCuts, verticalCuts) {
    this.topSide = topSide
    this.rightSide = rightSide
    this.bottomSide = bottomSide
    this.leftSide = leftSide

    // These define how we want to slice our shape. Just ignore them for now
    this.verticalCuts = verticalCuts
    this.horizontalCuts = horizontalCuts
  }
}

让我们用相同的形状填充它。

let grid = new Grid(
  new Curve(50, 50, 100, 100, 400, 100, 450, 50),
  new Curve(450, 50, 475, 250, 475, 250, 450, 450),
  new Curve(450, 450, 250, 300, 250, 300, 50, 450),
  new Curve(50, 450, 150, 100, 150, 250, 50, 50),
  8,
  6
)

寻找交叉点

显然您已经使用该t方法实现了它（而不是真正的曲线拼接长度），所以我把它放在这里只是为了完整性。

请注意，这cuts是您将获得的交点（红点）的实际数量。也就是说，起点和终点不存在（但可以稍作修改cut()）

function cut (cuts, callback) {
  cuts++
  for (let j = 1; j < cuts; j++) {
    const t = j / cuts
    callback(t)
  }
}

class Curve {

// ...

  getIntersectionPoints (cuts) {
    let points = []
    cut(cuts, (t) => {
      points.push(new Point(this.x(t), this.y(t)))
    })
    return points
  }

  x (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.start.x +
            3 * ((1 - t) * (1 - t)) * t * this.controlA.x +
            3 * (1 - t) * (t * t) * this.controlB.x +
            (t * t * t) * this.end.x
  }

  y (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.start.y +
            3 * ((1 - t) * (1 - t)) * t * this.controlA.y +
            3 * (1 - t) * (t * t) * this.controlB.y +
            (t * t * t) * this.end.y
  }
}

寻找分裂曲线

function lerp (from, to, t) {
  return from * (1.0 - t) + (to * t)
}

class Curve {

// ...

  getSplitCurves (cuts, oppositeCurve, fromCurve, toCurve) {
    let curves = []
    cut(cuts, (t) => {
      let start = new Point(this.x(t), this.y(t))
      // NOTE1: We must go backwards
      let end = new Point(oppositeCurve.x(1 - t), oppositeCurve.y(1 - t))
      let controlA = new Point(
        // NOTE2: Interpolate control points
        lerp(fromCurve.controlA.x, toCurve.controlA.x, t),
        lerp(fromCurve.controlA.y, toCurve.controlA.y, t)
      )
      let controlB = new Point(
        // NOTE2: Interpolate control points
        lerp(fromCurve.controlB.x, toCurve.controlB.x, t),
        lerp(fromCurve.controlB.y, toCurve.controlB.y, t)
      )
      curves.push(new Curve(
        start.x, start.y,
        controlA.x, controlA.y,
        controlB.x, controlB.y,
        end.x, end.y
      ))
    })
    return curves
  }
}

上面的代码有一些可疑之处。

NOTE1：由于曲线是按照您绘制它们的顺序表示的，因此相对的两侧朝向不同的方向。例如，顶部是从左到右绘制的，而底部是从右到左绘制的。也许图像会有所帮助：

NOTE2：这就是我们如何获得 Béziers 分割形状的控制点。t在连接对边控制点的线段上进行插值。

这是那些片段。它们的端点是各自曲线的控制点。

这是我们渲染曲线时的最终结果：

您可以在此处查看 Codepen 上的实时示例和完整代码。

从这往哪儿走

分割曲线

找到交点后，您将想要找到它们t发生的位置。你为什么t问？所以你可以分割曲线。

实际最终结果

最后，您需要选择曲线的这些部分并排列它们以表示网格的各个字段。

如您所见，您还有很长的路要走，我只走了一小部分（并且仍然设法写了一个冗长的答案：D）。

javascript - 四面、二维形状的细分