let shuffled = d3.shuffle(heartLineData)

let shuffledIds = shuffled.map(d => d.id)

let result = sortList(heartLineData);

let count = 0

let interval = d3.interval(function(elapsed) {

if (count >= result.length) {

interval.stop(); // <== !!!

return;

}

let resultIds = result[count].data.map(d => d.id);

let updatedSet = new Set(resultIds);

let resultLocations = [];

if(result[count].type == 'conquer'){

shuffled.forEach((d,i) => {

if(updatedSet.has(d.id)){

resultLocations.push(i);

}

})

resultLocations = resultLocations.sort(function(a, b) {

return a - b;

});;

for(let i in resultIds){

let resultId = resultIds[i];

let newLocation = resultLocations[i];

shuffledIds[newLocation] = resultId;

}

shuffled.forEach(d => {

if(updatedSet.has(d.id)){

d.status = result[count].type;

}else{

d.status = "inactive";

}

})

update(shuffled,shuffledIds);

count++;

}, 50);

x.domain(dataIds)

let lines = container.selectAll("line")

.data(heartLineData)

.join(

enter => enter.append('line')

.attr("x1", (d,i) => x(d.id) + (d.hypT * Math.cos(d.thetaTop)))

.attr("y1", d => d.intersectionY + (d.hypT * Math.sin(d.thetaTop)))

.attr("x2", (d,i) => x(d.id) - (d.hypB * Math.cos(d.thetaBottom)))

.attr("y2", d => d.intersectionY - (d.hypB * Math.sin(d.thetaBottom)))

.attr('stroke', 'red')

.attr("stroke-linecap", "round")

.attr('fill', 'red')

.attr('stroke-width', 2)

.style("opacity", d => d.status != "inactive" ? 1 : 0.5),

update =>update.call(e => e.transition()

.duration(75)

.delay(0)

.attr("x1", (d,i) => x(d.id) + (d.hypT * Math.cos(d.thetaTop)))

.attr("y1", d => d.intersectionY + (d.hypT * Math.sin(d.thetaTop)))

.attr("x2", (d,i) => x(d.id) - (d.hypB * Math.cos(d.thetaBottom)))

.attr("y2", d => d.intersectionY - (d.hypB * Math.sin(d.thetaBottom)))

.style("opacity", d => d.status != "inactive" ? 1 : 0.5)

)

)

I took an SVG path of a heart, that I got from the [Mozilla SVG transform docs](https://developer.mozilla.org/en-US/docs/Web/SVG/Attribute/transform).

Then calculated some points along the path, similarly to how I did it in my other puckering lips animation.

After that, I wanted to basically fill the shape with vertical lines from top to bottom. My solution to that might be a bit over-complicated, and there might be some library that could do this, or another algorithm or something to do it better.

Also it could be better as far as filling out the shape a little better - notice the right side of the heart is cut off a bit.

But I just wanted to post this for Valentine's day and am not concerned with perfection here. :)

So what I did:

* Calculated a horizontal line intersecting the center of the heart.

* Divided the data points into two groups of points that were either above or below this line. I tried to make the two groups as close to equal in size as possible.

* Sorted both groups by their x coordinate.

* The 'upper' points group was smaller, so I iterated through those to calculate the vertical lines.

* I matched each upper point to a lower point to create the line.

* Next I calculated the point of intersection of this line with the horizontal line I mentioned earlier.

* Then I calculated an upper hypotenuse and theta from the upper point of the line to the point of intersection.

* And a lower hypotenuse and theta from the lower point of the line to the point of intersection.

And that is the data for the lines, which also have an **id** based on their index, so the points go from left to right.

I have a scale below this part of the code and have another comment down there to explain a bit more of why I arranged it like this.

let lipsDrawing = svg.append("defs")

.append("g")

.attr("id","heartIcon")

.append("path")

.attr("id", "heartPath")

.attr("d", heartPath)

let lpLength = d3.select('#heartPath').node();

let totalLength = lpLength.getTotalLength();

totalLength = totalLength;

let dataPoints = d3.range(numPoints).map(point => {

let step = point * (totalLength/numPoints);

let pt = lpLength.getPointAtLength(step);

return {

x: pt.x * 3, //scale by 3

y: pt.y * 3

}

})

//let mx = d3.max(dataPoints, d => [d.x,d.y])

let xExtent = d3.extent(dataPoints, d => d.x);

let yExtent = d3.extent(dataPoints, d => d.y);

let xCenter = (xExtent[1] - xExtent[0])/2;

let yCenter = (yExtent[1] - yExtent[0])/2;

let centerPoint = {x: xCenter, y: yCenter};

let upperPoints = [];

let lowerPoints = [];

dataPoints.forEach(pt => {

if(pt.y > yCenter){

//upper point

upperPoints.push(pt);

}else{

//lower point

lowerPoints.push(pt);

}

})

upperPoints = upperPoints.sort(function(a, b) {

return a.x - b.x;

});

lowerPoints = lowerPoints.sort(function(a, b) {

return a.x - b.x;

});

let intersectionLine = {x1: xExtent[0], y1: centerPoint.y, x2: xExtent[1], y2: centerPoint.y};

const get_intersection = (p0, p1, p2, p3) => {

//http://bl.ocks.org/nitaku/fdbb70c3baa36e8feb4e

let s1_x = p1.x - p0.x

let s1_y = p1.y - p0.y

let s2_x = p3.x - p2.x

let s2_y = p3.y - p2.y

let s = (-s1_y * (p0.x - p2.x) + s1_x * (p0.y - p2.y)) / (-s2_x * s1_y + s1_x * s2_y)

let t = ( s2_x * (p0.y - p2.y) - s2_y * (p0.x - p2.x)) / (-s2_x * s1_y + s1_x * s2_y)

if ((s >= 0) && (s <= 1) && (t >= 0) && (t <= 1)){

return {x: p0.x + (t * s1_x), y: p0.y + (t * s1_y)}

}else{

return;

}

}

let heartLineData = upperPoints.map((d,i) => {

let lower = lowerPoints[i];

let intersectionPt = get_intersection({x: lower.x, y: lower.y}, {x: d.x,y: d.y}, {x: intersectionLine.x1, y: intersectionLine.y1}, {x: intersectionLine.x2,y: intersectionLine.y2});

//top hypotenuse

let hypTop = Math.sqrt(Math.pow(Math.abs(intersectionPt.y - d.y), 2) + Math.pow(Math.abs(intersectionPt.x - d.x), 2));

//bottom hypotenuse

let hypBottom = Math.sqrt(Math.pow(Math.abs(lower.y - intersectionPt.y), 2) + Math.pow(Math.abs(lower.x - intersectionPt.x), 2));

let thetaTop = Math.atan2((d.y - intersectionPt.y), (d.x - intersectionPt.x));

let thetaBottom = Math.atan2(Math.abs(lower.y - intersectionPt.y), Math.abs(lower.x - intersectionPt.x));

thetaTop = thetaTop < 0 ? thetaTop + (2*Math.PI) : thetaTop;

thetaBottom = thetaBottom < 0 ? thetaBottom + (2*Math.PI) : thetaBottom;

return {

id: i,

x1: d.x,

y1: d.y,

x2: lower.x,

y2: lower.y,

slope: (lower.y - d.y)/(lower.x - d.x),

length: 0,

intersectionX: intersectionPt.x,

intersectionY: intersectionPt.y,

thetaTop: thetaTop,

thetaBottom: thetaBottom,

hypB: hypBottom * 1.2,

hypT: hypTop * 1.3

}

})

return heartLineData;

}

The way I animated merge sort is that I am sorting the lines by their **ids** which were assigned in sorted order from left to right in the beginning.

To visualize the process, I start off by shuffling `heartLineData` and then sort by the ids.

For each iteration of the animation, I update the domain of this scale so that the visualization reflects the current order of the data as it gets sorted.

.domain(heartLineData.map(d => d.id))

.range(heartLineData.map(d => d.intersectionX))

.attr("transform",`translate(${margin.left},${margin.top})`)

const svgBackgroundColor = "#081c15",

svg = d3.select("#chart")

.append('svg')

.attr("width", width + margin.left + margin.right)

.attr("height", height + margin.top + margin.bottom)

.style("background-color", svgBackgroundColor);

return svg;

//merge sort function that returns steps for the animation loop

let animationSteps = [];

let updated = [];//numbers/lines that were swapped

const mergeSort = (d) => {

if(d.length){

let dCopy = JSON.parse(JSON.stringify(d));

animationSteps.push({type: "divide", data:dCopy});

}

if(d.length < 2){

return d;

}

let midPoint = Math.floor(d.length/2);

let left = d.slice(0,midPoint);

let right = d.slice(midPoint,d.length);

left = mergeSort(left);

right = mergeSort(right);

let solution = [];

while(left.length && right.length){

if(left[0].id < right[0].id){

solution.push(left.shift());

}else{

solution.push(right.shift());

}

}

while(left.length){

solution.push(left.shift());

}

while(right.length){

solution.push(right.shift());

}

if(solution.length){

let sCopy = JSON.parse(JSON.stringify(solution));

animationSteps.push({type: "conquer", data: sCopy});

}

return solution;

}

let mSort = mergeSort(data);

return animationSteps;