Menu
Given a 2D Space with X points, how can I efficiently find where to place a fixed-size rectangle, so that it covers the largest possible number of those X points?
I need something along these lines to position a viewport in a 2D game I'm building.
999
left pointer at the leftmost point, and a right pointer at the rightmost point that falls within left + width. Then iterate over all the points, recalculating the position of the right pointer each time until it is at the last point. top pointer at the highest point, and a bottom pointer at the lowest point that falls within top + height. Then iterate over all the points, recalculating the position of the bottom pointer each time until it is at the last point. Below is a simple implementation in Javascript, which can be optimised on many points. Run the code snippet to see the results with random data.
function placeRectangle(p, width, height) {
var optimal, max = 0;
var points = p.slice();
points.sort(horizontal);
for (var left = 0, right = 0; left < points.length; left++) {
while (right < points.length && points[right].x <= points[left].x + width) ++right;
var column = points.slice(left, right);
column.sort(vertical);
for (var top = 0, bottom = 0; top < column.length; top++) {
while (bottom < column.length && column[bottom].y <= column[top].y + height) ++bottom;
if (bottom - top > max) {
max = bottom - top;
optimal = column.slice(top, bottom);
}
if (bottom == column.length) break;
}
if (right == points.length) break;
}
var left = undefined, right = undefined, top = optimal[0].y, bottom = optimal[optimal.length - 1].y;
for (var i = 0; i < optimal.length; i++) {
var x = optimal[i].x;
if (left == undefined || x < left) left = x;
if (right == undefined || x > right) right = x;
}
return {x: (left + right) / 2, y: (top + bottom) / 2};
function horizontal(a, b) {
return a.x - b.x;
}
function vertical(a, b) {
return a.y - b.y;
}
}
var width = 160, height = 90, points = [];
for (var i = 0; i < 10; i++) points[i] = {x: Math.round(Math.random() * 300), y: Math.round(Math.random() * 200)};
var rectangle = placeRectangle(points, width, height);
// SHOW RESULT IN CANVAS
var canvas = document.getElementById("canvas");
canvas.width = 300; canvas.height = 200;
canvas = canvas.getContext("2d");
paintRectangle(canvas, rectangle.x - width / 2, rectangle.y - height / 2, width, height, 1, "red");
for (var i in points) paintDot(canvas, points[i].x, points[i].y, 2, "blue");
function paintDot(canvas, x, y, size, color) {
canvas.beginPath();
canvas.arc(x, y, size, 0, 6.2831853);
canvas.closePath();
canvas.fillStyle = color;
canvas.fill();
}
function paintRectangle(canvas, x, y, width, height, line, color) {
canvas.beginPath();
canvas.rect(x, y, width, height);
canvas.closePath();
canvas.lineWidth = line;
canvas.strokeStyle = color;
canvas.stroke();
}<BODY STYLE="margin: 0; border: 0; padding: 0;">
<CANVAS ID="canvas" STYLE="width: 300px; height: 200px; float: left; background-color: #F8F8F8;"></CANVAS>
</BODY>If someone is looking for @m69's code in C++ then here it is:
struct str {
bool operator() (cv::Point2f a, cv::Point2f b)
{
return a.x < b.x;
}
} compX;
struct str1 {
bool operator() (cv::Point2f a, cv::Point2f b)
{
return a.y < b.y;
}
} compY;
cv::Point2f placeRectangle(std::vector<cv::Point2f> p, float width, float height)
{
double max = 0;
std::vector<cv::Point2f> points = p;
std::sort(points.begin(), points.end(), compX);
std::vector<cv::Point2f> optimal;
float left = 0.0;
float right = 0.0;
for (left = 0, right = 0; left < points.size(); ++left)
{
while (right < points.size() && points[right].x <= points[left].x + width) ++right;
std::vector<cv::Point2f> myVector1(points.begin() + left, points.begin() + right);
std::vector<cv::Point2f> column = myVector1;
std::sort(column.begin(), column.end(), compY);
for (int top = 0, bottom = 0; top < column.size(); top++)
{
while (bottom < column.size() && column[bottom].y <= column[top].y + height) ++bottom;
if (bottom - top > max)
{
max = bottom - top;
std::vector<cv::Point2f> myVector(column.begin() + top, column.begin() + bottom);
optimal = myVector;
}
if (bottom == column.size()) break;
}
if (right == points.size()) break;
}
left = 0; right = 0; float top = optimal[0].y; float bottom = optimal[optimal.size() - 1].y;
for (int i = 0; i < optimal.size(); i++)
{
float x = optimal[i].x;
if (left == 0 || x < left) left = x;
if (right == 0 || x > right) right = x;
}
return cv::Point2f((left + right) / 2.0, (top + bottom) / 2.0);
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
