Здравствуйте друзья, такой вопрос:
как приблизить произвольный многоугольник прямоугольником, так чтобы сумма площадей отсекаемых и прибавляемых кусков была минимальна?
В opencv реализован поиск прямоугольника минимальной площади, окружающего данный — это не то, что нужно.
Есть ли какой-то готовый алгоритм (и его реализация на С++, в идеале)? Или какие-то разумные мысли, куда смотреть?
Здравствуйте, Che, Вы писали:
Che> Здравствуйте друзья, такой вопрос: Che>как приблизить произвольный многоугольник прямоугольником, так чтобы сумма площадей отсекаемых и прибавляемых кусков была минимальна?
Che> В opencv реализован поиск прямоугольника минимальной площади, окружающего данный — это не то, что нужно.
Che>Есть ли какой-то готовый алгоритм (и его реализация на С++, в идеале)? Или какие-то разумные мысли, куда смотреть?
Che> С уважением.
Мминимум достигается в положении, в котором длина каждой стороны прямоугольника ровно вдвое превышает длину пересечения этой стороны с исходной фигурой (либо касается некой грани исходной фигуры), ну просто по принципу "ищи положение, при котором микроперемещения не имеют смысла" (официально называется "лемма Ферма о локальном экстремуме"). Я бы искал этот минимум итеративно, чтоб не решать линейные уравнения.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Che>>как приблизить произвольный многоугольник прямоугольником
TB>(официально называется "лемма Ферма о локальном экстремуме"). Я бы искал этот минимум итеративно, чтоб не решать линейные уравнения.
Именно что о локальном экстремуме. Это для выпуклых многоугольников получаются быстрые алгоритмы (например). Для произвольных же многоугольников этих локальных минимумов — тьма.
Здравствуйте, T4r4sB, Вы писали:
TB>Здравствуйте, Che, Вы писали:
Che>> Здравствуйте друзья, такой вопрос: Che>>как приблизить произвольный многоугольник прямоугольником, так чтобы сумма площадей отсекаемых и прибавляемых кусков была минимальна?
Che>> В opencv реализован поиск прямоугольника минимальной площади, окружающего данный — это не то, что нужно.
Che>>Есть ли какой-то готовый алгоритм (и его реализация на С++, в идеале)? Или какие-то разумные мысли, куда смотреть?
Che>> С уважением.
TB>Мминимум достигается в положении, в котором длина каждой стороны прямоугольника ровно вдвое превышает длину пересечения этой стороны с исходной фигурой (либо касается некой грани исходной фигуры), ну просто по принципу "ищи положение, при котором микроперемещения не имеют смысла" (официально называется "лемма Ферма о локальном экстремуме"). Я бы искал этот минимум итеративно, чтоб не решать линейные уравнения.
Спасибо, действительно логично про половину каждой стороны. Понятно, что это дает ноебходимое условие локального экстремума. Я думаю, для моих целей этого вполне хватит. Хотелось бы, конечно, найти готовую программную реализацию чего-нибудь подобного, но вроде я и так придумал как более-менее разумно это реализовать.
