From Wikipedia, the free encyclopedia
Алгоритам две најближе тачке се користи у разним областима рачунарства. На пример, користи се у попуњавању површина на 3D моделима, за одређивање најкраћег растојања између елемената у електричним колима, детектовање судара два објекта и слично.
У равни је дато n тачака својим координатама (х, у). Одредити растојање на којем су две најближе тачке. Овде ћемо се бавити само дводимензионалним проблемом, мада се проблем може проширити и на више димензија.
Наивно решење проблема било би да проверимо растојање између сваке две тачке.
min = distance(points[0],points[1]);
for ( i = 0; i < n; i++)
{
for ( j = i+1; j < n; j++)
{
if (distance(points[i],points[j]) < min)
{
min = distance(points[i],points[j]);
}
}
}
Ово решење изискује О(n2) операција. Постоји боље решење.
Ово решење се заснива на принципу подели па владај. Алгоритам је следећи:
Да би се све то урадило, неоходно да су тачке сортиране по y координати.
Ако se не користи приступ последњег корака, сложеност је О(n2), јер је неопходно да се у последњем кораку упореде све тачке са сваком у нашем појасу. Међутим, ако се искористи тај приступ, морају се сортирати тачке у појасу (сложеност је О(n logn)), и остварује се линеарни пролаз кроз њих (О(n)), што на крају даје О(n logn) - бољу сложеност.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define BESKONACNOST 1E10
#define EPSILON 1E-10
#define MAX_VELICINA 1000
// definisemo strukturu Tacka
struct Tacka
{
double _x;
double _y;
Tacka () { _x = BESKONACNOST; _y = BESKONACNOST; }
Tacka ( double x, double y ) { _x = x; _y = y; }
};
// globalne promenljive
int n;
vector<Tacka> tacke(MAX_VELICINA);
bool sortirajPoX(const Tacka& A, const Tacka& B)
{
//if (A._x == B._x) return A._y < B._y;
return A._x < B._x;
}
bool sortirajPoY(int i, int j)
{
//if (tacke[i]._y == tacke[j]._y) return tacke[i]._x < tacke[j]._x;
return tacke[i]._y < tacke[j]._y;
}
// ovo vraca kvadrat rastojanja
double rastojanjeTacaka(const Tacka& A, const Tacka& B)
{
return (A._x - B._x) * (A._x - B._x) + (A._y - B._y) * (A._y - B._y);
}
double resi(int indeksiTacakaSortiranihPoY[MAX_VELICINA], int levi, int desni)
{
int i,j,k;
double dLmin,dDmin,dmin;
int N = desni - levi;
int s = (levi + desni)/2;
if (N <= 1) return BESKONACNOST;
if (N == 2) return rastojanjeTacaka(tacke[indeksiTacakaSortiranihPoY[0]], tacke[indeksiTacakaSortiranihPoY[1]]);
// podeli niz na dva dela
int b[MAX_VELICINA];
i=0;
j= s - levi;
for ( k = 0; k < N; k++)
{
if (indeksiTacakaSortiranihPoY[k] <= s && i < s-levi)
b[i++] = indeksiTacakaSortiranihPoY[k];
else
b[j++] = indeksiTacakaSortiranihPoY[k];
}
// nadji minimume u levoj i desnoj polovini rekurzivno
dLmin = resi(b,levi, s);
dDmin = resi(b,s+1, desni);
dmin = min(dLmin, dDmin);
// pronadji ako ima bolje resenje
int indeksiTacakaUPojasu[MAX_VELICINA];
int t = 0;
// izdvoj samo tacke u pojasu [-dmin,dmin] oko vertikalne linije koja razdvaja
for ( k = 0; k < N; k++)
{
if (fabs(tacke[indeksiTacakaSortiranihPoY[k]]._x - tacke[s]._x) - dmin < EPSILON)
{
indeksiTacakaUPojasu[t++] = indeksiTacakaSortiranihPoY[k];
}
}
// nadji rastojanja izmedju tacaka u pojasu i pronadji najmanje
for (int i=0; i<t-1; i++)
{
for (j= min(i+7,t-1); j>i; j--)
{
double rastojanje = rastojanjeTacaka(tacke[indeksiTacakaUPojasu[i]], tacke[indeksiTacakaUPojasu[j]]);
if (rastojanje < dmin)
{
dmin = rastojanje;
}
}
}
return dmin;
}
double najkraceRastojanje()
{
int indeksiTacakaSortiranihPoY[MAX_VELICINA];
for (int i = 0 ; i < n ; i++ ) indeksiTacakaSortiranihPoY[i] = i;
sort(tacke.begin(),tacke.begin()+n,sortirajPoX);
sort(indeksiTacakaSortiranihPoY, indeksiTacakaSortiranihPoY + n, sortirajPoY);
return resi(indeksiTacakaSortiranihPoY, 0, n);
}
int main()
{
double resenje;
// ucitamo broj tacaka
cin >> n;
// ucitavanje tacaka
for (int i=0;i<n;i++)
{
cin >> tacke[i]._x;
cin >> tacke[i]._y;
}
// nadjemo resenje
resenje = sqrt(najkraceRastojanje());
cout << resenje << endl;
return 0;
}
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.