四面二维形状的细分
Subdivision of Four-Sided, 2D Shape
我正在寻找一种将四边形拆分为网格的方法。例如：
最终我需要能够将生成的形状转换为 SVG，但我很乐意处理 to/from 另一个库或坐标系的转换。我正在寻找的是如何进行计算。
假设该形状是一个四边形绘制的二次方形状，其中每条边都可以是凹的或凸的，但没有边与其他边或它们自身重叠，并且四个边中的任何一个都可以是弯曲的。
四边形的相同方法（具有直边的形状是微不足道的），如果两条相对的边是直线，则很容易找到相交点，因为它们将位于绘制在两边之间的直线上对立面的细分。从那里可以相对容易地计算出将它们连接到沿替代轴的前一点所需的曲线：
然而，当没有两个相对的直边时（如上面的第三个示例），我不确定如何找到这些点，因为不再确定这些点位于一条直线上。
我花了很长时间寻找记录的方法，但无济于事。
下面是那种用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>
编辑：我问了一个类似的问题 question over at Stack Exchange Maths and one of the answers describes one approach - the use of a Coons Patch. Quora explaination here。
您可以在 Codepen here.
上查看实例和完整代码
数据表示
下图最简单的数据表示使用三次贝塞尔曲线。我相信这也将涵盖您的所有用例。为了不让各种特殊情况污染我们的代码，我们将要求输入始终采用四个后续三次贝塞尔曲线的格式，就像我们绘制它们一样。这意味着我们不能使用：
- 二次贝塞尔曲线（通过镜像另一个控制点可转换为立方曲线）
- Segments（通过将控制点等距离地放置在直线的端点之间，可转换为三次贝塞尔曲线）
- 关闭路径 [
Z SVG 命令]（通过计算给定线段然后从那里获取它可转换为三次贝塞尔曲线）
More on the subject of paths in 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.
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
)
寻找交点
显然你已经实现了它 using the t approach (as opposed to true curve splice length) 所以我把它放在这里只是为了完整起见。
注意 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：这就是我们如何获得贝塞尔曲线分割形状的控制点。 t 在连接对边控制点的线段上进行插值。
这是这些片段。它们的端点是各自曲线的控制点。
这是我们渲染曲线时的最终结果：
您可以在 Codepen here.
上查看实例和完整代码
从这里去哪里
更多路口
这显然不是最终结果。我们仍然需要找到生成曲线的交点。然而，找到两条贝塞尔曲线的交点并非易事。
这是bezier3bezier3()的nice Whosebug answer on the topic which will lead you to this neat library that will do the heavy lifting for you (look at the code，你就会明白）
分割曲线
找到交点后，您将要找到at which t they occur. Why t you ask? So you can split the curve。
实际最终结果
最后，您需要选择曲线的那些部分并将它们排列以表示网格的各个字段。
如您所见，您还有很长的路要走，我只走了一小部分（并且仍然设法写了一个冗长的答案：D）。
如果你的四边是三次贝塞尔曲线，来点比较简单的怎么样：
要制作水平分隔线（从上到下），通过插值顶部和底部的控制点制作新的三次贝塞尔曲线：
然后，将左右两边分成相同数量的点..
..并拉伸分隔曲线，使它们连接到这些点：
然后，从左到右执行相同的操作以创建垂直分隔线。
这里是测试不同形状的笔：https://codepen.io/Sphinxxxx/pen/pKddee
重要部分在 BezierWrapper.lerpCurve() 和 BezierWrapper.fitCurve() 中，还有 Bezier class 取自 https://gamedev.stackexchange.com/a/5427 以获得沿曲线均匀分布的点(.samples):
class BezierWrapper {
constructor(controls, sampleCount, classname) {
this.controls = controls;
this.classname = classname;
if(sampleCount) {
function point2obj(p) {
return { x: p[0], y: p[1] };
}
//https://gamedev.stackexchange.com/a/5427
const interpolator = new Bezier(point2obj(controls[0]),
point2obj(controls[1]),
point2obj(controls[2]),
point2obj(controls[3]));
const samples = this.samples = [];
for(let i = 1; i <= sampleCount; i++) {
const t = i / (sampleCount+1);
samples.push([interpolator.mx(t), interpolator.my(t)]);
}
}
}
static lerpCurve(source, target, t) {
function lerpCoord(from, to, t) {
const diffX = to[0] - from[0],
diffY = to[1] - from[1],
lerpX = from[0] + (diffX * t),
lerpY = from[1] + (diffY * t);
return [lerpX, lerpY];
}
const middle = source.map((c, i) => lerpCoord(c, target[i], t));
return middle;
}
static fitCurve(source, start, end) {
function distance(p1, p2) {
const dx = p2[0] - p1[0],
dy = p2[1] - p1[1];
return Math.sqrt(dx*dx + dy*dy);
}
//https://gist.github.com/conorbuck/2606166
function angle(p1, p2) {
const dx = p2[0] - p1[0],
dy = p2[1] - p1[1],
radians = Math.atan2(dy, dx);
return radians;
}
//
function rotate(p, radians) {
const x = p[0],
y = p[1],
cos = Math.cos(radians),
sin = Math.sin(radians);
return [cos*x - sin*y, sin*x + cos*y];
}
const sourceStart = source[0],
sourceEnd = source[3],
scale = distance(start, end)/distance(sourceStart, sourceEnd),
rot = angle(start, end) - angle(sourceStart, sourceEnd);
//Translate, scale and rotate the source control points to make them fit the start and end points:
const sourceNorm = source.map(c => [c[0] - sourceStart[0], c[1] - sourceStart[1]]),
fittedNorm = sourceNorm.map(c => rotate([c[0]*scale, c[1]*scale], rot)),
fitted = fittedNorm.map(c => [c[0] + start[0], c[1] + start[1]]);
return fitted;
}
}
我正在寻找一种将四边形拆分为网格的方法。例如：
最终我需要能够将生成的形状转换为 SVG，但我很乐意处理 to/from 另一个库或坐标系的转换。我正在寻找的是如何进行计算。
假设该形状是一个四边形绘制的二次方形状，其中每条边都可以是凹的或凸的，但没有边与其他边或它们自身重叠，并且四个边中的任何一个都可以是弯曲的。
四边形的相同方法（具有直边的形状是微不足道的），如果两条相对的边是直线，则很容易找到相交点，因为它们将位于绘制在两边之间的直线上对立面的细分。从那里可以相对容易地计算出将它们连接到沿替代轴的前一点所需的曲线：
然而，当没有两个相对的直边时（如上面的第三个示例），我不确定如何找到这些点，因为不再确定这些点位于一条直线上。
我花了很长时间寻找记录的方法，但无济于事。
下面是那种用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>
编辑：我问了一个类似的问题 question over at Stack Exchange Maths and one of the answers describes one approach - the use of a Coons Patch. Quora explaination here。
您可以在 Codepen here.
上查看实例和完整代码数据表示
下图最简单的数据表示使用三次贝塞尔曲线。我相信这也将涵盖您的所有用例。为了不让各种特殊情况污染我们的代码，我们将要求输入始终采用四个后续三次贝塞尔曲线的格式，就像我们绘制它们一样。这意味着我们不能使用：
- 二次贝塞尔曲线（通过镜像另一个控制点可转换为立方曲线）
- Segments（通过将控制点等距离地放置在直线的端点之间，可转换为三次贝塞尔曲线）
- 关闭路径 [
ZSVG 命令]（通过计算给定线段然后从那里获取它可转换为三次贝塞尔曲线）
More on the subject of paths in 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.
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
)
寻找交点
显然你已经实现了它 using the t approach (as opposed to true curve splice length) 所以我把它放在这里只是为了完整起见。
注意 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：这就是我们如何获得贝塞尔曲线分割形状的控制点。 t 在连接对边控制点的线段上进行插值。
这是这些片段。它们的端点是各自曲线的控制点。
这是我们渲染曲线时的最终结果：
您可以在 Codepen here.
上查看实例和完整代码从这里去哪里
更多路口
这显然不是最终结果。我们仍然需要找到生成曲线的交点。然而，找到两条贝塞尔曲线的交点并非易事。
这是bezier3bezier3()的nice Whosebug answer on the topic which will lead you to this neat library that will do the heavy lifting for you (look at the code，你就会明白）
分割曲线
找到交点后，您将要找到at which t they occur. Why t you ask? So you can split the curve。
实际最终结果
最后，您需要选择曲线的那些部分并将它们排列以表示网格的各个字段。
如您所见，您还有很长的路要走，我只走了一小部分（并且仍然设法写了一个冗长的答案：D）。
如果你的四边是三次贝塞尔曲线，来点比较简单的怎么样：
要制作水平分隔线（从上到下），通过插值顶部和底部的控制点制作新的三次贝塞尔曲线：
然后，将左右两边分成相同数量的点..
..并拉伸分隔曲线，使它们连接到这些点：
然后，从左到右执行相同的操作以创建垂直分隔线。
这里是测试不同形状的笔：https://codepen.io/Sphinxxxx/pen/pKddee
重要部分在 BezierWrapper.lerpCurve() 和 BezierWrapper.fitCurve() 中，还有 Bezier class 取自 https://gamedev.stackexchange.com/a/5427 以获得沿曲线均匀分布的点(.samples):
class BezierWrapper {
constructor(controls, sampleCount, classname) {
this.controls = controls;
this.classname = classname;
if(sampleCount) {
function point2obj(p) {
return { x: p[0], y: p[1] };
}
//https://gamedev.stackexchange.com/a/5427
const interpolator = new Bezier(point2obj(controls[0]),
point2obj(controls[1]),
point2obj(controls[2]),
point2obj(controls[3]));
const samples = this.samples = [];
for(let i = 1; i <= sampleCount; i++) {
const t = i / (sampleCount+1);
samples.push([interpolator.mx(t), interpolator.my(t)]);
}
}
}
static lerpCurve(source, target, t) {
function lerpCoord(from, to, t) {
const diffX = to[0] - from[0],
diffY = to[1] - from[1],
lerpX = from[0] + (diffX * t),
lerpY = from[1] + (diffY * t);
return [lerpX, lerpY];
}
const middle = source.map((c, i) => lerpCoord(c, target[i], t));
return middle;
}
static fitCurve(source, start, end) {
function distance(p1, p2) {
const dx = p2[0] - p1[0],
dy = p2[1] - p1[1];
return Math.sqrt(dx*dx + dy*dy);
}
//https://gist.github.com/conorbuck/2606166
function angle(p1, p2) {
const dx = p2[0] - p1[0],
dy = p2[1] - p1[1],
radians = Math.atan2(dy, dx);
return radians;
}
//
function rotate(p, radians) {
const x = p[0],
y = p[1],
cos = Math.cos(radians),
sin = Math.sin(radians);
return [cos*x - sin*y, sin*x + cos*y];
}
const sourceStart = source[0],
sourceEnd = source[3],
scale = distance(start, end)/distance(sourceStart, sourceEnd),
rot = angle(start, end) - angle(sourceStart, sourceEnd);
//Translate, scale and rotate the source control points to make them fit the start and end points:
const sourceNorm = source.map(c => [c[0] - sourceStart[0], c[1] - sourceStart[1]]),
fittedNorm = sourceNorm.map(c => rotate([c[0]*scale, c[1]*scale], rot)),
fitted = fittedNorm.map(c => [c[0] + start[0], c[1] + start[1]]);
return fitted;
}
}