Быстрое нахождение точек с минимальным расстоянием

md.gif

На множестве точек найти пару с минимальным расстоянием. Оптимизировать алгоритм. Сократить перебор.

Простой алгоритм — перебор всех пар и вычисление расстояния для каждой — работает за O(n^2). Построим алгоритм O(n*log(n))по общей схеме алгоритмов "разделяй-и-властвуй" в виде рекурсивной функции, которой передаётся множество точек; эта рекурсивная функция разбивает это множество пополам, вызывает себя рекурсивно от каждой половины, а затем выполняет какие-то операции по объединению ответов. Операция объединения заключается в обнаружении случаев, когда одна точка оптимального решения попала в одну половину, а другая точка — в другую.

Разбивать множество точек на два будем согласно их x-координатам: фактически мы проводим некоторую вертикальную прямую, разбивающую множество точек на два подмножества примерно одинаковых размеров. Тогда возьмём среднюю после сортировки точку Pm и все точки до неё и саму отнесём к первой половине, а все точки после неё — ко второй половине. Теперь, вызвавшись рекурсивно от каждого из множеств A1 и A2, мы найдём ответы h1 и h2 для каждой из половинок. Возьмём лучший из них: h = min(h1, h2). Теперь надо произвести стадию объединения, т.е. попытаться обнаружить такие пары точек, расстояние между которыми меньше h, причём одна точка лежит в A1, а другая — в A2. Очевидно, что для этого достаточно рассматривать только те точки, которые отстоят от вертикальной прямой раздела не расстояние, меньшее h (множество B). Для каждой точки из множества B надо попытаться найти точки, находящиеся к ней ближе, чем h. Например, достаточно рассматривать только те точки, координата y которых отличается не более чем на h. Более того, не имеет смысла рассматривать те точки, у которых y-координата больше y-координаты текущей точки (множество C(Pi)).

Стадия объединения выглядит следующим образом: построить множество B, которое состоит из точек, x координата которых отличается от вертикальной линии не более, чем на h, отсортировать в нём точки по y-координате, затем для каждой точки Pi в B рассмотреть все точки Pj в C(Pi), которое состоит из точек B, у которых y координата не отличается более, чем на h и каждой пары (Pi, Pj) посчитать расстояние и сравнить с текущим наилучшим расстоянием.

class dot {
public: 
  int x, y;
  dot() : x(0), y(0) {}
  dot(int a, int b) : x(a), y(b) {}
};
 
bool cmp_x (const dot &a, const dot &b)
{
  return a.x < b.x || a.x == b.x && a.y < b.y;
}
 
bool cmp_y (const dot &a, const dot &b)
{
  return a.y < b.y;
}
 
double mindist;
dot ma, mb;
 
void upd_ans (const dot &a, const dot &b)
{
  double dist = sqrt ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) + .0);
  if (dist < mindist)
    mindist = dist,  ma = a,  mb = b;
}
 
std::vector<dot> x;
 
void rec(int l, int r)
{
  int i, j;
  if (r - l < 4) {
    for (i = l; i <= r; ++i)
      for (j = i + 1; j <= r; ++j)
        upd_ans (x[i], x[j]);
    sort(x.begin() + l, x.begin() + r + 1, cmp_y);
    return;
  }
 
  int m = (l + r) / 2;
  int midx = x[m].x;
  rec(l, m);
  rec(m + 1, r);
  inplace_merge(x.begin() + l, x.begin() + m + 1, x.begin() + r + 1, cmp_y);
 
  vector<dot> t;
  for (i = l; i <= r; ++i)
    if (abs(x[i].x - midx) < mindist) {
      for (j = t.size() - 1; j >= 0 && x[i].y - t[j].y < mindist; --j)
        upd_ans (x[i], t[j]);
      t.push_back(x[i]);
    }
}
 
void addDot(LPARAM lParam)
{
  x.push_back(dot(LOWORD(lParam), HIWORD(lParam)));
}
 
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
  int wmId, wmEvent;
  PAINTSTRUCT ps;
  HDC hdc;
  TCHAR szHello[MAX_LOADSTRING];
  LoadString(hInst, IDS_HELLO, szHello, MAX_LOADSTRING);
 
  switch (message) 
  {
    case WM_COMMAND:
      wmId    = LOWORD(wParam); 
      wmEvent = HIWORD(wParam); 
      break;
    case WM_PAINT:
      hdc = BeginPaint(hWnd, &ps);
      {
        const int R = 3;
        HBRUSH oldBrush = (HBRUSH) SelectObject(hdc, CreateSolidBrush(0));
        HPEN oldPen = (HPEN) SelectObject(hdc, CreatePen(0, 1, 0));
 
        for (int i = 0; i < x.size(); ++i) {
          DeleteObject(SelectObject(hdc, CreateSolidBrush(RGB(255, 0, 0))));
          DeleteObject(SelectObject(hdc, CreatePen(0, 2, RGB(255, 0, 0))));
          Ellipse(hdc, x[i].x - R, x[i].y - R, x[i].x + R, x[i].y + R);
        }
        if (x.size() > 2) {
          sort(x.begin(), x.end(), cmp_x);
          mindist = 1E20;
          rec(0, x.size() - 1);
 
          DeleteObject(SelectObject(hdc, CreateSolidBrush(RGB(255, 255, 255))));
          DeleteObject(SelectObject(hdc, CreatePen(0, 2, RGB(255, 255, 255))));
 
          Ellipse(hdc, ma.x - R, ma.y - R, ma.x + R, ma.y + R);
          Ellipse(hdc, mb.x - R, mb.y - R, mb.x + R, mb.y + R);
 
          DeleteObject(SelectObject(hdc, CreatePen(0, 2, RGB(255, 255, 255))));
          MoveToEx(hdc, ma.x, ma.y, 0);
          LineTo(hdc, mb.x, mb.y);
 
          DeleteObject(SelectObject(hdc, oldBrush));
          DeleteObject(SelectObject(hdc, oldPen));
        }
      }
      EndPaint(hWnd, &ps);
      break;
    case WM_LBUTTONUP:
      addDot(lParam);
      InvalidateRect(hWnd, 0, true);
      break;
    case WM_DESTROY:
      PostQuitMessage(0);
      break;
    default:
      return DefWindowProc(hWnd, message, wParam, lParam);
   }
   return 0;
}

Ключевые слова: 
Минимальное, расстояние, нахождение
ВложениеРазмер
md.zip37.9 кб