/**
* Handles the edge routing between nodes and supernodes
* @module EdgeRouting
*/
var lines = [];
var edgeZPositionMin = -2;
var edgeZPositionRange = 1;
var edgeLengthNodeOut = 0.03;
var edgeDistanceMin = 0.01;
var edgeDistance = 0.01;
var edgeAngleDistance = Math.PI / 540;
var circleAngleStep = Math.PI / 72;
/**
* adds the required lines for all edges of the currently selected supernodes to the lines array
* @param {supernodeRenderedEdgeMatrix} supernodeRenderedEdgeMatrix describing the edges
*/
function computeDetailLODLinesRenderingObject(supernodeRenderedEdgeMatrix) {
// create two vectors to keep track of the positions defining the next line
let prevVec = new THREE.Vector2(0, 0);
let vec = new THREE.Vector2(0, 0);
// inter supernode edges
computeOutsideLinesForRendering(supernodeRenderedEdgeMatrix, vec, prevVec);
// intra supernode edges
computeInsideLinesForRendering(supernodeRenderedEdgeMatrix, vec, prevVec);
}
/**
* adds the required lines for all external (connecting) edges of the currently selected supernodes to the lines array
* @param {supernodeRenderedEdgeMatrix} supernodeRenderedEdgeMatrix describing the edges
* @param {THREE.Vector2} vec used for intermediate calculations
* @param {THREE.Vector2} prevVec used for intermediate calculations
*/
function computeOutsideLinesForRendering(supernodeRenderedEdgeMatrix, vec, prevVec) {
let startRadiusOut = [];
supernodes.forEach(() => startRadiusOut.push(supernodeRadius + supernodeSizePercentage * supernodeRadius / 2 + edgeLengthNodeOut));
for (let i = 0; i < supernodes.length; i++) {
for (let j = i + 1; j < supernodes.length; j++) {
renderedEdges = supernodeRenderedEdgeMatrix[i][j];
// edges between different supernodes
let vec1To2 = new THREE.Vector2(supernodes[j].position.x - supernodes[i].position.x, supernodes[j].position.y - supernodes[i].position.y);
vec1To2.normalize();
let supernode1ExitAngle = atan3(vec1To2.y, vec1To2.x);
let supernode2ExitAngle = atan3(-vec1To2.y, -vec1To2.x);
let radius = Math.max(startRadiusOut[i], startRadiusOut[j]);
let exitAngleOffsets = [0, edgeAngleDistance];
// sort edges based on weight then on angular distance to the exit point (closer edges get routed first)
sortEdgesForOutsideLayouting(renderedEdges, supernode1ExitAngle);
for (let k = 0; k < renderedEdges.length; k++) {
let renderedEdge = renderedEdges[k];
renderedEdge.linesStartIndex = lines.length;
// circle edge for first supernode
let angle1 = computeNodeExitAngle(computeNodeAngle(renderedEdge.node1.supernodeIndex, renderedEdge.node1.nodeIndex), renderedEdge.node1.nodeId, "outside");
let supernode1Position = supernodes[renderedEdge.node1.supernodeIndex].position;
let routingDirection = addCircularDrawLines(supernode1Position, angle1, supernode1ExitAngle, radius, exitAngleOffsets, prevVec, vec, renderedEdge);
let supernode1ExitAngleOffsets = routingDirection * exitAngleOffsets[getDirectionIndex(routingDirection)];
let supernode1ExitPosition = { x: vec.x, y: vec.y };
// outgoing edge for first node
addNodeOutDrawLine(supernode1Position, angle1, radius, prevVec, vec, renderedEdge);
exitAngleOffsets[getDirectionIndex(routingDirection)] += edgeAngleDistance;
// circle edge for second supernode using exit angles which match the ones from the first supernode to get straight line connections between the supernodes
let angle2 = computeNodeExitAngle(computeNodeAngle(renderedEdge.node2.supernodeIndex, renderedEdge.node2.nodeIndex), renderedEdge.node2.nodeId, "outside");
let supernode2Position = supernodes[renderedEdge.node2.supernodeIndex].position;
let exitAngle = (supernode2ExitAngle + supernode1ExitAngleOffsets) % (2 * Math.PI);
addCircularDrawLines(supernode2Position, angle2, exitAngle, radius, [0, 0], prevVec, vec, renderedEdge);
let supernode2ExitPosition = { x: vec.x, y: vec.y };
// outgoing edge for second node
addNodeOutDrawLine(supernode2Position, angle2, radius, prevVec, vec, renderedEdge);
// edge connecting the two supernodes
addSupernodeConnectionDrawLine(supernode1ExitPosition, supernode2ExitPosition, prevVec, vec, renderedEdge);
renderedEdge.linesEndIndex = lines.length;
radius += edgeDistance;
}
startRadiusOut[i] = radius;
startRadiusOut[j] = radius;
}
}
}
/**
* adds the required lines for all internal edges of the currently selected supernodes to the lines array
* @param {supernodeRenderedEdgeMatrix} supernodeRenderedEdgeMatrix describing the edges
* @param {THREE.Vector2} vec used for intermediate calculations
* @param {THREE.Vector2} prevVec used for intermediate calculations
*/
function computeInsideLinesForRendering(supernodeRenderedEdgeMatrix, vec, prevVec) {
// internal edges of one supernode
for (let i = 0; i < supernodes.length; i++) {
renderedEdges = supernodeRenderedEdgeMatrix[i][i];
let radius = supernodeRadius - supernodeSizePercentage * supernodeRadius / 2 - edgeLengthNodeOut;
sortEdgesForInsideLayouting(renderedEdges);
for (let k = 0; k < renderedEdges.length; k++) {
let renderedEdge = renderedEdges[k];
renderedEdge.linesStartIndex = lines.length;
let angle1 = computeNodeExitAngle(computeNodeAngle(renderedEdge.node1.supernodeIndex, renderedEdge.node1.nodeIndex), renderedEdge.node1.nodeId, "inside");
let angle2 = computeNodeExitAngle(computeNodeAngle(renderedEdge.node2.supernodeIndex, renderedEdge.node2.nodeIndex), renderedEdge.node2.nodeId, "inside");
let supernode1Position = supernodes[renderedEdge.node1.supernodeIndex].position;
addCircularDrawLines(supernode1Position, angle1, angle2, radius, [0, 0], prevVec, vec, renderedEdge);
addNodeOutDrawLine(supernode1Position, angle1, radius, prevVec, vec, renderedEdge);
addNodeOutDrawLine(supernode1Position, angle2, radius, prevVec, vec, renderedEdge);
renderedEdge.linesEndIndex = lines.length;
radius -= edgeDistance;
}
}
}
/**
* adds the circular part of one supernode of an edge to the lines array
* @param {vec3} supernodePosition center of the circle
* @param {float} startAngle where the circle will begin in the range [0-2*PI]
* @param {float} stopAngle where the circle will stop in the range [0-2*PI]
* @param {float} radius of the circle
* @param {float} stopAngleOffsets an offset to the stop angle for each of the two directions in the range [0-2*PI]
* @param {THREE.Vector2} prevVec used for intermediate calculations
* @param {THREE.Vector2} vec used for intermediate calculations
* @param {renderedEdge} renderedEdge to which the cirlce lines belong
* @returns {int} 0 or 1, determining the direction in which the cirlce was drawn
*/
function addCircularDrawLines(supernodePosition, startAngle, stopAngle, radius, stopAngleOffsets, prevVec, vec, renderedEdge) {
let routingDirection = getCircleLayoutDirection(startAngle, stopAngle);
if (stopAngle < startAngle && routingDirection == 1)
stopAngle += 2 * Math.PI;
else if (stopAngle > startAngle && routingDirection == -1)
stopAngle -= 2 * Math.PI;
let curAngle = startAngle;
let routing = true;
let stopAngleOffset = stopAngleOffsets[getDirectionIndex(routingDirection)];
setVecToDirectionWithOffset(vec, supernodePosition, radius, curAngle);
// draw cirlce segments
while (routing) {
prevVec.set(vec.x, vec.y);
curAngle = curAngle + routingDirection * circleAngleStep;
if ((routingDirection == 1 && curAngle > (stopAngle - stopAngleOffset)) || (routingDirection == -1 && curAngle < (stopAngle + stopAngleOffset))) {
curAngle = stopAngle - routingDirection * stopAngleOffset;
routing = false;
}
setVecToDirectionWithOffset(vec, supernodePosition, radius, curAngle);
addDrawLine(prevVec, vec, renderedEdge, computeEdgeZPriority(renderedEdge.edge.weight, supernodesEdgeWeightMax));
}
return routingDirection;
}
/**
* adds the one line of the edge which connects the two supernodes to the lines array
* @param {vec2} supernode1ExitPosition from where the line should stat
* @param {vec2} supernode2ExitPosition where the line should end
* @param {THREE.Vector2} prevVec used for intermediate calculations
* @param {THREE.Vector2} vec used for intermediate calculations
* @param {renderedEdge} renderedEdge to which the line belongs
*/
function addSupernodeConnectionDrawLine(supernode1ExitPosition, supernode2ExitPosition, prevVec, vec, renderedEdge) {
prevVec.set(supernode1ExitPosition.x, supernode1ExitPosition.y);
vec.set(supernode2ExitPosition.x, supernode2ExitPosition.y);
addDrawLine(prevVec, vec, renderedEdge, computeEdgeZPriority(renderedEdge.edge.weight, supernodesEdgeWeightMax));
}
/**
* adds the one line going out from the supernode and connects with the circle lines to the lines array
* @param {vec3} supernodePosition of the supernode
* @param {float} angle at which the node from which the drawn line exits is located within the supernode in the range [0-2*PI]
* @param {float} radius to which the line extends
* @param {THREE.Vector2} prevVec used for intermediate calculations
* @param {THREE.Vector2} vec used for intermediate calculations
* @param {renderedEdge} renderedEdge to which the drawn line belongs
*/
function addNodeOutDrawLine(supernodePosition, angle, radius, prevVec, vec, renderedEdge) {
setVecToDirectionWithOffset(prevVec, supernodePosition, supernodeRadius, angle);
setVecToDirectionWithOffset(vec, supernodePosition, radius, angle);
addDrawLine(prevVec, vec, renderedEdge, computeEdgeZPriority(renderedEdge.edge.weight, supernodesEdgeWeightMax));
}
/**
* adds a line defined by prevVec and vec to the lines array
* @param {THREE.Vector2} prevVec defining the start position of the edge
* @param {THREE.Vector2} vec defining the end position of the edge
* @param {renderedEdge} renderedEdge to which the drawn line belongs
* @param {float} zPriority of the edge [0-1], higher number is drawn on top
*/
function addDrawLine(prevVec, vec, renderedEdge, zPriority) {
let zPos = computeEdgeZPosition(zPriority);
lines.push({ position1: { x: prevVec.x, y: prevVec.y, z: zPos }, position2: { x: vec.x, y: vec.y, z: zPos }, renderedEdge: renderedEdge, weight: renderedEdge.edge.weight });
}
/**
* computes the z coordinate of an edge for rendering
* @param {float} priority [0-1], where higher number is drawn on top
* @returns {float} the edge z position
*/
function computeEdgeZPosition(priority) {
return edgeZPositionMin + priority * edgeZPositionRange;
}
/**
* sets the passed vector to the position defined by an offset o, a direction d and radius r (o + d * r)
* @param {THREE.Vector2} vec whose value is modified by this function
* @param {THREE.Vector2} offset origin from which to go into the direction
* @param {float} radius how far to step in the direction
* @param {float} direction in form of an angle in the range [0-2*PI]
*/
function setVecToDirectionWithOffset(vec, offset, radius, direction) {
vec.set(offset.x + Math.cos(direction) * radius, offset.y + Math.sin(direction) * radius);
}
/**
* sorts the renderedEdges of one supernode based on their weight and then their angular distance to the supernode exit angle
* @param {renderedEdge[]} renderedEdges an array of edges of one supernode to another one
* @param {float} supernodeExitAngle angle at which the edges exit the node in the range [0-2*PI]
*/
function sortEdgesForOutsideLayouting(renderedEdges, supernodeExitAngle) {
renderedEdges.sort((a, b) => {
if (b.edge.weight == a.edge.weight) {
bDifference = getAngleDifference(computeNodeAngle(b.node1.supernodeIndex, b.node1.nodeIndex), supernodeExitAngle);
aDifference = getAngleDifference(computeNodeAngle(a.node1.supernodeIndex, a.node1.nodeIndex), supernodeExitAngle);
if (aDifference < Math.PI && bDifference < Math.PI)
return aDifference - bDifference;
else
return bDifference - aDifference;
}
else
return b.edge.weight - a.edge.weight;
});
}
/**
* sorts the renderedEdges of one supernode based on their weight and then their angular distance between the two nodes of the edge
* @param {renderedEdge[]} renderedEdges an array of internal edges of one supernodeode
*/
function sortEdgesForInsideLayouting(renderedEdges) {
renderedEdges.sort((a, b) => {
if (b.edge.weight == a.edge.weight) {
bDifference = getSmallerConnectingAngleInCircle(computeNodeAngle(b.node1.supernodeIndex, b.node1.nodeIndex), computeNodeAngle(b.node2.supernodeIndex, b.node2.nodeIndex));
aDifference = getSmallerConnectingAngleInCircle(computeNodeAngle(a.node1.supernodeIndex, a.node1.nodeIndex), computeNodeAngle(a.node2.supernodeIndex, a.node2.nodeIndex));
return aDifference - bDifference;
}
else
return b.edge.weight - a.edge.weight;
});
}
/**
* maps the routing direction for circular lines to the dedicaded array index
* @param {int} routingDirection either -1 or 1
* @returns {int} 0 or 1
*/
function getDirectionIndex(routingDirection) {
return routingDirection == 1 ? 0 : 1;
}
/**
* computes the exit angle for the next edge of the specified node
* the exit angle is updated automatically within this function for the next call
* @param {float} nodeAngle at which the node is placed within the supernode in the range [0-2*PI]
* @param {int} nodeId id of the node
* @param {int} directionAttribute either 0 or 1 defining intra or inter supernode edges
* @returns the exit angle of the node edge
*/
function computeNodeExitAngle(nodeAngle, nodeId, directionAttribute) {
let nodeEdges = nodesNumberEdges[nodeId.toString()];
let angle = nodeAngle + (nodeEdges[directionAttribute].count - nodeEdges[directionAttribute].total / 2.0) * edgeAngleDistance;
angle = angle % (2 * Math.PI);
nodeEdges[directionAttribute].count++;
return angle;
}
/**
* returns the direciton which connects the two angles with the shorter path
* @param {float} startAngle of the circle in the range [0-2*PI]
* @param {float} stopAngle of the circle in the range [0-2*PI]
* @returns {int} -1: clockwise, 1: counterclockwise
*/
function getCircleLayoutDirection(startAngle, stopAngle) {
let angleDifference = getAngleDifference(startAngle, stopAngle);
if (angleDifference > Math.PI)
return -1;
else
return 1;
}
/**
* calculates the positive difference between two angles in the range [0,2*PI]
* @param {float} angle1 [0-2*PI]
* @param {float} angle2 [0-2*PI]
* @returns {float} difference between the angles
*/
function getAngleDifference(angle1, angle2) {
let angleDifference = angle2 - angle1;
if (angleDifference < 0)
angleDifference += 2 * Math.PI;
return angleDifference;
}
/**
* calculates the shortes angle distance connecting two angles in the range [0,PI]
* @param {float} angle1 [0-2*PI]
* @param {float} angle2 [0-2*PI]
* @returns the connection angle
*/
function getSmallerConnectingAngleInCircle(angle1, angle2) {
let angleDifference = getAngleDifference(angle1, angle2);
return angleDifference < Math.PI ? angleDifference : 2 * Math.PI - angleDifference;
}
/**
* computes the angle at which a node is positioned within a supernode
* @param {*} supernodeIndex withing the selected supernodes
* @param {*} nodeIndex withing the supernode
* @returns {float} the node angle in the range [0-2*PI]
*/
function computeNodeAngle(supernodeIndex, nodeIndex) {
return 2 * Math.PI / supernodes[supernodeIndex].nodeIds.length * (nodeIndex + 0.5);
}
/**
* computes the atan function in the range [0-2*PI]
* @param {float} b
* @param {*} a
* @returns {float} the calculated function value
*/
var atan3 = function (b, a) {
var angle = Math.atan2(b, a);
return angle < 0 ? angle + 2 * Math.PI : angle;
};
/**
* calculates the supernodeRenderedEdgeMatrix from the renderedEdgeMatrix which covers additional information for the edges
* @param {supernodeEdgeMatrix} supernodeEdgeMatrix used for the calculations
* @param {float} minEdgeWeight of all edges within the supernodeEdgeMatrix
* @param {float} maxEdgeWeight of all edges within the supernodeEdgeMatrix
* @returns {supernodeRenderedEdgeMatrix} the supernode rendered edge matrix
*/
function computeSupernodeRenderedEdgeMatrix(supernodeEdgeMatrix, minEdgeWeight, maxEdgeWeight) {
var supernodeRenderedEdgeMatrix = [];
for (let i = 0; i < supernodes.length; i++) {
supernodeRenderedEdgeMatrix[i] = [];
for (let j = i; j < supernodes.length; j++) {
supernodeRenderedEdgeMatrix[i][j] = [];
}
}
for (let i = 0; i < supernodes.length; i++) {
for (let j = i; j < supernodes.length; j++) {
for (let k = 0; k < supernodeEdgeMatrix[i][j].length; k++) {
let edge = supernodeEdgeMatrix[i][j][k];
if (edge.weight >= minEdgeWeight && edge.weight <= maxEdgeWeight) {
let nodeIndex1 = -1;
let nodeIndex2 = -1;
let nodeId1 = edge.id1;
let nodeId2 = edge.id2;
// store the edge node which belongs to the supernode with the smaller index first for rendering
if (i == j) {
supernodes[i].nodeIds.some(function (nodeId, nodeIndex) {
if (nodeId == edge.id1) {
nodeIndex1 = nodeIndex;
return true;
}
});
supernodes[i].nodeIds.some(function (nodeId, nodeIndex) {
if (nodeId == edge.id2) {
nodeIndex2 = nodeIndex;
return true;
}
});
}
else {
supernodes[i].nodeIds.some(function (nodeId, nodeIndex) {
if (nodeId == edge.id1) {
nodeIndex1 = nodeIndex;
nodeId1 = edge.id1;
return true;
}
else if (nodeId == edge.id2) {
nodeIndex1 = nodeIndex;
nodeId1 = edge.id2;
return true;
}
});
supernodes[j].nodeIds.some(function (nodeId, nodeIndex) {
if (nodeId == edge.id1) {
nodeIndex2 = nodeIndex;
nodeId2 = edge.id1;
return true;
}
else if (nodeId == edge.id2) {
nodeIndex2 = nodeIndex;
nodeId2 = edge.id2;
return true;
}
});
}
let position1 = computeNodePosition(i, nodeIndex1);
let position2 = computeNodePosition(j, nodeIndex2);
position1.z = edgeZPositionMin;
position2.z = edgeZPositionMin;
var renderedEdge = {
edge: edge,
node1: { position: position1, supernodeIndex: i, nodeIndex: nodeIndex1, nodeId: nodeId1 },
node2: { position: position2, supernodeIndex: j, nodeIndex: nodeIndex2, nodeId: nodeId2 }
};
supernodeRenderedEdgeMatrix[i][j].push(renderedEdge);
}
}
}
}
return supernodeRenderedEdgeMatrix;
}