|
В этом разделе представлены два алгоритма поиска минимального охватывающего эллипса.
Def<Ellipse2d> minEllipseAroundPoints ( double ext, CArrRef<Vector2d> points );Входные параметры функции: ext - удлинение эллипса ( 1e-6 ≤ ext ≤ 0.99 ) и points - массив точек. Второй алгоритм находит эллипс с оптимальным удлинением: Def<Ellipse2d> minEllipseAroundPointsA ( CArrRef<Vector2d> points );Результатом будет эллипс имеющий минимальную площадь. Краткое описание этого алгоритма: 1. Среди исходных точек находим три не лежащие на одной прямой. Если таких нет, то строим вырожденный ( с нулевой площадью ) эллипс и выходим из алгоритма. Иначе эти три точки считаем опорными и строим по ним эллипс. 2. Начало цикла. 3. Находим точку самую удалённую ( в специальной метрике ) от текущего эллипса. Если это расстояние равно нулю, то выходим из алгоритма. 4. Включаем эту точку в набор опорных точек. Для этого перебором строим новый элиипс для которого эта точка и старые опорные были бы внутри. К-во новых опорных точек будет не больше, чем пять - это к-во степеней свободы для эллипса. 5. Идём в начало цикла. В приложении DEMO показано, как применять эти функции.
Описание шаблона классов CArrRef находится здесь.
|