인간의 관리자는 (이었다 알고리즘은 어떤 원이 겹치는 경우 감지)

Question

문제

이 질문은 사실은 오늘 직장에서 내놓았다. 사용자에게 일련의지도를 보여줄 실험을 계획 중입니다. 각지도에는 31 개의 기호가 있습니다. 각 기호에는 레이블이 있습니다. 우리는 몇 가지 경우에 라벨이 겹쳐서 라벨 중 하나를 읽을 수 없도록 만들었습니다.

우리는 문제가되는 기호를 구식으로 식별했습니다. 각지도를 하나씩 살펴보고 발견 한 모든 문제 기호의 ID를 적어 두었습니다. 그러나이 문제가 아주 쉽게 해결되었을 수 있다고 생각했습니다. 알고리즘으로 시각적으로 모든지도를 확인하는 데 약 한 시간이 걸렸습니다 (시시한 clunky 실험 데이터 수집 도구 사용).

이 사이트의 사람들이이 문제를 얼마나 빨리 해결할 수 있는지 궁금합니다. 어떤 알고리즘을 생각해 내는지 궁금합니다. (참고 :.이 숙제 질문하지 않습니다, 나는 그것이 흥미로운 숙제 또는 면접 질문을 할 것이라고 생각하지만)

사양

• 지도 : 24
• 지도 크기 (픽셀) : 1024 지도 당 X 768 개
• 기호 (원) : 31
• 기호 직경 (픽셀) : 60

기호 좌표는 다음과 같은 열이 (탭으로 구분 된 텍스트 파일을 가정) 스프레드 시트 테이블에 저장됩니다

