두 점으로 눈금이 있습니다. 나는 각 점이 다른 점 앞에 도달 할 수있는 양의 제곱을 계산하려고합니다. 현재 필자는 FloodFill-Algoritm을 구현합니다.이 알고리즘은 한 지점에 도달 할 수있는 제곱의 양을 계산할 수 있습니다.FloodFill- 알고리즘을 변경하여 두 개의 데이터 포인트에 대해 보로 노이 테리토리를 얻으시겠습니까?
두 알고리즘 모두에 대해 "홍수"를 실행하려면 어떻게 알고리즘을 변경할 수 있습니까?
"각 포인트가 다른 포인트보다 먼저 도달 할 수 있음"이란 무엇을 의미합니까?
BF 검색이 필요하신 것처럼 보입니다. 다음과 같이 FIFO 대기열을 사용하십시오.
p1과 p2를 두 점의 위치라고합시다.
f를 대기열의 첫 번째 요소로, l을 마지막으로 놓습니다. 처음에는 f = 0, l = 1입니다. Q를 대기열이라고 합니다.
Q[f] = p1
Q[l] = p2
while (f <= l)
{
poz = Q[f];
++f;
for each neighbour poz' of poz
if poz' hasn't been marked yet
{
mark poz'
add poz' to Q: Q[++l] = poz
}
}
Q는 그리드 (행 x 열)의 크기 여야합니다. p1이 도달 할 수있는 위치와 p2가 도달 할 수있는 위치 중 하나를 사용하거나 두 개의 행렬을 사용하여 p1이 양수로 도달하고 squares p2가 음수로 도달 함을 표시 할 수 있습니다. 그들이 만나는 곳에 관심이 있다면 음수 값 (poz negative 및 poz 'positive) 또는 그 반대의 양수 값을 표시 할 것인지 확인해야합니다. 이것은 기본적으로 홍수를 번갈아 가며합니다 : 홍수가 p1에서 나온 다음 p2에서, 다음으로 p1에서, 그런 다음 p2에서 홍수가 발생합니다.
인사말, Google AI 참가자 : –
감사합니다. 이미 구현 했습니까, 아니면 다른 전략입니까? – Sven
나는 단지 두 가지 점에서 동시적인 BFS의 종류를 사용했다. IVlad의 대답과 비슷하다. –