Описать прямоугольник вокруг массива точек (2 стр)

MarkoPolo
> Но будет ли прямоугольник минимальным... не знаю.
не всегда: максимально удалённые точки могли по диагонали лечь, например:)

serpinf
> не всегда: максимально удалённые точки могли по диагонали лечь, например:)
Кстати да, по диагонали. Придумал еще один:

1. Находим две самые далеко стоящие точки.
2. Проводим через них отрезок а.
3. Копируем а, назвав его b
4. Поворачиваем b на какой-то угол к примеру 1 градус, каждый раз проверяя, все ли точки помещаются, поворачиваем в рамках от 0 до 90 градусов.
5. Первая найденная комбинация со всеми точками внутри, предположительно будет тем что искали с точностью 1 градус. Поворот обозначим через A
5а. Если точности мало, выделяем рамку [A-1 A+1] градусов, делим на n-частей и снова проверяем минимальный угол вхождения.

Но тоже не математическая ересь...

Сколько стоит проверка вхождения всех точек в OOB?

Chipmunk
> Это если прямоугольник не крутить.
Отжеж блин, протупил :)

Можно крутить не прямоугольник, а точки, вокруг центра тяжести фигуры, описанной контуром. Мне кажется что площадь будет минимальной, когда точки будут повернуты на такой угол, когда описывающий прямоугольник будет иметь минимальную длину одной из сторон.

Я уже реализовал алгоритм с перебором всех точек:
1. Перебираем все отрезки, образованные облаком точек - если точек n, отрезков будет (n-1)*n/2.
2. Для каждого отрезка вычисляем его направление (угол относительно какой-либо оси координат).
3. Выкидываем отрезки, если их угол совпадает с кем-либо или перпендикулярен кому-либо из отрезков (на этой стадии откидывается весьма много отрезков).
4. На базе каждого из оставшихся отрезков строим прямоугольник, вмещающий все облако точек, и вычисляем его площадь.
5. Выбираем прямоугольник с наименьшей площадью.

Без какой-либо оптимизации этот алгоритм вызывается у меня до 30 тысяч раз в секунду для одной сотни точек. Мне такого быстродействия пока хватает.