algorithm - 人工检查员与程序员(原为 : Algorithm to detect if any circles overlap)

Question

问题

这个问题实际上是今天在工作中提出的。我们正在计划一项实验，我们将向用户展示一系列 map 。每张 map 上都有 31 个符号。每个符号也有一个标签。我们注意到，在少数情况下，标签重叠，导致其中一个标签不可读。

我们最终以老式的方式识别问题符号——通过一张一张地查看每张 map 并记下我们发现的任何问题符号的 ID——但我认为这个问题可以很容易地解决一种算法。目视检查所有 map 花了大约一个工时(使用公认笨重的实验数据收集工具)。

我很好奇这个网站上的人能多快解决这个问题，我也很想知道你想出了什么样的算法。 (注意:这不是作业问题，尽管我认为它会成为一个有趣的作业或面试问题。)

规范

• map :24
• map 大小(像素):1024 X 768
• 每张 map 的符号(圆圈):31
• 符号直径(像素):60

符号坐标存储在包含以下列的电子表格(假设为制表符分隔的文本文件)中:

• MapId(范围:1 - 24)
• SymbolId(范围:1 - 744(24 个 map x 31 个符号/ map = 744 个符号总数)
• X坐标(范围:0 - 1024)
• Y坐标(范围:0 - 768)

假设所有四列都包含整数。

目标

你能多快想出一个算法(你选择的语言):

1. 读入包含输入数据的制表符分隔文本文件。
2. 为每张 map 确定是否有任何符号重叠。
3. 如果有任何符号重叠，报告哪些 SymbolId 违规

你的答案应该包含

1. 您的算法必须满足所有三个目标(上述)。
2. 您花了多长时间才想到并写下它(您很荣幸)。注意:您无需计算阅读和理解问题所花费的时间，但一旦您开始思考解决方案的想法，就开始计时。

我对您的算法运行速度或内存使用效率不感兴趣。我正在寻找一个快速、肮脏但准确可靠的问题解决方案。

Answer 1

对于每张 map :

If distance(A.center, B.center) < (A.radius+B.radius)
   the circles overlap.

在您的情况下，似乎每个圆都具有相同的半径，但为了以防万一，我允许每个圆具有不同半径的可能性。

至于想出多长时间，很难准确地说——比加载包含完整描述的页面所花的时间还少。然后我不得不做一些阅读以确认基本问题是标题中出现的问题......

编辑:如果你有很多圆圈，可能值得进行一些排序以消除不必要的重叠测试，但如果每张 map 只有大约 30 个圆圈，那可能不值得——你需要一台真正古老的计算机这需要整整一秒钟。

抱歉，我不得不离开一会儿带 children 去看一场轮滑曲棍球比赛。不管怎样，虽然我还没有测试过，但这是我在大约 10-12 分钟内为 C++ 程序生成的结果(我必须在那里打个电话，所以我没有确切的时间):

#include <vector>
#include <math.h>
#include <iostream>

struct point { 
    int id, x, y;
};

std::istream &operator>>(std::istream &is, point &p) { 
    return is >> p.id >> p.x >> p.y;
}

typedef std::vector<point> map;

double dist(point const &a, point const &b) { 
    double x=a.x-b.x;
    double y=a.y-b.y;
    return sqrt(x*x+y*y);
}

int main() { 
    std::vector<map> maps(24);
    int mapID;
    while (std::cin>> mapID) {
        point temp;
        std::cin >> temp;
        maps[mapID].push_back(temp);
    }

    for (int i=0; i<maps.size(); i++)
        for (int j=0; j<maps[j].size(); j++) 
            for (int k=j; k<maps[j].size(); k++) 
                if (dist(maps[i][j], maps[i][k]) < 60)
                    std::cout 
                        << "map " << i << "\t" 
                        << maps[i][j].id 
                        << " overlaps with " 
                        << maps[i][k].id << "\n";
    return 0;
}

我还没有真正测试过它，所以可能需要 5 到 10 分钟(或按顺序)来确保它正常工作，但我不希望有更长的时间。无论如何，我希望一个人能在一小时内完成。如果您习惯了 AWK 或 Perl 之类的东西，我希望它能更快地完成——不过，老实说，这已经足够微不足道了，主要归结为减少了输入……