@2619's poste précédent montre un intérêt pour le Problème de bliffoscope . Étant donné que le contenu du texte de div.one
et div.two
dans une police à largeur fixe, style ascii, sont des images reconstituées à partir de +
ce qui signifie qu'un actif pixel, et " " (espace) inactif . L'idée est de trouver dans quelle position nous pourrions placer div.one
sur div.two
de sorte que les deux motifs forment davantage d'intersections. Je ne considère que l'intersection des coordonnées de l'axe des actif des pixels de deux images données.
Dans cet exemple, +
est remplacé par o
pour mettre en évidence les intersections de chaque correspondance. Une version simplifiée qui utilise canvas
peuvent être trouvés ici .
Dans le tableau ci-dessous Extrait du SO et dans le Démonstration de JSFiddle cliquez sur le bouton Next
et Previous
ou appuyez sur les touches fléchées du clavier pour naviguer dans les correspondances.
_main.best_positions()
renvoie le nombre d'intersections pour chaque superposition possible, avec n'importe quel degré de tolérance à l'erreur, trié par nombre d'intersections (plus de correspondances en premier).
var PatternFinder;
PatternFinder = (function(win, doc, undefined) {
'use strict';
var _main = {
selectors: {
object_1_pattern: ".one",
background_pattern: ".two",
results: ".three",
next_button: ".next",
previous_button: ".previous",
match_score: ".intersecting_coords",
match_nr: ".match_nr",
},
cache: {
object_text_string: '',
context_text_string: ''
},
init: function() {
_main.cache.object_text_string = $(_main.selectors.object_1_pattern).text();
_main.cache.context_text_string = $(_main.selectors.background_pattern).text();
// Parse our images from the text strings.
_main.serialized_context = _main.serialize_map(_main.cache.context_text_string);
_main.serialized_object = _main.serialize_map(_main.cache.object_text_string);
// Find the position of the object with larger amount of intersecting coordinates
_main.best_positions = _main.get_best_position(_main.serialized_context, _main.serialized_object);
_main.current_result = _main.best_positions.length - 1;
// Draw initial results
_main.print_output(_main.current_result);
// Handle user input
$(_main.selectors.next_button).click(function() {
_main.current_result -= 1;
_main.print_output();
});
$(_main.selectors.previous_button).click(function() {
_main.current_result += 1;
_main.print_output();
});
// Keyboard: Arrow keys
$(document).keydown(function(e) {
switch (e.which) {
case 37:
{ // left
_main.current_result += 1;
_main.print_output();
break;
}
case 39:
{ // right
_main.current_result -= 1;
_main.print_output();
break;
}
default:
return;
}
e.preventDefault(); // prevent the default action (scroll / move caret)
});
},
// Highlight an intersection.
// Replace "+" by "o" in coords _x, _y.
highlight_match: function(_x, _y, background) {
var x = 0,
y = 0,
i = 0,
output = "",
c;
for (i = 0; i < background.length; i += 1) {
c = background[i];
if (c == "+" && x == _x && y == _y) {
output = output + "o";
} else {
output = output + c;
}
x += 1;
if (c == "\n") {
x = 0;
y += 1;
}
}
return output;
},
// Receive the translated serialized object,
// and the original text string for the background.
// Return the background text string, with the matches
// between it and serialized_object highlighted.
merge_and_deserialize: function(serialized_object, background) {
var i;
for (i = serialized_object.length - 1; i >= 0; i--) {
background = _main.highlight_match(serialized_object[i][0], serialized_object[i][1], background);
}
return background;
},
// Receive a text string like the one from the Stack Overflow ticket,
// return an array of coordinates of filled in pixels (+ or space).
serialize_map: function(char_map) {
var x = 0,
y = 0,
c,
i,
map = [];
for (i = 0; i < char_map.length; i += 1) {
c = char_map[i];
if (c == "+") {
map.push([x, y]);
}
x += 1;
if (c == "\n") {
x = 0;
y += 1;
}
}
return map;
},
// Find number of intersections between two images (that's where the magic happens).
// Found here: https://gist.github.com/lovasoa/3361645
array_intersect: function() {
var a, d, b, e, h = [],
l = [],
f = {},
g;
g = arguments.length - 1;
b = arguments[0].length;
for (a = d = 0; a <= g; a += 1) {
e = arguments[a].length, e < b && (d = a, b = e);
}
for (a = 0; a <= g; a += 1) {
e = a === d ? 0 : a || d;
b = arguments[e].length;
for (l = 0; l < b; l += 1) {
var k = arguments[e][l];
f[k] === a - 1 ? a === g ? (h.push(k), f[k] = 0) : f[k] = a : 0 === a && (f[k] = 0);
}
}
return h;
},
// Translate the coordinates of a serialized image.
translate: function(coords, ix, iy) {
return [coords[0] + ix, coords[1] + iy];
},
// Find in which position the object has more intersections with the background.
get_best_position: function(context, object) {
// Calculate image dimensions
var context_width = context.sort(function(a, b) {
return b[0] - a[0];
})[0][0],
context_height = context.sort(function(a, b) {
return b[1] - a[1];
})[0][1],
object_width = object.sort(function(a, b) {
return b[0] - a[0];
})[0][0],
object_height = object.sort(function(a, b) {
return b[1] - a[1];
})[0][1];
// Swipe context, store amount of matches for each patch position.
var similaritudes = [],
cx, cy, intersection, translated_object;
for (cx = -object_width; cx < context_width; cx += 1) {
for (cy = -object_height; cy < context_height; cy += 1) {
translated_object = object.map(function(coords) {
return _main.translate(coords, cx, cy);
});
intersection = _main.array_intersect(context, translated_object);
if (intersection.length > 0) {
similaritudes.push({
coords: [cx, cy],
similaritudes: intersection.length
});
}
}
}
// Return coords,
// sorted by those for which number of matches was greater.
return similaritudes.sort(function(a, b) {
return a.similaritudes - b.similaritudes;
});
},
print_output: function() {
var positioned_object;
// Get the coordinates of one of our matches.
_main.current_result = Math.max(_main.current_result, 1);
_main.current_result = Math.min(_main.current_result, _main.best_positions.length - 1);
var score = _main.best_positions.slice(_main.current_result)[0].similaritudes;
var best_position = _main.best_positions.slice(_main.current_result)[0].coords;
// Translate our image patch to the position defined by _main.current_result.
positioned_object = _main.serialized_object.map(function(coords) {
return _main.translate(coords, best_position[0], best_position[1]);
});
// Produce merged images (background after replace).
var final_image = _main.merge_and_deserialize(positioned_object, _main.cache.context_text_string);
// Print image and information
$(_main.selectors.results).text(final_image);
$(_main.selectors.match_score).text(score);
$(_main.selectors.match_nr).text(_main.best_positions.length - _main.current_result);
}
};
// Expose methods
_main.public_methods = {
init: _main.init,
};
return _main.public_methods;
}(window, document));
PatternFinder.init();
.one,
.two {
display: none;
}
.three {
white-space: pre;
font-family: "Lucida Console", Monaco, "Courier New", Courier, monospace;
margin: 0 0 20px 0;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div class="one">
+
+++
+
</div>
<div class="two">
+ + ++++ + ++ + + +
+ ++ +++ + +++ ++ + +++
+ ++ + + ++ + + + + ++
</div>
<h3>Match: <span class="match_nr"></span></h3>
<h5>Intersecting coordinates: <span class="intersecting_coords"></span></h5>
<div class="three"></div>
<nav>
<a class="previous" href="#">Previous</a>
<a class="next" href="#">Next</a>
</nav>
<p>Click Next and Previous or use the keyboard arrows to see other possible matches.</p>