/**
@param selectedLinks
@return
*/
/**
* Function calculates Different Edge-Bundling Metrics.
* Therefore some chosen edges get compared against each other edge with 3 different metrics.
* --> Distance, Edge length similarity, Parallelism
* The result of these 3 Metrics get aggregated to an consistency value.
* The Function returns the consistency value for each link which gets sampled for the heatmap.
* The Lines get sampled in 4 Steps and in 8 steps for the display on the svg
* @param {Array} selectedLinks The links which should be compared by the metrics
* @param {number} alpha The weight for the Distance Metric
* @param {number} beta The weight for the Edge length similarity Metric
* @param {number} gamma The weight for the Parallelism Metric
* @returns {Array} result Array of objects for the Heatmap -> {x, y, value}
*/
function EdgeBundlingMetrics(selectedLinks,alpha,beta,gamma)
{
var steps = 4;
var distance = CalculateMetric(1,selectedLinks, steps);
var edgeLength = CalculateMetric(2,selectedLinks, steps);
var parallelism = CalculateMetric(3,selectedLinks, steps);
var consistency = Consistency(selectedLinks, distance, edgeLength, parallelism, alpha, beta, gamma);
var result = EdgeSampling(selectedLinks,steps*2,consistency); // Sample all lines for Heatmap
return result;
}
/**
* METRIC 1: Distance
* Calculates the distance between the sample points of two edges.
* First the minimum of all distances between the first point on the first edge, and the second edge are taken and the maxiumum
* of all distances from the first edge is taken as result.
* (We compare each point on the first edge repeatedly against all points on the second edge)
* @param {Object} link1 First link which should be compared against the second link
* @param {Object} link2 Second link which should be compared against the first link
* @param {number} steps steps at which the line is sampled
* @result {number} Result of the Metric = Maximum distance of all minimum distances between the two edges
*/
function Distance(link1, link2, steps) {
var travelRatio_link1 = 100/(steps-1);// -1 because we start at the startpoint
var travelRatio_link2 = 100/(steps-1);
var link1_x1 = parseFloat(d3.select(link1).attr("x1"));
var link1_x2 = parseFloat(d3.select(link1).attr("x2"));
var link1_y1 = parseFloat(d3.select(link1).attr("y1"));
var link1_y2 = parseFloat(d3.select(link1).attr("y2"));
var link2_x1 = parseFloat(d3.select(link2).attr("x1"));
var link2_x2 = parseFloat(d3.select(link2).attr("x2"));
var link2_y1 = parseFloat(d3.select(link2).attr("y1"));
var link2_y2 = parseFloat(d3.select(link2).attr("y2"));
var link1_currentX = link1_x1; // Startvalues
var link1_currentY = link1_y1; // Startvalues
var currentMinDistance = [];
for(var i= 1; i <=steps; i++) {
var link2_currentX = link2_x1; //Startvalues
var link2_currentY = link2_y1; //Startvalues
var tempDistance = [];
// Take Startpoint
if (i != 1){
link1_currentX = link1_x1 + (link1_x2 - link1_x1) * (100 / travelRatio_link1);
link1_currentY = link1_y1 + (link1_y2 - link1_y1) * (100 / travelRatio_link1);
// Adds up to 100% of the range
travelRatio_link1 += 100/(steps-1);
}
for(var j= 1; j <=steps; j++){
// Take Startpoint
if (j != 1) {
link2_currentX = link2_x1 + (link2_x2 - link2_x1) * (100 / travelRatio_link2);
link2_currentY = link2_y1 + (link2_y2 - link2_y1) * (100 / travelRatio_link2);
// Adds up to 100% of the range
travelRatio_link2 += 100/(steps-1);
}
// Save the different distances
tempDistance.push(Math.sqrt( Math.pow(link1_currentX - link2_currentX,2) + Math.pow(link1_currentY - link2_currentY,2)));
}
// get the Minimum distance of the points
currentMinDistance.push(arrayMin(tempDistance));
}
// Return maximum distance of all minimum distances
return arrayMax(currentMinDistance);
}
/**
* METRIC 2: Edge length similarity
* The edge length similarity between link1 and link2 is the minimum between the length of link1 and link2
* divided by the maximum between the length of link1 and link2.
* @param {Object} link1 First link which should be compared against the second link
* @param {Object} link2 Second link which should be compared against the first link
* @result {number} Result of the Metric = minimum distance of link1,link2 divided by the maximum distance of link1,link2
*/
function EdgeLengthSimilarity(link1, link2) {
var lengthLink1 = 0;
var lengthLink2 = 0;
var link1_x1 = parseFloat(d3.select(link1).attr("x1"));
var link1_x2 = parseFloat(d3.select(link1).attr("x2"));
var link1_y1 = parseFloat(d3.select(link1).attr("y1"));
var link1_y2 = parseFloat(d3.select(link1).attr("y2"));
var link2_x1 = parseFloat(d3.select(link2).attr("x1"));
var link2_x2 = parseFloat(d3.select(link2).attr("x2"));
var link2_y1 = parseFloat(d3.select(link2).attr("y1"));
var link2_y2 = parseFloat(d3.select(link2).attr("y2"));
// Length of the lines
lengthLink1 = Math.sqrt( Math.pow(link1_x1 - link1_x2,2) + Math.pow(link1_y1 - link1_y2,2));
lengthLink2 = Math.sqrt( Math.pow(link2_x1 - link2_x2,2) + Math.pow(link2_y1 - link2_y2,2));
// Returns the minimum distance divided by the maximum distance
return Math.min(lengthLink1,lengthLink2)/Math.max(lengthLink1,lengthLink2);
}
/**
* METRIC 3: Parallelism
* The parallelism of two links is measured as the minimum between: (projection of link1 on link2) /link2
* and (projection of link2 on link1) /link1
* @param {Object} link1 First link which should be compared against the second link
* @param {Object} link2 Second link which should be compared against the first link
* @result {number} result Result of the Metric = Minimum of the projection from link1 to link2 and visa versa
*/
function Parallelism(link1, link2) {
var link1_x1 = parseFloat(d3.select(link1).attr("x1"));
var link1_x2 = parseFloat(d3.select(link1).attr("x2"));
var link1_y1 = parseFloat(d3.select(link1).attr("y1"));
var link1_y2 = parseFloat(d3.select(link1).attr("y2"));
var link2_x1 = parseFloat(d3.select(link2).attr("x1"));
var link2_x2 = parseFloat(d3.select(link2).attr("x2"));
var link2_y1 = parseFloat(d3.select(link2).attr("y1"));
var link2_y2 = parseFloat(d3.select(link2).attr("y2"));
// Direction link1
var link1_directionX = link1_x1 - link1_x2;
var link1_directionY = link1_y1 - link1_y2;
// Direction link2
var link2_directionX = link2_x1 - link2_x2;
var link2_directionY = link2_y1 - link2_y2;
// Dot Product between link1*link2
var link1DotLink2 = (link1_directionX * link2_directionX) + (link1_directionY * link2_directionY);
// Projection of link1 on link2
var magnitude_link2 = Math.sqrt(Math.pow(link2_directionX,2) + Math.pow(link2_directionY,2));
var projection_l1_l2_X = (link1DotLink2/magnitude_link2) * link2_directionX;
var projection_l1_l2_Y = (link1DotLink2/magnitude_link2) * link2_directionY;
// Projection of link1 on link2
var magnitude_link1 = Math.sqrt(Math.pow(link1_directionX,2) + Math.pow(link1_directionY,2));
var projection_l2_l1_X = (link1DotLink2/magnitude_link1) * link1_directionX;
var projection_l2_l1_Y = (link1DotLink2/magnitude_link1) * link1_directionY;
//Length
var lengthLink1 = Math.sqrt( Math.pow(link1_directionX,2) + Math.pow(link1_directionY,2));
var lengthLink2 = Math.sqrt( Math.pow(link2_directionX,2) + Math.pow(link2_directionY,2));
var lengthProjection_l1_l2 = Math.sqrt( Math.pow(projection_l1_l2_X,2) + Math.pow(projection_l1_l2_Y,2));
var lengthProjection_l2_l1 = Math.sqrt( Math.pow(projection_l2_l1_X,2) + Math.pow(projection_l2_l1_Y,2));
// Minimum of the projection from link1 to link2 and visa versa
var result = Math.min(lengthProjection_l1_l2/lengthLink2, lengthProjection_l2_l1/lengthLink1);
return result;
}
/**
* Aggregated consistency
* Consistency of two edges is defined by the three metrics Distance, EdgeLengthSimilarity and Parallelism which have
* different weights alpha, beta and gamma which hold -> alpha + beta + gamma = 1.
* The Distance Metric gets normalized based on the maximum of the distances.
* @param {Array} selectedLinks The links which should be compared by the metrics
* @param {Array} distance Results of the distance metric of all selected links
* @param {Array} edgeLength Results of the EdgeLengthSimilarity metric of all selected links
* @param {Array} parallelism Results of the parallelism metric of all selected links
* @param {number} alpha The weight for the Distance Metric
* @param {number} beta The weight for the Edge length similarity Metric
* @param {number} gamma The weight for the Parallelism Metric
* @returns {Array} consistency Returns the result array of the aggregated consistency for all selected links
*/
function Consistency(selectedLinks, distance, edgeLength, parallelism, alpha, beta, gamma) {
// Normalize the distance
var normDistance = distance;
var squaredDistance = 0;
var consistency = [];
// Loop adds up all squared distances
for(var i = 0; i < selectedLinks.length; i++){
squaredDistance += Math.pow(distance[i],2);
}
var normFactor = 1/Math.sqrt(squaredDistance);
// Multiplies every value by the normalize factor
normDistance = normDistance.map(function(element) {
return element*normFactor;
});
// Calculate for every Link its Consistency
for(var i = 0; i < selectedLinks.length; i++){
consistency[i] = Math.sqrt(alpha * Math.pow(normDistance[i],2) + beta * Math.pow(1-edgeLength[i],2) + gamma * Math.pow(1-parallelism[i],2));
}
return consistency;
}
/**
* Calculates the chosen Metric for every given link against each other link
* and returns an Array with the result for each link.
* To get only one result for each link, the average over all values for the respective link is taken as final result.
* @param {number} metricNumber Defines which Metric should be used
* 1 = Distance --> The Average Distance is taken
* 2 = Edge length similarity
* 3 = Parallelism
* @param {Array} links The selected links
* @param {number} steps The amount of samples, for an link, which some metrics need
* @return {Array} result Array with the average result for each link in the size of all selected links
*/
function CalculateMetric(metricNumber,links, steps) {
var result = [];
var tempResult = [];
for(var i = 0; i < links.length; i++){
for(var j = 0; j < links.length; j++){
// Do not compare the same link
if(j!=i){
// CHOOSE METRIC
if(metricNumber == 1){ // Distance
tempResult.push(Distance(links[i], links[j], steps));
}
else if(metricNumber == 2){ // Edge length similarity
tempResult.push(EdgeLengthSimilarity(links[i], links[j]));
}
else if(metricNumber == 3){ // Parallelism
tempResult.push(Parallelism(links[i], links[j]));
}
}
}
// After finishing the comparision of one link against the others push the average
result.push(averageOfArray(tempResult));
}
return result;
}
/**
* Returns the Average value of an given array
* @param {Array} array Array of numbers
* @returns {number} avg Returns the average number calculated from the array
*/
function averageOfArray(array){
var sum = 0;
for( var i = 0; i < array.length; i++ ){
sum += array[i];
}
return avg = sum/array.length;
}
/**
* Returns the minimum value of an given array
* @param {Array} arr Array of numbers
* @returns {number} min Returns the minimum number from the array
*/
function arrayMin(arr) {
var len = arr.length, min = Infinity;
while (len--) {
if (Number(arr[len]) < min) {
min = Number(arr[len]);
}
}
return min;
};
/**
* Returns the maximum value of an given array
* @param {Array} arr Array of numbers
* @returns {number} max Returns the maximum number from the array
*/
function arrayMax(arr) {
var len = arr.length, max = -Infinity;
while (len--) {
if (Number(arr[len]) > max) {
max = Number(arr[len]);
}
}
return max;
};