Created
August 26, 2016 23:38
-
-
Save gdyrrahitis/c59a608d4291dc338fe05aad9a2aa428 to your computer and use it in GitHub Desktop.
We have an image with white background and a black colored rectangle. 1 = white, 0 = black. Solution in finding any number of rectangles in a 2D array.
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
<!DOCTYPE html> | |
<html> | |
<head> | |
<title>Rectangles</title> | |
</head> | |
<body> | |
<h1>Find rectangles in images!</h1> | |
<button id="singleRectangle">Find single rectangle coordinates</button> | |
<button id="multipleRectangle">Find multiple rectangles coordinates</button> | |
<button id="reset">Reset</button> | |
<div id="container"></div> | |
<script src="script.js"></script> | |
<script src="main.js"></script> | |
</body> | |
</html> |
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
// Singe rectangle | |
var singleRectangle = [ | |
[1, 1, 1, 1, 1, 1, 1], | |
[1, 1, 1, 0, 0, 0, 1], | |
[1, 1, 1, 0, 0, 0, 1], | |
[1, 1, 1, 0, 0, 0, 1], | |
[1, 1, 1, 0, 0, 0, 1], | |
[1, 1, 1, 1, 1, 1, 1], | |
]; | |
var multipleRectangles = [ | |
[0, 0, 0, 1, 0, 0, 0], | |
[0, 0, 0, 1, 0, 0, 0], | |
[1, 1, 1, 1, 0, 0, 0], | |
[1, 1, 1, 1, 1, 1, 1] | |
]; | |
var container = document.querySelector("#container"); | |
document.querySelector("#singleRectangle").addEventListener("click", function () { | |
var result = findRectangle(singleRectangle); | |
container.innerHTML = JSON.stringify(result); | |
}, false); | |
document.querySelector("#multipleRectangle").addEventListener("click", function () { | |
var objs = []; | |
var cloned = JSON.parse(JSON.stringify(multipleRectangles)); | |
while(!cloned.every(isInverted)) { | |
var coords = findRectangle(cloned); | |
var options = {x1: coords.topLeft.x, y1: coords.topLeft.y, x2: coords.bottomRight.x, y2: coords.bottomRight.y}; | |
invertTo(cloned, options, 1); | |
objs.push(coords); | |
} | |
container.innerHTML = JSON.stringify(objs); | |
}, false); | |
document.querySelector("#reset").addEventListener("click", function () { | |
container.innerHTML = ""; | |
}, false); | |
function isInverted(b) { | |
return b.every(function(c) {return c === 1;}); | |
} |
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
var INT_MAX = 999999; | |
function findRectangle(array) { | |
var topLeft, bottomRight; | |
for (var i = 0; i < array.length; i++) { | |
for (var j = 0; j < array[i].length; j++) { | |
if (!topLeft) { | |
if (0 === array[i][j]) { | |
// First zero | |
topLeft = { | |
x: i, | |
y: j | |
}; | |
break; | |
} | |
} | |
if(topLeft && !bottomRight) { | |
if(0 === array[i][j] && | |
(1 === array[i][j + 1] || typeof array[i][j + 1] === "undefined") && | |
(1 == array[i + 1][j] || typeof array[i + 1][j] === "undefined")) { | |
// Last zero | |
bottomRight = { | |
x: i, | |
y: j | |
}; | |
i = INT_MAX; | |
break; | |
} | |
} | |
} | |
} | |
return { | |
topLeft: topLeft, | |
bottomRight: bottomRight | |
} | |
} | |
function invertTo(array, options, bit) { | |
if(bit < 0 || bit > 1) throw new Error("Not valid bit"); | |
for (var i = options.x1; i <= options.x2; i++) { | |
for (var j = options.y1; j <= options.y2; j++) { | |
array[i][j] = bit; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment