|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 03 Nov 2001 02:53:04
To : Yurij Zabelyshynskij
Subject : Re: Maximal area rect
--------------------------------------------------------------------------------
Hi Yurij,
"Yurij Zabelyshynskij" <ergo@sky.net.ua> wrote in message
news:9rv5b7$6mm$1@ddt.demos.su...
> > 1) Hаходим площадь и центр многоугольника, а также его осевые
> > моменты относительно x и у (простым интегрированием).
> > 2) Строим прямоугольник с центром в центре многоугольника, с
> > таким же соотношением моментов, и плошадью равной pi/2 от площади
> > многоугольника (коэффициент, в принципе, можно подкорректировать
> > эмпирически).
>
> Спасибо, но у меня возникли разногласия:)
> 1) Если находить моменты относительно координатных осей, то у нас
> появится зависимость от координатной системы, что совсем нехорошо.
> Скорее уж относительно прямых, проходящих через центр.
Это и имелось в виду :) Я приписал направление осей, чтобы отличить
от главных моментов (повернутых так, что один - максимальный,
а другой - минимальный). Подзабыл терминологию :(
> 2) Если не ошибаюсь, для вычисления моментов нужна какая-то величина,
> кроме координат, чей момент и считается (масса, вероятность...). Или
> ты предлагаешь поместить во все вершины единичную массу? Или
> распределить ее по ребрам? Или я тебя не понял? :)
Момент самого многоугольника (равномерно распрелеоенной плотностью)
Hадо посчитать интегралы
площадь
A = int (A) 1dxdy -
первые моменты
Sx = int(A) ydxdy
Sy = int(A) xdxdy
откуда находим центр
Xc =Sy/A;
Yc =Sx/A;
и первые моменты относительно центра равны нулю.
вторые моменты (или просто моменты :)
Ix = int(A) (y-Yc)^2 dxdy
Iy = int(A) (x-Xc)^2 dxdy
> 3) Все это хорошо, если есть центр прямоугольника, но как раз его
> поиск и является IMHO основной трудностью.
центр искомого прямоугольника == центр данного многоугольника
> А вот идея отношения сторон прямоугольника не равного отношению для
> описанного прямоугольника действительно может пригодиться.
идея простая - строим эллипс по интегральным параметрам равный
исходному мноугольнику и берем максимальный вписанный в него
прямоугольник.
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