• MapId (범위 : 1 - 24)
• SymbolId (범위 : 1-744 (24 개지도 기호 X 31/744 개 = 맵 전체 심볼)
• XCoordinate (범위 : 0 - (1024))
• YCoordinate (범위 : 0 - 768)

모든 가정 네 개의 열은 integers입니다.

목표

당신이 알고리즘 (선택한 언어)이 가지고 올 수 얼마나 빨리 :

1. 는 입력 데이터가 포함 된 탭으로 구분 된 텍스트 파일에서 읽습니다.
2. 각지도에 대해 기호가 겹치는 지 여부를 결정합니다. 어떤 문자가 겹치는 경우
3. , SymbolId의이 위반

에있는 보고서는 대답은 위 세 가지 목표를 달성해야하는,

1. 귀하의 알고리즘을 포함해야합니다.
2. 당신이 그것을 생각하고 쓰는 데 얼마나 오랜 시간이 걸렸습니까 (당신은 존중받습니다). 참고 : 질문을 읽고 이해하는 데 걸리는 시간을 계산할 필요는 없지만 솔루션에 대한 아이디어를 생각해 내면 시계를 시작하십시오.

알고리즘의 실행 속도 또는 메모리 사용 효율에 관심이 없습니다. 나는 문제에 대한 빠르고 더럽지 만 정확하고 신뢰할만한 해결책을 찾고있다. 각 맵에 대한

Answer 1

, 나는 쿼리를 통해 실행하는 것 :

select 
    s1.symbolId,s2.symbolId 
from 
    symbols s1 
    join 
    symbols s2 
where 
    s1.mapid=s2.mapid 
    and 
    s1.symbolid<s2.symbolid 
    and 
    ((s1.xcoordinate-s2.xcoordinate)* 
    (s1.xcoordinate-s2.xcoordinate)+ 
    (s1.ycoordinate-s2.ycoordinate)* 
    (s1.ycoordinate-s2.ycoordinate)) 
    <(r+r)*(r+r) 

(약 5 분 아마 몇 가지 실수로)

Answer 2

:

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

귀하의 경우는 모든 원이 동일한 반경을 가지고 나타납니다,하지만 난 단지의 경우, 다른 반경을 갖는 각 원의 가능성을 허용했습니다.

얼마나 오래 생각해 내는지에 관해서는 말하기가 약간 어렵지만 전체 설명으로 페이지를로드하는 데 걸리는 시간보다 적습니다. 그렇다면 기본적인 문제가 제목에서 나온 것임을 확인하기 위해 독서를해야했습니다 ...

편집 : 서클이 많았다면 불필요한 테스트를 제거 할 가치가 있습니다. 겹치기는하지만지도 당 ~ 30 개의 원만 있으면 가치가 없을 것입니다. 실제로 고대의 컴퓨터가 필요합니다.

죄송합니다. 아이들을 롤러 하키 경기에 데려 가기 위해 잠시 떠나야했습니다. 어쨌든, 내가 그것을 테스트하지는 못했지만, 여기에 C++ 프로그램을 위해 10-12 분 정도의 시간이 걸릴 것입니다 (정확한 시간이 없으므로 전화를 걸어야했습니다) :

#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 분 이상 걸릴 수 있지만 더 오래 걸릴 것으로는 기대하지 않습니다. 여하튼 한 사람이 1 시간 이내에 잘 끝나기를 기대합니다. AWK 나 Perl과 같은 것에 익숙하다면 조금 더 빨리 끝내기를 기대합니다. 그러나 정직하게 말하자면, 이것은 타이핑을 줄이기 위해 주로 사용됩니다 ...

Answer 3

내 첫 번째 생각 간단한 O (N) 알고리즘 Jerry가 이미 게시 한 간단한 예외 : 거리 은 제곱근을 필요로하지 않으므로 계산하기가 쉽기 때문에 (반지름 합계) ^{과 비교하십시오 2}.

두 번째 생각은 모든 포인트를 포함하는 quadtree으로 솔루션을 향상시키는 것입니다. 이는 비교해야 할 비교 횟수를 줄이는 데 도움이됩니다.

이 답을 쓰는 데는이 솔루션 중 하나를 생각하는 것보다 길었습니다 (아마도 10 초). 이런 종류의 문제는 컴퓨터 그래픽에서 매우 흔한 일입니다. 저는 전에 보았던 것을 반항합니다.

---

하스켈에서 솔루션을 하나의 구현을 신속하게 작성 (1 분했다) :

규정 문제와

import Control.Monad 
import Data.List 
radius = 30 
main = do 
    points <- fmap (map (map read . words) . lines) getContents 
    mapM_ print $ overlapping (points :: [[Int]]) 
overlapping list = do 
    [m1, s1, x1, y1]:rest <- tails list 
    [m2, s2, x2, y2] <- rest 
    guard $ m1 == m2 && (x2-x1)^2 + (y2-y1)^2 < 2*radius^2 
    return ((m1, s1), (m2, s2)) 

, 즉 3e5 비교보다 적은이다; quadtree 삽입/검색을 작성하는 것은 가치가 없을 것입니다. 비교가 3000 클럭 사이클을 거쳤더라도 (분명히하지는 않겠지 만) 여전히 1 초 이내에 완료 될 것입니다.

Answer 4

답변을 빨리 할 수있는 방법을 찾으려면 "스윕하고 치우기"를 시도해보십시오.

Answer 5

여기가 보다 빠릅니다. O (n^2) 여기서 n은 기호의 수입니다. STL vector과 같은 동적 배열 행렬을 사용하여 이미지의 각 픽셀을 나타냅니다. 각 원이 차지하는 픽셀을 계산하고 pushSymbolID을 원의 각 픽셀 배열에 계산합니다. 모든 서클을 끝내고 나면 각 픽셀을 살펴보고 어떤 픽셀에 배열에 심볼이 두 개 이상있는 경우 어떤 SymbolID이 위반인지 알 수 있습니다. 촬영

시간 : ~ 5 분

UPDATE

: 새로운 요구 사항으로, 내 최초의 알고리즘이 약간 각 행에서 읽은 나는 각각의 기호 위에 정의한 픽셀 - SymbolID 맵을 업데이트하도록 수정 될 수있다 다음지도로 이동하십시오. 스프레드 시트 소프트웨어에서 SQL 권한을 가정