// 描画 const backgroundColor = ['#824880', '#824948', '#808248', '#488249', '#488082', '#494882']; const pointColor = '#ffffffdd'; const pointSize = 4; const sweepColor = '#ffffff66'; const sweepWeight = 1; const parabolaColor = '#ffffffaa'; const parabolaWeight = 4; const lineColor = '#ffffffaa'; const lineWeight = 1.5; // 母点 const N = 30; let points = []; // 1ステップ const x_step = 0.05; const y_step = 0.05; const steps = 10; // 変化する値 let sweep_y = 0; let parabola_id = []; let joint_x = []; let top_id = 0; let lines = []; let bg; function setup() { createCanvas(640, 480); noFill(); bg = createGraphics(width, height); bg.background(backgroundColor[int(random(backgroundColor.length))]); bg.stroke(255, 20); for (let i = 0; i < 100000; i++) { bg.point(random(width), random(height)); } for (let i = 0; i < N; i++) { points.push(new p5.Vector(int(random(width)), int(random(height)))); } points.sort(function(a,b) { if (a.y < b.y ) return -1; if (b.y < a.y ) return 1; return 0; }); frameRate(60); } function draw() { image(bg, 0, 0); // 平面走査 for (let i = 0; i < steps; i++) { // 交点の更新 let x = 0; let delete_list = []; for (let i = 0; i < parabola_id.length; i++) { if (i < parabola_id.length - 1) { const current_id = parabola_id[i]; const next_id = parabola_id[i+1]; let current_y; let next_y; do { current_y = sq(x - points[current_id].x) / (2 * (points[current_id].y - sweep_y)) + (points[current_id].y + sweep_y) / 2; next_y = sq(x - points[next_id].x) / (2 * (points[next_id].y - sweep_y)) + (points[next_id].y + sweep_y) / 2; x+=x_step; } while (current_y > next_y && (current_y > -100000 || x < points[current_id].x)); x-=x_step; joint_x[i+1].value = x; lines[joint_x[i+1].number[0]][joint_x[i+1].number[1]].set(x, current_y); if (joint_x[i+1].value - joint_x[i].value <= 0 && sweep_y - points[current_id].y > 1) { delete_list.push(i); joint_x[i+1].number = [lines.length, 0]; lines.push([new p5.Vector(x, current_y), new p5.Vector(x, current_y)]); } } else { const current_id = parabola_id[parabola_id.length-1]; let current_y; do { current_y = sq(x - points[current_id].x) / (2 * (points[current_id].y - sweep_y)) + (points[current_id].y + sweep_y) / 2; x+=x_step; } while (x < width); if (joint_x[parabola_id.length-1].value >= width) { delete_list.push(parabola_id.length-1); } } } // 放物線の削除 for (let i = delete_list.length - 1; i >= 0; i--) { parabola_id.splice(delete_list[i], 1); joint_x.splice(delete_list[i], 1); } // 放物線の追加 if (top_id < N) { if (sweep_y >= points[top_id].y) { if (parabola_id.length == 0) { parabola_id.push(top_id); joint_x.push({value: 0, number: [-1, 0]}); joint_x.push({value: width, number: [-1, 1]}); } else { let p; for (let i = 0; i < joint_x.length - 1; i++) { if (points[top_id].x > joint_x[i].value && points[top_id].x <= joint_x[i+1].value) { p = i; } } const y = sq(points[top_id].x - points[parabola_id[p]].x) / (2 * (points[parabola_id[p]].y - sweep_y)) + (points[parabola_id[p]].y + sweep_y) / 2; parabola_id.splice(p+1, 0, top_id, parabola_id[p]); joint_x.splice(p+1, 0, {value: points[top_id].x, number: [lines.length, 0]}, {value: points[top_id].x, number: [lines.length, 1]}); lines.push([new p5.Vector(points[top_id].x, y), new p5.Vector(points[top_id].x, y)]); } top_id++; } } sweep_y+=y_step; } // 走査線の描画 stroke(sweepColor); strokeWeight(sweepWeight); line(0, sweep_y, width, sweep_y); sweep_y+=0.1; // 母点の描画 stroke(pointColor); strokeWeight(pointSize); for (let i = 0; i < N; i++) { point(points[i]); } // 分割線の描画 stroke(lineColor); strokeWeight(lineWeight); for (let i = 0; i < lines.length; i++) { line(lines[i][0].x, lines[i][0].y, lines[i][1].x, lines[i][1].y); } // 放物線の描画 if (parabola_id.length != 0) { let num = 0; noStroke(); stroke(parabolaColor); strokeWeight(parabolaWeight); beginShape(); for (let x = 0; x < width; x++) { if (num != parabola_id.length) { if (x > joint_x[num+1].value) { num++; } } let current_id = parabola_id[num]; const y = sq(x - points[current_id].x) / (2 * (points[current_id].y - sweep_y)) + (points[current_id].y + sweep_y) / 2; curveVertex(x, y); } endShape(); } }

Fortune's Algorithm