Skip to content

Instantly share code, notes, and snippets.

@mfbx9da4
Last active August 14, 2021 19:32
Show Gist options
  • Save mfbx9da4/cea175c5cfcdcdbbd93fa6f0481b73d5 to your computer and use it in GitHub Desktop.
Save mfbx9da4/cea175c5cfcdcdbbd93fa6f0481b73d5 to your computer and use it in GitHub Desktop.
function area(image) {
return image.width * image.height;
}
/** https://en.wikipedia.org/wiki/Halton_sequence */
function halton(index, base) {
let fraction = 1;
let result = 0;
while (index > 0) {
fraction /= base;
result += fraction * (index % base);
index = ~~(index / base); // floor division
}
return result;
}
export function haltonCoord(index, prime1, prime2, image, width, height) {
const xRand = halton(index, prime1);
const yRand = halton(index, prime2);
const halfImageWidth = Math.floor(image.width / 2);
const halfImageHeight = Math.floor(image.height / 2);
const x =
Math.floor(xRand * Math.max(0, width - halfImageWidth * 2)) +
halfImageWidth;
const y =
Math.floor(yRand * Math.max(0, height - halfImageHeight * 2)) +
halfImageHeight;
return { x, y };
}
function pseudoRandomCoord(image, width, height) {
const halfImageWidth = Math.floor(image.width / 2);
const halfImageHeight = Math.floor(image.height / 2);
const x =
Math.floor(Math.random() * Math.max(0, width - halfImageWidth * 2)) +
halfImageWidth;
const y =
Math.floor(Math.random() * Math.max(0, height - halfImageHeight * 2)) +
halfImageHeight;
return { x, y };
}
function intersection(posA, imageA, posB, imageB) {
const intersectionTopLeft = {
x: Math.max(
Math.round(posA.x - imageA.width / 2),
Math.round(posB.x - imageB.width / 2)
),
y: Math.max(
Math.round(posA.y - imageA.height / 2),
Math.round(posB.y - imageB.height / 2)
),
};
const topRightAX = Math.round(posA.x + imageA.width / 2);
const topRightBX = Math.round(posB.x + imageB.width / 2);
const bottomLeftAY = Math.round(posA.y + imageA.height / 2);
const bottomLeftBY = Math.round(posB.y + imageB.height / 2);
const intersectionTopRightX = Math.min(topRightAX, topRightBX);
const intersectionBottomRightY = Math.min(bottomLeftAY, bottomLeftBY);
const width = Math.max(0, intersectionTopRightX - intersectionTopLeft.x);
const height = Math.max(0, intersectionBottomRightY - intersectionTopLeft.y);
return width * height;
}
function conflict(posA, imageA, allCoords, images) {
// any more than threshold (%) will be considered a conflict
const imageAreaA = area(imageA);
let biggestConflictPercentage = 0;
for (let i = 0; i < allCoords.length; i++) {
const posB = allCoords[i];
const imageB = images[i];
const imageAreaB = area(imageB);
const intersectionArea = intersection(posA, imageA, posB, imageB);
const unionArea = imageAreaA + imageAreaB - intersectionArea;
const ratio = intersectionArea / unionArea;
if (ratio * 100 > biggestConflictPercentage) {
biggestConflictPercentage = ratio * 100;
}
}
return biggestConflictPercentage;
}
function getRandomCoPrimes() {
// 2 and 3 seem to work the best
if (Math.random() > 0.5) return [2, 3];
return [3, 2];
}
export function randomCoords(images, width, height) {
const allCoords = [];
let i = 0;
let count = 0;
// 100 means allow total overlap
const overlapThreshold = 10;
const recursionLimit = images.length * 5;
const [prime1, prime2] = getRandomCoPrimes();
while (i < images.length && count < recursionLimit) {
// const pos = pseudoRandomCoord(images[i], width, height)
const pos = haltonCoord(i, prime1, prime2, images[i], width, height);
count++;
const conflictPercentage = conflict(pos, images[i], allCoords, images);
if (conflictPercentage > overlapThreshold) {
// console.log("found conflict!", conflictPercentage);
continue;
}
allCoords.push(pos);
i++;
}
return allCoords;
}
const images = [
{ width: 200, height: 300, url: 'https://example.com' },
{ width: 250, height: 310, url: 'https://example.com' },
]
const coords = randomCoords(images, 600, 600)
for (const coord of coords) {
console.log(coord.x, coord.y)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment