Created
November 14, 2021 07:11
-
-
Save iann0036/c50cfb36ed2a118501e6a76fcf2be9ed to your computer and use it in GitHub Desktop.
Toy Car CAPTCHA Solve
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<html> | |
<body> | |
<canvas id="canvas" width="320" height="320"></canvas> | |
<div style="display:none;"> | |
<img id="source" src="test.png"> | |
</div> | |
<script> | |
var canvas = document.getElementById("canvas"); | |
var ctx = canvas.getContext('2d'); | |
var image = document.getElementById('source'); | |
function distance(from, to) { | |
return Math.sqrt(Math.pow(from[0] - to[0], 2) + Math.pow(from[1] - to[1], 2)); | |
} | |
function mirrorImage(ctx, image, x = 0, y = 0, horizontal = false, vertical = false) { | |
ctx.save(); // save the current canvas state | |
ctx.setTransform( | |
horizontal ? -1 : 1, 0, // set the direction of x axis | |
0, vertical ? -1 : 1, // set the direction of y axis | |
x + (horizontal ? image.width : 0), // set the x origin | |
y + (vertical ? image.height : 0) // set the y origin | |
); | |
ctx.drawImage(image,0,0); | |
ctx.restore(); // restore the state as it was when this function was called | |
} | |
function close_to_color(r_a, g_a, b_a, r_b, g_b, b_b, closeness) { | |
return (!( | |
r_a < r_b - closeness || r_a > r_b + closeness || | |
g_a < g_b - closeness || g_a > g_b + closeness || | |
b_a < b_b - closeness || b_a > b_b + closeness | |
)); | |
} | |
function is_greyscale(r_a, g_a, b_a) { | |
return ((Math.max(r_a, g_a, b_a) - Math.min(r_a, g_a, b_a)) < 70); | |
} | |
function process(flipped) { | |
var imageWidth = canvas.width; | |
var imageHeight = canvas.height; | |
var imageData = ctx.getImageData(0, 0, imageWidth, imageHeight); | |
var data = imageData.data; | |
var i, n; | |
var bg_r = data[0]; | |
var bg_g = data[1]; | |
var bg_b = data[2]; | |
var topmost, leftmost, bottommost, rightmost = null; | |
var leftmax = 999999; | |
var rightmax = 0; | |
var car_points = []; | |
var intersection_points = []; | |
var line_points = []; | |
// quickly iterate over all pixels | |
for (i = 0, n = data.length; i < n; i += 4) { | |
var x = Math.floor((i % (imageWidth * 4)) / 4); | |
var y = Math.floor((i / 4) / imageWidth); | |
var r = data[i]; | |
var g = data[i + 1]; | |
var b = data[i + 2]; | |
if (!close_to_color(r, g, b, bg_r, bg_g, bg_b, 50)) { | |
if (!topmost && is_greyscale(r, g, b) && !close_to_color(r, g, b, 255, 255, 255, 20)) { | |
topmost = [x, y]; | |
} | |
if (x < leftmax && is_greyscale(r, g, b) && !close_to_color(r, g, b, 255, 255, 255, 20)) { | |
leftmost = [x, y]; | |
leftmax = x; | |
} | |
if (x > rightmax && is_greyscale(r, g, b) && !close_to_color(r, g, b, 255, 255, 255, 20)) { | |
rightmost = [x, y]; | |
rightmax = x; | |
} | |
if (is_greyscale(r, g, b) && !close_to_color(r, g, b, 255, 255, 255, 20)) { | |
bottommost = [x, y]; | |
} | |
if (!is_greyscale(r, g, b)) { | |
ctx.fillStyle = 'blue'; | |
ctx.fillRect(x, y, 1, 1); | |
line_points.push([x, y]); | |
} | |
} | |
if (close_to_color(r, g, b, 255, 255, 255, 20)) { | |
ctx.fillStyle = 'green'; | |
ctx.fillRect(x, y, 1, 1); | |
car_points.push([x, y]); | |
} | |
} | |
if (leftmost[1] > rightmost[1]) { | |
// tilted right | |
let x_dist = ((rightmost[0] - topmost[0]) / 5); | |
let y_dist = ((rightmost[1] - topmost[1]) / 5); | |
let drop_x_dist = ((leftmost[0] - topmost[0]) / 5); | |
let drop_y_dist = ((leftmost[1] - topmost[1]) / 5); | |
let inv_x_dist = ((leftmost[0] - bottommost[0]) / 5); | |
let inv_y_dist = ((leftmost[1] - bottommost[1]) / 5); | |
let inv_drop_x_dist = ((rightmost[0] - bottommost[0]) / 5); | |
let inv_drop_y_dist = ((rightmost[1] - bottommost[1]) / 5); | |
let forward_points = []; | |
let inverse_points = []; | |
for (let j = 0; j < 6; j++) { | |
for (let i = 0; i < 6; i++) { | |
ctx.strokeStyle = 'pink'; | |
//ctx.beginPath(); | |
//ctx.arc(topmost[0] + (i*x_dist) + (j*drop_x_dist), topmost[1] + (i*y_dist) + (j*drop_y_dist), 8, 0, 2 * Math.PI); | |
forward_points.push([topmost[0] + (i * x_dist) + (j * drop_x_dist), topmost[1] + (i * y_dist) + (j * drop_y_dist), i, j]); | |
//ctx.stroke(); | |
ctx.strokeStyle = 'yellow'; | |
//ctx.beginPath(); | |
//ctx.arc(bottommost[0] + (i*inv_x_dist) + (j*inv_drop_x_dist), bottommost[1] + (i*inv_y_dist) + (j*inv_drop_y_dist), 8, 0, 2 * Math.PI); | |
inverse_points.push([bottommost[0] + (i * inv_x_dist) + (j * inv_drop_x_dist), bottommost[1] + (i * inv_y_dist) + (j * inv_drop_y_dist), 5-i, 5-j]); | |
//ctx.stroke(); | |
} | |
} | |
inverse_points.reverse(); | |
for (let i = 0; i < 36; i++) { | |
ctx.strokeStyle = 'magenta'; | |
let x_offset = i % 6; | |
let y_offset = Math.floor(i / 6); | |
let proportional_x = Math.floor(((forward_points[i][0] * (5 - x_offset)) + (inverse_points[i][0] * x_offset)) / 5); | |
let proportional_y = Math.floor(((forward_points[i][1] * (5 - y_offset)) + (inverse_points[i][1] * y_offset)) / 5); | |
intersection_points.push([proportional_x, proportional_y, x_offset, y_offset]); | |
ctx.strokeStyle = 'magenta'; | |
ctx.beginPath(); | |
ctx.arc(proportional_x, proportional_y, 8, 0, 2 * Math.PI); | |
ctx.stroke(); | |
} | |
ctx.strokeStyle = 'red'; | |
ctx.beginPath(); | |
ctx.arc(leftmost[0], leftmost[1], 8, 0, 2 * Math.PI); | |
ctx.stroke(); | |
ctx.beginPath(); | |
ctx.arc(rightmost[0], rightmost[1], 8, 0, 2 * Math.PI); | |
ctx.stroke(); | |
ctx.beginPath(); | |
ctx.arc(topmost[0], topmost[1], 8, 0, 2 * Math.PI); | |
ctx.stroke(); | |
ctx.beginPath(); | |
ctx.arc(bottommost[0], bottommost[1], 8, 0, 2 * Math.PI); | |
ctx.stroke(); | |
} else if (!flipped) { | |
mirrorImage(ctx, image, 0, 0, true, false); | |
process(true); | |
return; | |
} else { | |
return; // unprocessable | |
} | |
let best_car_point = car_points[0]; | |
let best_neighbor_value = 0; | |
for (let point of car_points) { | |
let cumul_neighbors = 0; | |
for (let compare_point of car_points) { | |
if (Math.abs(compare_point[0]-point[0]) < 20 && Math.abs(compare_point[1]-point[1]) < 20) { | |
cumul_neighbors += 1; | |
} | |
} | |
if (cumul_neighbors > best_neighbor_value) { | |
best_neighbor_value = cumul_neighbors; | |
best_car_point = point; | |
} | |
} | |
ctx.strokeStyle = 'orange'; | |
ctx.beginPath(); | |
ctx.arc(best_car_point[0], best_car_point[1], 12, 0, 2 * Math.PI); | |
ctx.stroke(); | |
let closest_intersection_to_car_point = intersection_points.reduce((a, b) => distance(a, [best_car_point[0], best_car_point[1]]) < distance(b, [best_car_point[0], best_car_point[1]]) ? a : b); | |
let closest_points_to_intersections = [{ | |
'closest': line_points.reduce((a, b) => distance(a, [best_car_point[0], best_car_point[1]]) < distance(b, [best_car_point[0], best_car_point[1]]) ? a : b), | |
'intersection': closest_intersection_to_car_point | |
}]; | |
for (let point of intersection_points) { | |
let closest = line_points.reduce((a, b) => distance(a, point) < distance(b, point) ? a : b); | |
if (distance(closest, point) < 12) { | |
ctx.strokeStyle = 'yellow'; | |
ctx.beginPath(); | |
ctx.moveTo(point[0], point[1]); | |
ctx.lineTo(closest[0], closest[1]); | |
ctx.stroke(); | |
closest_points_to_intersections.push({ | |
'closest': closest, | |
'intersection': point | |
}); | |
} | |
} | |
let solved_paths = []; | |
for (let close_point of closest_points_to_intersections) { | |
for (let candidate_close_point of closest_points_to_intersections) { | |
if ( | |
(close_point['intersection'][2] == candidate_close_point['intersection'][2] && Math.abs(close_point['intersection'][3] - candidate_close_point['intersection'][3]) == 1) || // x axis is same and y off by 1, or | |
(close_point['intersection'][3] == candidate_close_point['intersection'][3] && Math.abs(close_point['intersection'][2] - candidate_close_point['intersection'][2]) == 1) // y axis is same and x off by 1 | |
) { | |
let candidate_score = 0; | |
for (let i=0; i<10; i++) { | |
let test_x = close_point['closest'][0] + Math.floor(((candidate_close_point['closest'][0] - close_point['closest'][0]) / 10) * i); | |
let test_y = close_point['closest'][1] + Math.floor(((candidate_close_point['closest'][1] - close_point['closest'][1]) / 10) * i); | |
let closest = line_points.reduce((a, b) => distance(a, [test_x, test_y]) < distance(b, [test_x, test_y]) ? a : b); | |
if (distance(closest, [test_x, test_y]) < 12) { | |
candidate_score += 1; | |
ctx.strokeStyle = 'aqua'; | |
ctx.beginPath(); | |
ctx.arc(test_x, test_y, 1, 0, 2 * Math.PI); | |
ctx.stroke(); | |
} | |
} | |
if (candidate_score > 7) { | |
ctx.strokeStyle = 'yellow'; | |
ctx.beginPath(); | |
ctx.moveTo(close_point['intersection'][0], close_point['intersection'][1]); | |
ctx.lineTo(candidate_close_point['intersection'][0], candidate_close_point['intersection'][1]); | |
ctx.stroke(); | |
solved_paths.push({ | |
'from': close_point['intersection'], | |
'to': candidate_close_point['intersection'] | |
}); | |
} | |
} | |
} | |
} | |
console.log(closest_intersection_to_car_point); | |
console.log(JSON.parse(JSON.stringify(solved_paths))); | |
// deduplicate | |
for (let i=0; i<solved_paths.length; i++) { | |
for (let j=i+1; j<solved_paths.length; j++) { | |
if ( | |
( | |
solved_paths[i]['from'][2] == solved_paths[j]['from'][2] && solved_paths[i]['from'][3] == solved_paths[j]['from'][3] && | |
solved_paths[i]['to'][2] == solved_paths[j]['to'][2] && solved_paths[i]['to'][3] == solved_paths[j]['to'][3] | |
) || | |
( | |
solved_paths[i]['from'][2] == solved_paths[j]['to'][2] && solved_paths[i]['from'][3] == solved_paths[j]['to'][3] && | |
solved_paths[i]['to'][2] == solved_paths[j]['from'][2] && solved_paths[i]['to'][3] == solved_paths[j]['from'][3] | |
) | |
) { | |
solved_paths.splice(i, 1); | |
i -= 1; | |
break; | |
} | |
} | |
} | |
function traverse_path(remaining_paths, current_point) { | |
let traversal_made = false; | |
for (let i=0; i<remaining_paths.length; i++) { | |
if (remaining_paths[i]['from'][0] == current_point[0] && remaining_paths[i]['from'][1] == current_point[1]) { | |
current_point = remaining_paths[i]['to']; | |
remaining_paths.splice(i, 1); | |
traverse_path(remaining_paths, current_point); | |
traversal_made = true; | |
} else if (remaining_paths[i]['to'][0] == current_point[0] && remaining_paths[i]['to'][1] == current_point[1]) { | |
current_point = remaining_paths[i]['from']; | |
remaining_paths.splice(i, 1); | |
traverse_path(remaining_paths, current_point); | |
traversal_made = true; | |
} | |
} | |
if (!traversal_made) { | |
ctx.strokeStyle = 'lime'; | |
ctx.beginPath(); | |
ctx.arc(current_point[0], current_point[1], 14, 0, 2 * Math.PI); | |
ctx.stroke(); | |
} | |
} | |
traverse_path(solved_paths, closest_intersection_to_car_point); | |
} | |
image.addEventListener('load', e => { | |
ctx.drawImage(image, 0, 0); | |
process(false); | |
}); | |
</script> | |
</body> | |
</html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment