Быстрый поиск треугольника наименьшей площади

Быстрый поиск треугольника наименьшей площади

На заданном множестве точек найти треугольник с наименьшей площадью. Оптимизировать алгоритм, сократив перебор.

Если мы будем просто перебирать всевозможные пары вершин j и k, то сложность алгоритма будет O(N^3). Но можно пойти другим путём: зафиксировав некоторое i, отсортировать все остальные вершины, используя для сравнения X1 * Y2 < X2 * Y1. Теперь, если мы пройдёмся по отсортированному таким образом массиву вершин и рассмотрим каждую пару соседних вершин, то среди них мы обязательно рассмотрим треугольник минимальной площади. Теперь сложность будет равна O(N2*log N).

class dot {
public: 
  int x, y;
  dot() : x(0), y(0) {}
  dot(int a, int b) : x(a), y(b) {}
};
 
//класс треугольника
class triangle {
public:
  dot a, b, c;
  triangle() : a(), b(), c() {}
};
 
bool operator<(const dot &lhs, const dot &rhs)
{
  return lhs.x < rhs.x;
}
 
dot operator-(const dot &lhs, const dot &rhs)
{
  return dot(lhs.x - rhs.x, lhs.y - rhs.y);
}
dot operator+(const dot &lhs, const dot &rhs)
{
  return dot(lhs.x + rhs.x, lhs.y + rhs.y);
}
 
int cross(const dot &lhs, const dot &rhs)
{
  return lhs.x * rhs.y - rhs.x * lhs.y;
}
 
bool my_cmp(const dot &lhs, const dot &rhs)
{
  return lhs.x * rhs.y < rhs.x * lhs.y;
}
 
vector<dot> x;
 
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;
 
  switch (message)
  {
  case WM_COMMAND:
    wmId    = LOWORD(wParam);
    wmEvent = HIWORD(wParam);
    break;
  case WM_PAINT:
    hdc = BeginPaint(hWnd, &ps);
    {
      const int R = 4;
      HBRUSH oldBrush = (HBRUSH) SelectObject(hdc, CreateSolidBrush(0));
      HPEN oldPen = (HPEN) SelectObject(hdc, CreatePen(0, 1, 0));
 
      int p = 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() > 4) {
        DeleteObject(SelectObject(hdc, CreatePen(0, 2, RGB(255, 255, 255))));
 
        triangle mtr;
        const double EPS = 1E-8;
        const double INF = 1E+20;
        double result = INF;
        for (int i = 0; i < x.size(); ++i) {
          vector<dot> xx(x);
          //вычисляем координаты точек относительно точки x[i]
          for (int j = 0; j < xx.size(); ++j)
            xx[j] = xx[j] - x[i];
          //сортируем точки за O(n*log(n))
          sort(xx.begin(), xx.end(), my_cmp);
          for (int j = 1; j < xx.size(); ++j) {
            double s = 0.5 * (xx[j].x * xx[j - 1].y - xx[j].y * xx[j - 1].x);
            if (s > EPS && s < result) {
              result = s;
              mtr.a = x[i];
              mtr.b = xx[j-1] + x[i];
              mtr.c = xx[j] + x[i];
            }
          }
        }
        MoveToEx(hdc, mtr.a.x, mtr.a.y, 0);
        LineTo(hdc, mtr.b.x, mtr.b.y);
        MoveToEx(hdc, mtr.b.x, mtr.b.y, 0);
        LineTo(hdc, mtr.c.x, mtr.c.y);
        MoveToEx(hdc, mtr.c.x, mtr.c.y, 0);
        LineTo(hdc, mtr.a.x, mtr.a.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;
}

Ключевые слова: 
Треугольник, поиск, площадь, наименьшая площадь
ВложениеРазмер
tri.zip46.5 кб