in modules/actions/orthogonalize.js [19:193]
var action = function(graph, t) {
if (t === null || !isFinite(t)) t = 1;
t = Math.min(Math.max(+t, 0), 1);
var way = graph.entity(wayID);
way = way.removeNode(''); // sanity check - remove any consecutive duplicates
if (way.tags.nonsquare) {
var tags = Object.assign({}, way.tags);
// since we're squaring, remove indication that this is physically unsquare
delete tags.nonsquare;
way = way.update({tags: tags});
}
graph = graph.replace(way);
var isClosed = way.isClosed();
var nodes = graph.childNodes(way).slice(); // shallow copy
if (isClosed) nodes.pop();
if (vertexID !== undefined) {
nodes = nodeSubset(nodes, vertexID, isClosed);
if (nodes.length !== 3) return graph;
}
// note: all geometry functions here use the unclosed node/point/coord list
var nodeCount = {};
var points = [];
var corner = { i: 0, dotp: 1 };
var node, point, loc, score, motions, i, j;
for (i = 0; i < nodes.length; i++) {
node = nodes[i];
nodeCount[node.id] = (nodeCount[node.id] || 0) + 1;
points.push({ id: node.id, coord: projection(node.loc) });
}
if (points.length === 3) { // move only one vertex for right triangle
for (i = 0; i < 1000; i++) {
motions = points.map(calcMotion);
points[corner.i].coord = vecAdd(points[corner.i].coord, motions[corner.i]);
score = corner.dotp;
if (score < epsilon) {
break;
}
}
node = graph.entity(nodes[corner.i].id);
loc = projection.invert(points[corner.i].coord);
graph = graph.replace(node.move(vecInterp(node.loc, loc, t)));
} else {
var straights = [];
var simplified = [];
// Remove points from nearly straight sections..
// This produces a simplified shape to orthogonalize
for (i = 0; i < points.length; i++) {
point = points[i];
var dotp = 0;
if (isClosed || (i > 0 && i < points.length - 1)) {
var a = points[(i - 1 + points.length) % points.length];
var b = points[(i + 1) % points.length];
dotp = Math.abs(geoOrthoNormalizedDotProduct(a.coord, b.coord, point.coord));
}
if (dotp > upperThreshold) {
straights.push(point);
} else {
simplified.push(point);
}
}
// Orthogonalize the simplified shape
var bestPoints = clonePoints(simplified);
var originalPoints = clonePoints(simplified);
score = Infinity;
for (i = 0; i < 1000; i++) {
motions = simplified.map(calcMotion);
for (j = 0; j < motions.length; j++) {
simplified[j].coord = vecAdd(simplified[j].coord, motions[j]);
}
var newScore = geoOrthoCalcScore(simplified, isClosed, epsilon, threshold);
if (newScore < score) {
bestPoints = clonePoints(simplified);
score = newScore;
}
if (score < epsilon) {
break;
}
}
var bestCoords = bestPoints.map(function(p) { return p.coord; });
if (isClosed) bestCoords.push(bestCoords[0]);
// move the nodes that should move
for (i = 0; i < bestPoints.length; i++) {
point = bestPoints[i];
if (!vecEqual(originalPoints[i].coord, point.coord)) {
node = graph.entity(point.id);
loc = projection.invert(point.coord);
graph = graph.replace(node.move(vecInterp(node.loc, loc, t)));
}
}
// move the nodes along straight segments
for (i = 0; i < straights.length; i++) {
point = straights[i];
if (nodeCount[point.id] > 1) continue; // skip self-intersections
node = graph.entity(point.id);
if (t === 1 &&
graph.parentWays(node).length === 1 &&
graph.parentRelations(node).length === 0 &&
!node.hasInterestingTags()
) {
// remove uninteresting points..
graph = actionDeleteNode(node.id)(graph);
} else {
// move interesting points to the nearest edge..
var choice = vecProject(point.coord, bestCoords);
if (choice) {
loc = projection.invert(choice.target);
graph = graph.replace(node.move(vecInterp(node.loc, loc, t)));
}
}
}
}
return graph;
function clonePoints(array) {
return array.map(function(p) {
return { id: p.id, coord: [p.coord[0], p.coord[1]] };
});
}
function calcMotion(point, i, array) {
// don't try to move the endpoints of a non-closed way.
if (!isClosed && (i === 0 || i === array.length - 1)) return [0, 0];
// don't try to move a node that appears more than once (self intersection)
if (nodeCount[array[i].id] > 1) return [0, 0];
var a = array[(i - 1 + array.length) % array.length].coord;
var origin = point.coord;
var b = array[(i + 1) % array.length].coord;
var p = vecSubtract(a, origin);
var q = vecSubtract(b, origin);
var scale = 2 * Math.min(vecLength(p), vecLength(q));
p = vecNormalize(p);
q = vecNormalize(q);
var dotp = (p[0] * q[0] + p[1] * q[1]);
var val = Math.abs(dotp);
if (val < lowerThreshold) { // nearly orthogonal
corner.i = i;
corner.dotp = val;
var vec = vecNormalize(vecAdd(p, q));
return vecScale(vec, 0.1 * dotp * scale);
}
return [0, 0]; // do nothing
}
};