Войти
ПрограммированиеФорум2D графика и изометрия

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

Advanced: Тема повышенной сложности или важная.

Страницы: 1 2 Следующая »
#0
23:52, 26 янв. 2011

Доброго всем времени!
Необходимо описать прямоугольник вокруг массива точек, да не просто найти диапазоны границ этого массива по XY, а подобрать прямоугольник с наименьшей площадью.
Подскажите, пожалуйста, может кто знает какие-нибудь способы, желательно быстрые?


#1
23:55, 26 янв. 2011

Ээээ, как это - прямоугольник с наименьшей площадью? Тебе нужно чтобы _все_ точки входили в прямоугольник? Тогда площадь будет одна-единственная.

#2
0:08, 27 янв. 2011

Flamer
> Ээээ, как это - прямоугольник с наименьшей площадью? Тебе нужно чтобы _все_
> точки входили в прямоугольник? Тогда площадь будет одна-единственная.
Это если прямоугольник не крутить.

#3
0:18, 27 янв. 2011

Крутить нужно.
Мне пока в голову пришла идея перебрать все пары точек, на основе каждой пары выстраивая прямоугольник (линию, соединяющую эти две точки брать как базис) и вычислять его площадь, потом выбрать прямоугольник с наименьшей площадью. Но это какой-то прям брутфорс.

#4
0:49, 27 янв. 2011

Найти convex hull,  а дальше плясать от отрезков, его составляющих.
Как-то так наверно...

#5
1:15, 27 янв. 2011

находишь матрицу ковариации для всего множества точек, из нее основные оси элипса(собственные вектора), по ним строишь бокс

#6
5:47, 27 янв. 2011

Синий Дракон
вот здесь кое-что есть

#7
6:58, 27 янв. 2011

Nikopol
мне кажется, что прямоугольник должен касаться одной из сторон convex hull, но обосновать не могу

#8
8:19, 27 янв. 2011

Думаю из точек можно организовать сеточный граф простым разбиением в сетку. Потом просто найти остовку  с наименьшим весом, например алгоримом Краскала. По получившемуся дереву просто найти наиболее глубокую ветку. В итоге знаем две точки и длинну диагонали. Дабы понять как направлен прямоугольник, просто взвешиваем это дерево. Куды больше, туды и направлен, причем крайней точкой и будут самые глубокие ветки в взвешеном графе.  Так кажется, должно быть наиболее эффективным. Хотя, нет, нет. Вторую часть, лучше сделать, как расстояние от точек до прямой, ибо взвешивание тикаемким будет.

#9
8:33, 27 янв. 2011

http://blog.gamedeff.com/?p=168

#10
11:46, 27 янв. 2011

Пере6рать все точки и получить max и min по всем осям, исходя из координат точки. получаем AABB. А если позицию каждой точки умножить на матрицу вращения, то получим значения для вращающегося прямоугольника. Вроде 6ы так. Хотя, возможно, я и не так понял задачу.

#11
14:13, 27 янв. 2011

Hartmann
Жесть какая. Но спасибо за информацию.

CoolDev
Спасибо огроменное, то что нужно, как раз по профилю. Вопрос можно считать закрытым.

#12
17:21, 27 янв. 2011

crazy_miner
> находишь матрицу ковариации для всего множества точек, из нее основные оси
> элипса(собственные вектора), по ним строишь бокс
это будет не обязательно точным решением в случае облака точек, верно?

#13
20:33, 27 янв. 2011

Suslik
конечно, но "точное" чаще всего не нужно

#14
22:21, 27 янв. 2011

так... как я вижу:

1. Найти две самые удаленные точки.
2. Провести между ними прямую а.
3. Найти справа и слева от прямой самые удаленные от нее точки
4. Провести две линии b, c
5. Принять за длину прямоугольника прямую а, а за ширину длину прямой b+c
6. Ориентировать прямоугольник по прямой а

Сложность будет Sum[from 1 to n](n)+Sum[from 1 to n-2](n)

Но будет ли прямоугольник минимальным... не знаю.

Страницы: 1 2 Следующая »
ПрограммированиеФорум2D графика и изометрия

Тема в архиве.