如何找到给定点的最接近平方

Question

我有一个正方形的二维数组（正方形），每个正方形的长度为50个单位，并且x，y坐标为。正方形之间的距离是5个单位。 x，y坐标是正方形的左下角。现在，给定任何点（x，y坐标），我怎么能找到最接近该点的正方形。

square **sq = new square*[10];
for(int i=0;i<10;++i){
    sq[i]=new square[10];
}

int m=0, n=0;
for(int i=0;i<10;++i){
    m=0;
    for(int j=0;j<10;++j){
        sq[i][j].setCoOrdinates(m,n);
        m+=55;
    }
    n+=55;
}

//给定点（x，y），我如何找到最接近该点的平方的索引（i，j）。

Answer 1

让我们严格定义从正方形到点的距离的定义：“从点（x，y）到矩形内某个点的所有长度中的最小值”。这为定义到矩形的距离提供了一些明确的规则。对于任何矩形，如果point（x，y）位于矩形侧面的上方，下方，左侧或右侧，则与矩形的最小距离是垂直或水平方向绘制的直线重点。例如，如果您的点是（40，90）并且矩形的左下角是（0,0）（并且它是50x50的正方形），则可以在您的点上绘制一条垂直线，并且距离是min（90- （0 + 50），90-0）

如果该点不在正方形边的上方，下方，左侧或右侧，则最接近的距离是四个角中最接近的一个。您可以简单地获取到四个角的所有距离中的最小值，这可以通过使用距离公式来找到。

只需将此逻辑应用于数组中的每个正方形，就可以了！时间O（NM），其中n是正方形的行数，M是正方形的列数。换句话说，O（您拥有的平方数）。空格O（1）。

Answer 2

让我们从一个更简单的问题开始：所有矩形的宽度均为55个单位，即它们之间没有空白...

最好的容器是您不需要的容器。数组中正方形的i和j索引与其m和n坐标之间有一个简单的关系：

const int distance = 55;
int m(int i) { return i*distance; }
int n(int j) { return m(j); }

由于该关系是线性的，因此可以将其反转：

int i(int m) { return m / distance; }
int j(int n) { return i(n); }

这里使用整数算术很好，因为我们得到的结果与使用浮点数然后四舍五入的结果相同。

这已经是较简单问题的完整解决方案。给定坐标m和n，最接近的正方形位于索引i(m),j(n)。

现在让我们介绍一下差距：

cosnt int width = 50;
const int gap = 5;

现在，我们必须区分两种可能性：给定的坐标位于正方形内部或外部。在外面时，有两个最接近的正方形候选。

int i_with_gap(int m) {
     int i = m / (width + gap);

     // point is inside the square?
     if (m % distance <= width) return i;

     // point is closer to square at index i?
     if (m % distance <= width+ gap/2.0) return i;

     // otherwise i+1 is closer
     return i+1;
}