Lin Sanxin
Implementation approach
The effect you want to achieve
As you can see from the cover, each algorithm starts with the first image and ends up looking like the second
Polar coordinates
Before talking about the realization of ideas, I will review a high school knowledge for you — polar coordinates. Haha, I wonder how many people still remember him?
- O: The pole, the origin
- Rho: diameter
- θ : Angle between the polar diameter and the X-axis
X = ρ * cos thetaBecause theX / ρ = cosθY = ρ * sinθBecause theY / ρ = sinθ
What does the result that we want to achieve have to do with polar coordinates? Well, it does matter, let’s say I have a sorted array, and it has 37 elements, and we can convert those 37 elements into 37 points in polar coordinates. How do we do that?
const arr = [
0.1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36
]
Copy the codeWe can go like this:
Element index * 10 -> Angle θ(Why do I multiply by 10, because I want to make 360 degrees?)The value arr[index] -> polar diameter ρ
If we follow the above rules, we can get 37 points in polar coordinates (on canvas the Y axis is from top to bottom, and the following graph is also on canvas, but I still draw the Y axis in the normal direction, so the graph is actually inverted, but there is a reason for that) :
(0- > theta =00°, rho =0) (1- > theta =10°, rho =1) (2- > theta =20°, rho =2) (3- > theta =30°, rho =3)
(4- > theta =40°, rho =4) (5- > theta =50°, rho =5) (6- > theta =60°, rho =6) (7- > theta =70°, rho =7)
(8- > theta =80°, rho =8) (9- > theta =90°, rho =9) (10- > theta =100°, rho =10) (11- > theta =110°, rho =11)
(12- > theta =120°, rho =12) (13- > theta =130°, rho =13) (14- > theta =140°, rho =14) (15- > theta =150°, rho =15)
(16- > theta =160°, rho =16) (17- > theta =170°, rho =17) (18- > theta =180°, rho =18) (19- > theta =190°, rho =19)
(20- > theta =200°, rho =20) (21- > theta =210°, rho =21) (22- > theta =220°, rho =22) (23- > theta =230°, rho =23)
(24- > theta =240°, rho =24) (25- > theta =250°, rho =25) (26- > theta =260°, rho =26) (27- > theta =270°, rho =27)
(28- > theta =280°, rho =28) (29- > theta =290°, rho =29) (30- > theta =300°, rho =30) (31- > theta =310°, rho =31)
(32- > theta =320°, rho =32) (33- > theta =330°, rho =33) (34- > theta =340°, rho =34) (35- > theta =350°, rho =35)
(36- > theta =360°, rho =36)
Copy the code
Do you see any similarities to the trajectory of what we want to achieve in the end?
Randomly scattered
So with that out of the way, let’s think about how do we start by breaking up the elements of the array in polar coordinates? Well, it’s really easy. We can generate an out-of-order array, like
const arr = [
25.8.32.1.19.14.0.29.17.6.7.26.3.30.31.16.28.15.24.10.21.2.9.4.35.5.36.33.11.27.34.22.13.18.23.12.20
]
Copy the codeAnd then, using the same rule, convert polar coordinates
Element index * 10 -> Angle θ(Why do I multiply by 10, because I want to make 360 degrees?)The value arr[index] -> polar diameter ρ
So we can get to these 37 points, and we can naturally achieve the effect of fragmentation
(25- > theta =00°, rho =25) (8- > theta =10°, rho =8) (32- > theta =20°, rho =32) (1- > theta =30°, rho =1)
(19- > theta =40°, rho =19) (14- > theta =50°, rho =14) (0- > theta =60°, rho =0) (29- > theta =70°, rho =29)
(17- > theta =80°, rho =17) (6- > theta =90°, rho =6) (7- > theta =100°, rho =7) (26- > theta =110°, rho =26)
(3- > theta =120°, rho =3) (30- > theta =130°, rho =30) (31- > theta =140°, rho =31) (16- > theta =150°, rho =16)
(28- > theta =160°, rho =28) (15- > theta =170°, rho =15) (24- > theta =180°, rho =24) (10- > theta =190°, rho =10)
(21- > theta =200°, rho =21) (2- > theta =210°, rho =2) (9- > theta =220°, rho =9) (4- > theta =230°, rho =4)
(35- > theta =240°, rho =35) (5- > theta =250°, rho =5) (36- > theta =260°, rho =36) (33- > theta =270°, rho =33)
(11- > theta =280°, rho =11) (27- > theta =290°, rho =27) (34- > theta =300°, rho =34) (22- > theta =310°, rho =22)
(13- > theta =320°, rho =13) (18- > theta =330°, rho =18) (23- > theta =340°, rho =23) (12- > theta =350°, rho =12)
(20- > theta =360°, rho =20)
Copy the code
Implementation effect
To sum up, we want to achieve the effect, there is a train of thought
- 1, Mr. One
Disorderly ordinal group - 2. Use canvas to draw this
Disorderly ordinal groupFor all the elementsThe polar point - 3,
Disorderly ordinal groupforThe sorting - 4. Sorting process
Keep emptying the canvasAnd,redrawThe points corresponding to the polar coordinates of all the elements of the array - 5. Terminate the canvas operation until the sorting is complete
Do it!!
We must do things in order, remember the steps above?
- 1, Mr. One
Disorderly ordinal group - 2. Use canvas to draw this
Disorderly ordinal groupFor all the elementsThe polar point - 3,
Disorderly ordinal groupforThe sorting - 4. Sorting process
Keep emptying the canvasAnd,redrawThe points corresponding to the polar coordinates of all the elements of the array - 5. Terminate the canvas operation until the sorting is complete
Let’s follow this step, step by step to achieve the effect, brothers, go!!
Generate random ordinal groups
My nums is an ordered array from 0 to 179, then I scramble it and stuff it into the array NUMs. I do this 4 times. Why is it 0 minus 179, because 0 minus 179 has exactly 180 numbers
As a programmer, THERE is no way I can type so many elements by hand. To.. In the code
let nums = []
for (let i = 0; i < 4; i++) {
// Generate an ordered array from 0 to 179
const arr = [...Array(180).keys()] // array.keys (
const res = []
while (arr.length) {
/ / upset
const randomIndex = Math.random() * arr.length - 1
res.push(arr.splice(randomIndex, 1) [0])
}
nums = [...nums, ...res]
}
Copy the codeAfter the above operation, I have 4 * 180 = 720 elements in numS, and the elements in NUMS are in the range 0 to 179
Canvas draws scrambled Ordinal Numbers
Before drawing canvas, you must write a canvas node on the HTML page. Here, I set the width to 1000, the height to 1000, and the background color to black
<canvas id="canvas" width="800" height="800" style="background: #000;"></canvas>
Copy the codeAs seen above, the pole (origin) is in the middle of the coordinate, but the original origin of canvas is in the upper left corner of the canvas. We need to move the origin of canvas to the center of the canvas. What is the coordinate of the center? Remember when we were 1,000 by 1,000? If the canvas center is (500, 500), we can use the canvas ctx.translate(500, 500) to move the center. Since the dots we draw are all white, let’s incidentally set ctx.fillStyle to white
One thing to notice is that the Y axis in the canvas goes from top to bottom, as opposed to the normal Y axis.
const canvas = document.getElementById('canvas')
const ctx = canvas.getContext('2d')
ctx.fillStyle = 'white' // Set the brush color
ctx.translate(400.400) // Move center point to (400, 400)
Copy the codeSo how do I draw the dots? It’s not enough to calculate the Angle θ and the polar diameter ρ, because the Canvas doesn’t recognize these two things. What does Canvas know? He only knows (x, y), so we just need to calculate (x, y) by Angle θ and polar diameter ρ. Remember the formula of polar coordinates
X = ρ * cos thetaBecause theX / ρ = cosθY = ρ * sinθBecause theY / ρ = sinθ
Since we’re laying out a scatter point, we’re laying out a circle, so the Angle of a circle is 0 degrees minus 360 degrees, but we don’t want 360 degrees, we just want 0 degrees minus 359 degrees, because 0 degrees and 360 degrees are the same line. One degree on a line is enough for us. So let’s figure out the cosine theta and the sine theta for each Angle of 0 minus 359 degrees.
const CosandSin = []
for (let i = 0; i < 360; i++) {
const jiaodu = i / 180 * Math.PI
CosandSin.push({ cos: Math.cos(jiaodu), sin: Math.sin(jiaodu) })
}
Copy the codeThere are only 360 integer angles between 0° and 359° on a circle, but numS has 720 elements. How to allocate canvas? That’s easy. If I put 2 elements on one Angle, that’s exactly 2 times 360 is 720
All right, let’s cut to the chase and draw the initial scatter. We also know that we need to draw 720 points, and we’re going to have to use a lot of object-oriented programming for this kind of multiple identical things
// a single rectangle constructor
function Rect(x, y, width, height) {
this.x = x / / coordinates x
this.y = y / / y coordinate
this.width = width // The width of the rectangle
this.height = height // Rectangle height
}
// Render a single rectangle
Rect.prototype.draw = function () {
ctx.beginPath() // Start drawing one
ctx.fillRect(this.x, this.y, this.width, this.height) / / draw a
ctx.closePath() // Finish drawing one
}
const CosandSin = []
for (let i = 0; i < 360; i++) {
const jiaodu = i / 180 * Math.PI
CosandSin.push({ cos: Math.cos(jiaodu), sin: Math.sin(jiaodu) })
}
function drawAll(arr) {
const rects = [] // Store 720 rectangles
for (let i = 0; i < arr.length; i++) {
const num = arr[i]
const { cos, sin } = CosandSin[Math.floor(i / 2)] // Draw two in each corner
const x = num * cos // x = ρ * cosθ
const y = num * sin // y = ρ * sinθ
rects.push(new Rect(x, y, 5.3)) // Collect all rectangles
}
rects.forEach(rect= > rect.draw()) // iterate over the render
}
drawAll(nums) // Execute the render function
Copy the codeCheck it out on the page. The initial scatter rendering is now complete
I’m redrawing as I sort
In fact, it is very simple, just sort once, empty the canvas, and then re-execute the above rendering function drawAll. For performance reasons, I wrapped drawAll as a Promise function
function drawAll(arr) {
return new Promise((resolve) = > {
setTimeout(() = > {
ctx.clearRect(-500, -500.1000.1000) // Empty the canvas
const rects = [] // Store 720 rectangles
for (let i = 0; i < arr.length; i++) {
const num = arr[i]
const { cos, sin } = CosandSin[Math.floor(i / 2)] // Draw two in each corner
const x = num * cos // x = ρ * cosθ
const y = num * sin // y = ρ * sinθ
rects.push(new Rect(x, y, 5.3)) // Collect all rectangles
}
rects.forEach(rect= > rect.draw()) // iterate over the render
resolve('draw success')},10)})}Copy the codeAnd then let’s do an example of a sort algorithm, let’s do a bubble sort
async function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) { // Compare adjacent elements in pairs
var temp = arr[j + 1]; // Element swap
arr[j + 1] = arr[j]; arr[j] = temp; }}await drawAll(arr) // Redraw while sorting
}
return arr;
}
Copy the codeThen place a button on the page that performs the start sort
<button id="btn"</button>document.getElementById('btn').onclick = function () {
bubbleSort(nums)
}
Copy the codeThe effect is as follows, is not very happy ha ha ha!!
The complete code
Here I refer to [front-end god] Lin Sanxin’s source code added a little bit of events, the purpose is to make the algorithm more clear visualization
/* CSS file */
.wrap{
display: flex;
justify-content: flex-start;
align-items: flex-start;
}
#startBtn.#restart.#stopBtn {
margin-left: 7px;
}
Copy the code<! -- HTML file -->
<div class="wrap">
<canvas id="canvas" width="800" height="800" style="background: #000;"></canvas>
<button id="restart">Start all over again</button>
<button id="stopBtn">suspended</button>
<button id="startBtn">Start sorting</button>
</div>
Copy the code / / js file
const canvas = document.getElementById('canvas')
const ctx = canvas.getContext('2d')
ctx.fillStyle = 'white' // Set the brush color
ctx.translate(400.400) // Move center point to (400, 400)
/* * @nums: store random hash * @status: change render state * */
let nums = [], status = false
// Randomly generate hash points
;function randomNum() {
nums.length = 0 // Get into the habit of emptying arrays when they are associated with function
for (let i = 0; i < 4; i++) {
// Generate an ordered array from 0 to 180
const arr = [...Array(180).keys()]
const res = []
while (arr.length) {
// Scatter around the center of the circle
const randomIndex = Math.random() * arr.length - 1
res.push(arr.splice(randomIndex, 1) [0])
}
nums = [...nums, ...res]
}
}
randomNum()
// Define the rectangle prototype
/* * @x: coordinates x * @y: coordinates y * @width: rectangular width * @height: rectangular height * */
function Rect(x, y, width, height) {
this.x = x
this.y = y
this.width = width
this.height = height
}
// Draw a rectangle
Rect.prototype.draw = function () {
ctx.beginPath() // Draw the starting path
ctx.fillRect(this.x, this.y, this.width, this.height) // Draw the path
ctx.closePath() // End the path
}
const CosandSin = []
for (let i = 0; i < 360; i++) {
const jiaodu = i / 180 * Math.PI
CosandSin.push({ cos: Math.cos(jiaodu), sin: Math.sin(jiaodu) })
}
// Draw a random scatter diagram
/* * @arr: random hash passed in * @statusFlag: a flag indicating whether the timer exists * */
function drawAll(arr, statusFlag) {
let timer = null; (!!!!! statusFlag) &&clearTimeout(timer)
return new Promise(resolve= > {
timer = setTimeout(_= > {
ctx.clearRect(-400, -400.800.800) // Empty the canvas
const rects = []
for (let i = 0; i < arr.length; i++) {
const num = arr[i]
const { cos, sin } = CosandSin[Math.floor(i / 2)] // Draw two in each corner
const x = num * cos
const y = num * sin
rects.push(new Rect(x, y, 5.3)) // Collect all rectangles
}
rects.forEach(rect= > rect.draw())
resolve('draw success')},10)
})
}
drawAll(nums)
// Bubble sort painting
async function bubbleSort(arr) {
for (let i = 0, len = arr.length; i < len; ++i) {
if (status) return
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
await drawAll(arr) // Redraw while sorting
}
return arr
}
// start
startBtn.onclick = () = > {
console.log('Start sorting ============')
status = false
bubbleSort(nums) // Click Execute
}
// stop
stopBtn.onclick = () = > {
console.log('suspend = = = = = = = = = = = =')
drawAll(nums, true)
console.log('status: ', status)
status = true
}
// restart
restart.onclick = () = > {
console.log('Start over ============')
randomNum()
console.log('nums: ', nums)
drawAll(nums, true)
status = true
}
Copy the code