Próbuję zaimplementować prostszą wersję tego algorytmu, ale która działa lepiej niż algorytm kwadratowy. Moim pomysłem jest zasadniczo posortowanie punktów za pomocą tylko współrzędnej x i spróbuj ją rozwiązać. Kiedy już posortuję tablicę punktów według współrzędnej x, chcę przetestować tablicę i zasadniczo pominąć punkty, których odległość jest większa niż pierwsze dwa punkty, w które brałem.Najbliższa para algorytmów punktów
Na przykład mój currentminDist = x;
Jeśli dwie pary punktów, na które patrzę, mają odległość> x (tylko przy jej rozkładzie x coordin), ignoruję punkt i przesuwam go obok tablicy.
Mam pomysł w dół, ale jestem w pewien sposób utknąłem na tym, jak faktycznie to zaimplementować (zwłaszcza część warunku). Mam funkcję, która zwraca mi odległość między dwoma punktami na podstawie ich współrzędnej x.
Jestem zdezorientowany, jak właściwie zapisać moje warunki dla mojej pętli, ponieważ chcę zignorować punkt, jeśli odległość jest zbyt duża i nadal wypełniać moją tablicę, która będzie zawierała odpowiedzi dla najbliższych punktów dla każdego i (jestem aktualnym punktem, na który patrzę).
Wszelkie wskazówki i wskazówki są mile widziane. Nie znam się dobrze na algorytmach kodowania, więc jest to dość frustrujące.
Tutaj jest częścią mojego kodu:
for (i = 0; i < numofmypoints; i++)
{
for (int j = i + 1; (j < numpofmypoints) && ((inputpoints[j].x - inputpoints[i].x) < currbest); j++)
{
currdist = Auxilary.distbyX(inputpoints[i],inputpoints[j]);
if (currdist < bestdist)
{
closest[i] = j;
bestdist = currdist;
}
}
}
distbyX jest moja funkcja, która po prostu zwraca odległość między dwoma punktami.
Dzięki!
@Paul: czy trzeba to robić częściej? Nie zapisałbyś twoich punktów w pomocy "quadtree"? http://pl.wikipedia.org/wiki/Quadtree – TacticalCoder
Zauważ, że możesz uzyskać lepszą wydajność niż przy użyciu algorytmu naiwnego, ale nadal będziesz mieć "O (n^2)". – ARRG
Dlaczego w twoim kodzie są 'currbest' i' bestdist'? Jaka jest różnica? – Ishtar