Доброго, всем, времени суток.

Условие:
Есть контур растровой фигуры.
Требуется:
Найти контур этой фигуры представленный векторно, с наименьшей погрешностью между площадями растровой и векторной фигуры и с наименьшим количестов вершин последней.

В данный момент существует такое решение:
Находиться максимальное расстояние между точками на контуре растровой фигуры. И оно принимается за радиус описанной окружности, после этого находиться середина отрезка, которая является центром описн. окр-ти O (очевидно).

Окружность разбивается на количество вершин Vn(задаются опционально) потом находятся точки растрового контура T лежащие на прямых OVi (где i=0;Vn-1) Vi=T,
после этого вершины полученного многоугольника соединяются прямыми
потом проводиться проверка на избытычность вершин.

Проблема в том чтобы добиться заданной погрешности между площадями не засчет первоначального увеличения количества вершин.

Помогите кто знает (заодно математику с геометрией вспомните )

Для представления конечной векторной фигуры можно использовать только прямые?

Цитата(Lan @ 12.3.2004, 12:11)

Для представления конечной векторной фигуры можно использовать только прямые?

Конечно, ведь вектор поумолчанию - это направленный прямолинейный отрезок

Тем более, что описание фигуры кривыми увеличит количество вершин, а их нужно по возможности уменьшить.

Так ты определи тогда, что тебе надо - более точное описание фигуры или меньшее число вершин. Коэффициент какой-нибудь введи...

Потому-что, большего соответствия можно достигнуть, используя, например, кривые Безье.

Цитата(Lan @ 13.3.2004, 01:11)

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

Мне надо найти такое описание чтобы количество вершин и погрешность описания были минимальны и главное чтобы это было описано векторами.

Цитата

количество вершин и погрешность описания были минимальны

Ну что ты всё про это говоришь...

Ты сам подумай - по твоим словам выходит, что - "самый лучший способ - три вершины и максимально соответствующая площадь". Ну не получится такого! В очень редких случаях только.

Прими, например, такое соотношение вершин/площади

kS * S + kK * K = 1

где
kS, kK - коэффициенты важности для тебя того, что-бы площадь и вершины, соответственно, достигли оптимальных значений. Изменяются от 0 до 1. kS + kK = 1.
S - процент достижения площадью оптимального значения (оптимум - значение площади исходной растровой фигуры). 0 <= S <= 1.
K - процент достижения оптимального количества вершин (оптимум - 3 вершины). 0 <= K <= 1.

И используй потом свой алгоритм построения... БОльшего ты всё равно не добьёшся, если использовать только вектора.

Можно предложить небольшую модификацию, только.

Например, найти все точки контура. Потом немного убрать количество этих точек, путём отбрасывания тех, которые лежат на одной прямой, кроме конечной и начальной.

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

Цитата(Lan @ 13.3.2004, 12:34)

Цитата количество вершин и погрешность описания были минимальны Ну что ты всё про это говоришь... Ты сам подумай - по твоим словам выходит, что - "самый лучший способ - три вершины и максимально соответствующая площадь". Ну не получится такого! В очень редких случаях только.

Я-то это понимаю, но ТЗ такое. А за совет спасибо, я все никак не мог придумать как завязать между собой количество вершин и площадь.

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

Про распознавание нарисованной фигуры мы тут как-то беседовали... Может там что полезного найдешь.

А ещё вспомним, как год назад говорили о распознавании...

http://forum.vingrad.ru/index.php?showtopic=8594

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

Цитата(cardinal @ 17.3.2004, 00:51)

Про распознавание нарисованной фигуры мы тут как-то беседовали... Может там что полезного найдешь.

Jcs, С распознованием проблем не возникло, а вот с преобразованием в вектор, проблем куча, так как хочется вершин поменьше и погрешность разумеется тоже. Но за ссылку спасибо идейки там интересные может когда-нить пригодятся

А насчет НС задумка хорошая может осмелюсь, как нить замутить.


Спасибо, что откликнулся.

Как выделить контур фигуры наверное ты знаешь...

Берешь точку на окружности, произвольно... Пробегаешь по всем точкам и запоминаешь их пока не вернешься в исходную...
Затем берешь туже точку (допустим Т1) и ищешь максимально удаленную от нее - Т2... в результате получается отрезок... T1-T2(Диаметр), а окружность разбивается на 2 дуги.
Далее рассматриваешь эти 2 дуги находишь максимальное расстояние от полученного отрезка/прямой до точки на одной-Т3 и другой-Т4 дуге... В результате получится уже 4 отрезка:
Т1-Т3, Т3-Т2, Т2-Т4, Т4-Т1 (то есть перечисленных по, к примеру, часовой стрелке...)
Далее аналогично... При этом точность такого приближения может задаваться порогом максимального расстояния от некоторой прямой до некоторой максимально удаленной точки на окружности...

Диаметр тебе скорее всего понадобится для расчета того самого порога, ведь чем он больше тем больше будет съедаться площади при одном и том же количестве вершин. Так что предлагаю ввести зависимость количества вершин от диаметра окружности.

Чем мог...

B2_Russia, спасибо.
попробую реализовать.
На бумаге, вроде все сходится