共计 6976 个字符，预计需要花费 18 分钟才能阅读完成。
目前在做等值线等值面相干的性能，用户可拖拽控制点批改等值线，再用等值线生成等值面。因为初始的等值线点数据太多，不利于用户操作，所以先应用道格拉斯 - 普克算法 (Douglas–Peucker) 进行等值线抽稀，再将抽稀后的控制点应用贝塞尔曲线算法进行平滑。
对于贝塞尔曲线算法的平滑过程，有人做了很具体的示意图，举荐大家看下贝塞尔曲线算法之 JS 获取点
能够理解到贝赛尔曲线算法平滑失去的曲线是通过起始点的，同时二阶算法须要三个点，三阶算法须要四个点，四阶算法须要五个点，以此类推。
个别的来说，三阶贝塞尔曲线就曾经够用了，而且成果还不错，所以我抉择了三次贝塞尔曲线平滑算法来进行控制点的平滑解决。
贝塞尔曲线平滑后的等值线是根本不通过控制点的，思考到用户操作逻辑，以及点线关系（我的控制点是等值线抽稀失去的，所以等值线是通过控制点的），所以采纳三次贝塞尔曲线过点平滑算法来进行控制点的平滑解决。
过点平滑的原理就是以相邻两个控制点为起始点，而后往起始点两头插入其余过程点（不是在起始点直线上抉择点），这样平滑失去的曲线是通过起始点的，而曲线如何平滑是由插入的点来管制的，三次贝塞尔曲线须要四个点，那就须要在起始点两头插入两个点。
大抵思路就是，先算出相邻原始点的中点，在把相邻中点连成的线段平移到对应的原始点，以平移后的中点作为控制点，相邻原始点为起始点画贝塞尔曲线，这样就保障了连接处的润滑。而贝塞尔曲线自身是润滑的，所以就把这些原始点用润滑曲线连起来了。具体代码及示意图如下：
代码：
function createCurve(originPoint, option){
// 控制点膨胀系数，经调试 0.6 较好
let scale = option.tension || 0.6;
// 平滑插值插入的最大点数
let maxpoints = option.pointsPerSeg
let originCount = originPoint.length
let curvePoint = []
let midpoints = []
// 生成中点
for(let i = 0 ;i < originCount - 1 ; i++){
midpoints.push([(originPoint[i][0] + originPoint[i + 1][0])/2.0,
(originPoint[i][1] + originPoint[i + 1][1])/2.0
])
}
// 平移中点
let extrapoints = []
for(let i = 1 ;i < originCount - 1 ; i++){
let backi = i - 1;
let midinmid = [(midpoints[i][0] + midpoints[backi][0])/2.0,
(midpoints[i][1] + midpoints[backi][1])/2.0
]
let offsetx = originPoint[i][0] - midinmid[0];
let offsety = originPoint[i][1] - midinmid[1];
let extraindex = 2 * i;
extrapoints[extraindex] = [midpoints[backi][0] + offsetx,
midpoints[backi][1] + offsety
]
// 朝 originPoint[i]方向膨胀
let addx = (extrapoints[extraindex][0] - originPoint[i][0]) * scale;
let addy = (extrapoints[extraindex][1] - originPoint[i][1]) * scale;
extrapoints[extraindex] = [originPoint[i][0] + addx,
originPoint[i][1] + addy
]
let extranexti = extraindex + 1;
extrapoints[extranexti] = [midpoints[i][0] + offsetx,
midpoints[i][1] + offsety
]
// 朝 originPoint[i]方向膨胀
addx = (extrapoints[extranexti][0] - originPoint[i][0]) * scale;
addy = (extrapoints[extranexti][1] - originPoint[i][1]) * scale;
extrapoints[extranexti] = [originPoint[i][0] + addx,
originPoint[i][1] + addy
]
}
let controlPoint = []
// 生成 4 控制点，产生贝塞尔曲线
for(let i = 1 ;i < originCount - 2 ; i++){controlPoint[0] = originPoint[i];
let extraindex = 2 * i;
controlPoint[1] = extrapoints[extraindex + 1];
let extranexti = extraindex + 2;
controlPoint[2] = extrapoints[extranexti];
let nexti = i + 1;
controlPoint[3] = originPoint[nexti];
for(let n = maxpoints; n >= 0; n--){
// 存入曲线点
curvePoint.push(bezier3func(n / maxpoints, controlPoint) );
}
}
return curvePoint
}
// 三次贝塞尔曲线
function bezier3func(uu, controlP){let partX0 = controlP[0][0] * uu * uu * uu;
let partX1 = 3 * controlP[1][0] * uu * uu * (1 - uu);
let partX2 = 3 * controlP[2][0] * uu * (1 - uu) * (1 - uu);
let partX3 = controlP[3][0] * (1 - uu) * (1 - uu) * (1 - uu);
let partX = partX0 + partX1 + partX2 + partX3;
let partY0 = controlP[0][1] * uu * uu * uu;
let partY1 = 3 * controlP[1][1] * uu * uu * (1 - uu);
let partY2 = 3 * controlP[2][1] * uu * (1 - uu) * (1 - uu);
let partY3 = controlP[3][1] * (1 - uu) * (1 - uu) * (1 - uu);
let partY = partY0 + partY1 + partY2 + partY3;
return [partX, partY]
}c++ 版的能够看穿过已知点画平滑曲线（3 次贝塞尔曲线）
然而事件到这里并没有完结，还有坑须要填，间接应用该算法进行平滑，在理论利用中发现控制点间隔近的话，平滑的曲线会有尖角或穿插景象。
比方这样的
还有这样的
这是因为插入的两个新控制点和起始控制点地位非凡，平滑后产生尖角或穿插，如下所示：
优化思路是判断四个点的关系，获取直线控制点 1 - 新控制点 1 与直线控制点 2 - 新控制点 2 之间的交点（如果有的话），如果交点在线段控制点 1 - 点 1 中时，用交点替换点 1，线段控制点 2 - 点 2 同理。或者以控制点 1、交点、控制点 2 三点，而后应用二次贝赛尔曲线算法进行平滑。新的成果示意图如下所示：
优化前与优化后的成果比照如下：右边为优化前的平滑成果，左边是优化后的平滑成果：
优化后的代码：
function createCurve(originPoint, option){
// 控制点膨胀系数，经调试 0.6 较好
let scale = option.tension || 0.6;
// 平滑插值插入的最大点数
let maxpoints = option.pointsPerSeg
let originCount = originPoint.length
let curvePoint = []
let midpoints = []
// 生成中点
for(let i = 0 ;i < originCount - 1 ; i++){
midpoints.push([(originPoint[i][0] + originPoint[i + 1][0])/2.0,
(originPoint[i][1] + originPoint[i + 1][1])/2.0
])
}
// 平移中点
let extrapoints = []
for(let i = 1 ;i < originCount - 1 ; i++){
let backi = i - 1;
let midinmid = [(midpoints[i][0] + midpoints[backi][0])/2.0,
(midpoints[i][1] + midpoints[backi][1])/2.0
]
let offsetx = originPoint[i][0] - midinmid[0];
let offsety = originPoint[i][1] - midinmid[1];
let extraindex = 2 * i;
extrapoints[extraindex] = [midpoints[backi][0] + offsetx,
midpoints[backi][1] + offsety
]
// 朝 originPoint[i]方向膨胀
let addx = (extrapoints[extraindex][0] - originPoint[i][0]) * scale;
let addy = (extrapoints[extraindex][1] - originPoint[i][1]) * scale;
extrapoints[extraindex] = [originPoint[i][0] + addx,
originPoint[i][1] + addy
]
let extranexti = extraindex + 1;
extrapoints[extranexti] = [midpoints[i][0] + offsetx,
midpoints[i][1] + offsety
]
// 朝 originPoint[i]方向膨胀
addx = (extrapoints[extranexti][0] - originPoint[i][0]) * scale;
addy = (extrapoints[extranexti][1] - originPoint[i][1]) * scale;
extrapoints[extranexti] = [originPoint[i][0] + addx,
originPoint[i][1] + addy
]
}
let controlPoint = []
// 生成 4 控制点，产生贝塞尔曲线
for(let i = 1 ;i < originCount - 2 ; i++){controlPoint[0] = originPoint[i];
let extraindex = 2 * i;
controlPoint[1] = extrapoints[extraindex + 1];
let extranexti = extraindex + 2;
controlPoint[2] = extrapoints[extranexti];
let nexti = i + 1;
controlPoint[3] = originPoint[nexti];
let fn = bezier3func;
let cp = intersects(controlPoint.slice(0, 2), controlPoint.slice(-2))
if(cp && isContains(controlPoint[0], controlPoint[1], cp)){controlPoint[1] = cp
}
if(cp && isContains(controlPoint[2], controlPoint[3], cp)){controlPoint[2] = cp
}
if(controlPoint[1][0] == controlPoint[2][0] && controlPoint[1][1] == controlPoint[2][1]){
fn = bezier2func
controlPoint.splice(1, 1)
}
for(var n = maxpoints; n >= 0; n--){
// 存入曲线点
curvePoint.push(fn(n / maxpoints, controlPoint) );
}
}
return curvePoint
}
// 三次贝塞尔曲线
function bezier3func(uu, controlP){let partX0 = controlP[0][0] * uu * uu * uu;
let partX1 = 3 * controlP[1][0] * uu * uu * (1 - uu);
let partX2 = 3 * controlP[2][0] * uu * (1 - uu) * (1 - uu);
let partX3 = controlP[3][0] * (1 - uu) * (1 - uu) * (1 - uu);
let partX = partX0 + partX1 + partX2 + partX3;
let partY0 = controlP[0][1] * uu * uu * uu;
let partY1 = 3 * controlP[1][1] * uu * uu * (1 - uu);
let partY2 = 3 * controlP[2][1] * uu * (1 - uu) * (1 - uu);
let partY3 = controlP[3][1] * (1 - uu) * (1 - uu) * (1 - uu);
let partY = partY0 + partY1 + partY2 + partY3;
return [partX, partY]
}
// 二次贝塞尔曲线
function bezier2func(uu, controlP){let partX0 = controlP[0][0] * uu * uu;
let partX1 = 2 * controlP[1][0] * uu * (1 - uu);
let partX2 = controlP[2][0] * (1 - uu) * (1 - uu);
let partX = partX0 + partX1 + partX2;
let partY0 = controlP[0][1] * uu * uu;
let partY1 = 2 * controlP[1][1] * uu * (1 - uu);
let partY2 = controlP[2][1] * (1 - uu) * (1 - uu);
let partY = partY0 + partY1 + partY2;
return [partX, partY]
}
/**
* Find a point that intersects LineStrings with two coordinates each
* 找到一个点，该点与每个线串有两个坐标相交
*/
function intersects(coords1, coords2) {if (coords1.length !== 2) {throw new Error("<intersects> line1 must only contain 2 coordinates");
}
if (coords2.length !== 2) {throw new Error("<intersects> line2 must only contain 2 coordinates");
}
const x1 = coords1[0][0];
const y1 = coords1[0][1];
const x2 = coords1[1][0];
const y2 = coords1[1][1];
const x3 = coords2[0][0];
const y3 = coords2[0][1];
const x4 = coords2[1][0];
const y4 = coords2[1][1];
// 斜率穿插相乘 k1 = (y4 - y3) / (x4 - x3) ... k2 = (y2 - y1) / (x2 - x1)
//k1 k2 同乘 (x4 - x3) * (x2 - x1) 失去 denom
const denom = ((y4 - y3) * (x2 - x1)) - ((x4 - x3) * (y2 - y1));
const numeA = ((x4 - x3) * (y1 - y3)) - ((y4 - y3) * (x1 - x3));
const numeB = ((x2 - x1) * (y1 - y3)) - ((y2 - y1) * (x1 - x3));
if (denom === 0) { // 斜率一样，平行线
return null;
}
const uA = numeA / denom;
const uB = numeB / denom;
const x = x1 + (uA * (x2 - x1));
const y = y1 + (uA * (y2 - y1));
return [x, y];
}
function isContains(sp, ep, p) {
return ((p[0] > ep[0] && p[0] < sp[0]) || (p[0] > sp[0] && p[0] < ep[0])
) && ((p[1] > ep[1] && p[1] < sp[1]) || (p[1] > sp[1] && p[1] < ep[1])
)
}
正文完
