2D 부울 행렬에서 가장 가까운 "참"원소를 찾으시겠습니까?

Question

나는 매우 자주 업데이트되는 부울 값을 가진 2D 행렬을 가지고 있습니다. 매트릭스에서 2D 인덱스 {x, y}를 선택하고 모든 요소를 ​​거치지 않고 테이블에서 "true"인 가장 가까운 요소를 찾고 싶습니다 (매트릭스가 큽니다). 예를 들어

, 나는 행렬이있는 경우 :

0000100 
0100000 
0000100 
0100001 

을하고 난 {x1, y1} 같은 좌표 선택 {4, 3}, 나는 가장 가까운 "true"로 값의 위치를 ​​반환하려는이에있는 대소 문자는 {5, 3}입니다. 요소 사이의 거리는 표준 피타고라스 방정식을 사용하여 측정됩니다.

distance = sqrt(distX * distX + distY * distY)distX = x1 - x 및 distY = y1 - y입니다.

매트릭스의 모든 요소를 ​​살펴보고 "실제"값 목록을 유지하고 가장 짧은 거리 결과를 갖는 목록을 선택할 수 있지만 매우 비효율적입니다. 검색 시간을 줄이기 위해 어떤 알고리즘을 사용할 수 있습니까?

세부 정보 : 매트릭스 크기는 1920x1080이며 모든 프레임마다 약 25 개의 쿼리가 생성됩니다. 전체 매트릭스는 매 프레임마다 업데이트됩니다. 합리적인 프레임 속도를 유지하려고하는데, 7fps 이상이면 충분합니다. 행렬이 항상 업데이트되는 경우

Answer 1

, 다음 거리 같은 일부 auxillary 구조를 구축 할 필요가 없습니다 변환, Voronoy 다이어그램 등을 질의 지점에서 전파

당신은 단지 BFS (빵 우선 탐색)과 같은 검색을 할 수 있습니다 . 일반적인 BFS와 유일한 차이점은 유클리드 지표입니다. (u 또는 v가 제로의 경우 8 점, 그렇지 않으면, 네 개의 점) 그래서 당신은

Answer 2

당신은 쿼드 트리와 같은 트리 데이터 구조를 사용할 수있다 (https://en.wikipedia.org/wiki/Quadtree를 참조 (u^2+v^2)의 지시 (u, v)쌍를 생성하고 (+-u,+-v),(+-v,+-u) 조합에 의해 이동 대칭 포인트를 확인하실 수 있습니다)를 사용하여 "true"값을 갖는 모든 위치를 저장하십시오. 이 방법으로 주어진 위치의 이웃에있는 모든 "참"값을 신속하게 반복 할 수 있어야합니다. 또한 위치의 값이 변경되면 트리는 로그 시간으로 업데이트 될 수 있습니다.