in modules/actions/circularize.js [17:189]
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);
var origNodes = {};
graph.childNodes(way).forEach(function(node) {
if (!origNodes[node.id]) origNodes[node.id] = node;
});
if (!way.isConvex(graph)) {
graph = action.makeConvex(graph);
}
var nodes = utilArrayUniq(graph.childNodes(way));
var keyNodes = nodes.filter(function(n) { return graph.parentWays(n).length !== 1; });
var points = nodes.map(function(n) { return projection(n.loc); });
var keyPoints = keyNodes.map(function(n) { return projection(n.loc); });
var centroid = (points.length === 2) ? vecInterp(points[0], points[1], 0.5) : d3_polygonCentroid(points);
var radius = d3_median(points, function(p) { return vecLength(centroid, p); });
var sign = d3_polygonArea(points) > 0 ? 1 : -1;
var ids, i, j, k;
// we need at least two key nodes for the algorithm to work
if (!keyNodes.length) {
keyNodes = [nodes[0]];
keyPoints = [points[0]];
}
if (keyNodes.length === 1) {
var index = nodes.indexOf(keyNodes[0]);
var oppositeIndex = Math.floor((index + nodes.length / 2) % nodes.length);
keyNodes.push(nodes[oppositeIndex]);
keyPoints.push(points[oppositeIndex]);
}
// key points and nodes are those connected to the ways,
// they are projected onto the circle, in between nodes are moved
// to constant intervals between key nodes, extra in between nodes are
// added if necessary.
for (i = 0; i < keyPoints.length; i++) {
var nextKeyNodeIndex = (i + 1) % keyNodes.length;
var startNode = keyNodes[i];
var endNode = keyNodes[nextKeyNodeIndex];
var startNodeIndex = nodes.indexOf(startNode);
var endNodeIndex = nodes.indexOf(endNode);
var numberNewPoints = -1;
var indexRange = endNodeIndex - startNodeIndex;
var nearNodes = {};
var inBetweenNodes = [];
var startAngle, endAngle, totalAngle, eachAngle;
var angle, loc, node, origNode;
if (indexRange < 0) {
indexRange += nodes.length;
}
// position this key node
var distance = vecLength(centroid, keyPoints[i]) || 1e-4;
keyPoints[i] = [
centroid[0] + (keyPoints[i][0] - centroid[0]) / distance * radius,
centroid[1] + (keyPoints[i][1] - centroid[1]) / distance * radius
];
loc = projection.invert(keyPoints[i]);
node = keyNodes[i];
origNode = origNodes[node.id];
node = node.move(vecInterp(origNode.loc, loc, t));
graph = graph.replace(node);
// figure out the between delta angle we want to match to
startAngle = Math.atan2(keyPoints[i][1] - centroid[1], keyPoints[i][0] - centroid[0]);
endAngle = Math.atan2(keyPoints[nextKeyNodeIndex][1] - centroid[1], keyPoints[nextKeyNodeIndex][0] - centroid[0]);
totalAngle = endAngle - startAngle;
// detects looping around -pi/pi
if (totalAngle * sign > 0) {
totalAngle = -sign * (2 * Math.PI - Math.abs(totalAngle));
}
do {
numberNewPoints++;
eachAngle = totalAngle / (indexRange + numberNewPoints);
} while (Math.abs(eachAngle) > maxAngle);
// move existing nodes
for (j = 1; j < indexRange; j++) {
angle = startAngle + j * eachAngle;
loc = projection.invert([
centroid[0] + Math.cos(angle) * radius,
centroid[1] + Math.sin(angle) * radius
]);
node = nodes[(j + startNodeIndex) % nodes.length];
origNode = origNodes[node.id];
nearNodes[node.id] = angle;
node = node.move(vecInterp(origNode.loc, loc, t));
graph = graph.replace(node);
}
// add new in between nodes if necessary
for (j = 0; j < numberNewPoints; j++) {
angle = startAngle + (indexRange + j) * eachAngle;
loc = projection.invert([
centroid[0] + Math.cos(angle) * radius,
centroid[1] + Math.sin(angle) * radius
]);
// choose a nearnode to use as the original
var min = Infinity;
for (var nodeId in nearNodes) {
var nearAngle = nearNodes[nodeId];
var dist = Math.abs(nearAngle - angle);
if (dist < min) {
min = dist;
origNode = origNodes[nodeId];
}
}
node = osmNode({ loc: vecInterp(origNode.loc, loc, t) });
graph = graph.replace(node);
nodes.splice(endNodeIndex + j, 0, node);
inBetweenNodes.push(node.id);
}
// Check for other ways that share these keyNodes..
// If keyNodes are adjacent in both ways,
// we can add inBetweenNodes to that shared way too..
if (indexRange === 1 && inBetweenNodes.length) {
var startIndex1 = way.nodes.lastIndexOf(startNode.id);
var endIndex1 = way.nodes.lastIndexOf(endNode.id);
var wayDirection1 = (endIndex1 - startIndex1);
if (wayDirection1 < -1) { wayDirection1 = 1; }
var parentWays = graph.parentWays(keyNodes[i]);
for (j = 0; j < parentWays.length; j++) {
var sharedWay = parentWays[j];
if (sharedWay === way) continue;
if (sharedWay.areAdjacent(startNode.id, endNode.id)) {
var startIndex2 = sharedWay.nodes.lastIndexOf(startNode.id);
var endIndex2 = sharedWay.nodes.lastIndexOf(endNode.id);
var wayDirection2 = (endIndex2 - startIndex2);
var insertAt = endIndex2;
if (wayDirection2 < -1) { wayDirection2 = 1; }
if (wayDirection1 !== wayDirection2) {
inBetweenNodes.reverse();
insertAt = startIndex2;
}
for (k = 0; k < inBetweenNodes.length; k++) {
sharedWay = sharedWay.addNode(inBetweenNodes[k], insertAt + k);
}
graph = graph.replace(sharedWay);
}
}
}
}
// update the way to have all the new nodes
ids = nodes.map(function(n) { return n.id; });
ids.push(ids[0]);
way = way.update({nodes: ids});
graph = graph.replace(way);
return graph;
};