Подскажите пожалуйста где искать/читать:
Есть кривая (массив точек).
Необходимо определить координаты минимального по площади прямоугольника описывающего
данную кривую и гол наклона этого прямоугольника относительно оси координат.
Здравствуйте, sbj, Вы писали:
sbj>Есть кривая (массив точек). sbj>Необходимо определить координаты минимального по площади прямоугольника описывающего sbj>данную кривую и гол наклона этого прямоугольника относительно оси координат.
Строим выпуклую оболочку этой кривой.
Поскольку она задана набором точек (скажем, N штук), то оболочка — это многоугольник (скажем, K-сторонний).
Находим описывающие прямоугольники, соосные поочерёдно каждой стороне оболочки. Среди них — ищем минимальный по площади.
O(N*log(N)) на построение оболочки.
O(K^2) для тупого перебора прямоугольников (для каждого за линейное время находим минимумы-максимумы координат вершин оболочки в повёрнутой системе координат). А если запоминать крайние вершины — то O(K).
Перекуём баги на фичи!
Re: Минимальный прямоугольник описывающий кривую
От:
Аноним
Дата:
03.05.06 13:33
Оценка:
Здравствуйте, sbj, Вы писали:
sbj>Подскажите пожалуйста где искать/читать: sbj>Есть кривая (массив точек). sbj>Необходимо определить координаты минимального по площади прямоугольника описывающего sbj>данную кривую и гол наклона этого прямоугольника относительно оси координат.
Сначала ищем угол наклона, потом поворачиваем на него кривую и находим прямоугольник в горизонтальном положении
Как найти угол наклона, расписано, например, здесь
Здравствуйте, Аноним, Вы писали:
А>Сначала ищем угол наклона, потом поворачиваем на него кривую и находим прямоугольник в горизонтальном положении А>Как найти угол наклона, расписано, например, здесь
Во-первых, там решалась другая задача: найти направление, в котором фигура "наиболее вытянута" (грубо говоря, это направление, в котором прямоугольная оболочка имеет наибольшее соотношение сторон; а точнее, это направление наибольшей оси эллипсоида инерции выпуклой оболочки).
Во-вторых, эти задачи даже близко не лежат. Контрпример: ромб. Наибольшая вытянутость — по диагонали, а наименьшая площадь — по стороне.
В-третьих, исходная задача имеет точное решение, а задача наибольшей вытянутости носит скорее эстетический характер.
Здравствуйте, Кодт, Вы писали:
К>Во-вторых, эти задачи даже близко не лежат. Контрпример: ромб. Наибольшая вытянутость — по диагонали, а наименьшая площадь — по стороне.
Согласен, конечно, контрпример с ромбом справедлив
К>В-третьих, исходная задача имеет точное решение, а задача наибольшей вытянутости носит скорее эстетический характер.
Конечно, такое решение не будет всегда точным, но для некоторых типов кривых вполне хорошо подойдет
Кроме того, оно быстрое, простое и красивое
Интересно было бы посмотреть, как ты будешь искать выпуклую оболочку для эллипса,
а потом полным перебором вокруг него бегать и считать площадь
Но в целом, конечно, выпад справедлив, признаю
Точное решение можно получить только полным перебором для выпуклой оболочки
Здравствуйте, sbj, Вы писали:
sbj>Подскажите пожалуйста где искать/читать: sbj>Есть кривая (массив точек). sbj>Необходимо определить координаты минимального по площади прямоугольника описывающего sbj>данную кривую и гол наклона этого прямоугольника относительно оси координат.
Здравствуйте, sbj, Вы писали:
sbj>Подскажите пожалуйста где искать/читать: sbj>Есть кривая (массив точек). sbj>Необходимо определить координаты минимального по площади прямоугольника описывающего sbj>данную кривую и гол наклона этого прямоугольника относительно оси координат.
если я правильно понял, то так:
-ищем таксимальные и минимальные значения точек
-соединяем (max.x min,y) c (min.x min.y)
-соединяем (min.x min.y) с (min.x max x)
-соединяем (min.x max,y) c (max.x min.y)
а потом ищишь угол через отношение сторон....
ну в этом случае не всегда получиться меньший, поэтому придется еще анализировать просто значения других координат в точкач min и max
Перекуём баги на фичи!
