Уже решённая мной задача "из жизни":

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

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

Вопрос:

Как можно быстро исправить ситуацию (все домики уже есть,
нужно только их подкорректировать)?

Здравствуйте, vvaizh, Вы писали:

V>Как можно быстро исправить ситуацию (все домики уже есть,
V>нужно только их подкорректировать)?

Есть три варианта:

либо:
1) Увеличить контраст.
либо:
2) Я что-то не так понял в условии...
либо:
3) Одно из трёх.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, vvaizh, Вы писали:

V>>Как можно быстро исправить ситуацию (все домики уже есть,
V>>нужно только их подкорректировать)?

А>Есть три варианта:

А>либо:
А>1) Увеличить контраст.
А>либо:
А>2) Я что-то не так понял в условии...
А>либо:
А>3) Одно из трёх.

Видимо под увеличением контраста предполагается утончение линий на растре
(растр — планшет 500-го масштаба, не полутоновое изображение, а
отсканированное с нанесённого тушью на специальную плёнку изображения, где интересующие
нас линии — толщиной ~0,5 мм)
Кроме того даже если вы "утончите" линии спец алгоритмом (которые действительно
существуют, хоть и в данном случае не очень годятся), вы не заставите "тётеньку-оператора"
монотонно в течении смены тыкать мышкой с точностью до пиксела..
Кроме того, углы в домах действительно не всегда абсолютно прямые

Кроме тоге, растр уже не нужен..
Все домики уже обведены... (второй раз работу делать неохота ~ 1000 домиков..)
Но — у дома с прямым углом, углы получились не совсем прямыми..
(такая вот погрешность ручной обводки толстых линий)

Потому мат. постановка задачи:

— имеется многоугольник, все углы которого "примерно" прямые..
— требуется найти @ближайший@ к нему многоугольник, все углы
которого уже будут прямыми

Вот понятие "ближайший" здесь уже не "строго" математическое,
хотя можно и такое найти..

Представтье прямоугольник нарисованный толстой черной линией (скажем толщиной 1 см)
Вы накладываете на него кальку, "на глаз" прицеливаетесь в серединку каждого угла,
и ставите точку. Обводите каждую точку тонким карандашом, убираете фон,
и видите что на кальке это уже совсем не прямугольник.. углы кривые

Здравствуйте, vvaizh, Вы писали:


V>- требуется найти @ближайший@ к нему многоугольник, все углы
V> которого уже будут прямыми

Чего ж я так плохо учился-то?
Из всех многоугольников со всеми прямыми углами мне известен только прямоугольник...
А их наверное много бывает?

В общем, задача-то как стоит?
Из произвольного четырехугольника сделаь прямоугольник?
А дополнительные требования (сохранение площади, периметра и т.д.) есть?

Здравствуйте, UgN, Вы писали:

UgN>Здравствуйте, vvaizh, Вы писали:

UgN>
V>>- требуется найти @ближайший@ к нему многоугольник, все углы
V>> которого уже будут прямыми

UgN>Чего ж я так плохо учился-то?
UgN>Из всех многоугольников со всеми прямыми углами мне известен только прямоугольник...
UgN>А их наверное много бывает?

Ну ещё бывает нечто вроде:

1 2
+----------+
| |
| 4 |
+-----+ |
3 | |
| |
+----+
5 6

6-угольник со всеми прямыми..
Ну и вообще, вы там что, в цирке сидите, или в чём то авангардном/кривом?
В здании как правило прямые углы, и не всегда их 4..
В общем любой 2*n угольник может иметь все углы прямые..


UgN>В общем, задача-то как стоит?
UgN>Из произвольного четырехугольника сделаь прямоугольник?
Ну правтически (конечно нечётное количество углов откидываем..)

UgN>А дополнительные требования (сохранение площади, периметра и т.д.) есть?
Я формулирую, так как задача была поставлена..
В этом то и прелесть __прикладного__
программирования/математики, а не __теоретического__.
Что "чёткой" постановки не существует..
Зато существует достаточно красивое решение, которое скажем мне в
голову пришло не сразу..

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

Здравствуйте, vvaizh, Вы писали:


V>Ну ещё бывает нечто вроде:

V>1          2
V>+----------+
V>|          |
V>|      4   |
V>+-----+    |
V>3     |    |
V>      |    |
V>      +----+
V>      5    6

V>Я формулирую, так как задача была поставлена..
V>В этом то и прелесть __прикладного__
V>программирования/математики, а не __теоретического__.
V>Что "чёткой" постановки не существует..

А из существующей ничего не пойму.
Вот бы пару картинок: Было — Стало (Реклама препарата для похудения)

Ну так могу предложить взять все точки, найти минимальные и максимальные координаты х и y,
а потом построить прямоугольник A( Xmin,Ymin ) B( Xmin,Ymax ) C( Xmax,Ymax ) D( Xmax,Ymin )
И сказать что это домик.

Или разбить исходную картинку на четырехугольники и сделать из них прямоугольники как описано выше.

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

( Угол считать по двум прямым, проведенным через точки 1 — 2 и 2 — 3 )

Сдраствуйте

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

Чем вы занимаетесь конкретно, может можно будет по сотрудничать

Здравствуйте, UgN, Вы писали:

UgN>Здравствуйте, vvaizh, Вы писали:

UgN>А из существующей ничего не пойму.
UgN>Вот бы пару картинок: Было — Стало (Реклама препарата для похудения)

Вот пример (красное — исходное, синее — результат..)


UgN>Ну так могу предложить взять все точки, найти минимальные и максимальные координаты х и y,
UgN>а потом построить прямоугольник A( Xmin,Ymin ) B( Xmin,Ymax ) C( Xmax,Ymax ) D( Xmax,Ymin )

Нет, это не подходит..

UgN>Или разбить исходную картинку на четырехугольники и сделать из них прямоугольники как описано выше.

Тоже

UgN>А можно просто последовательно обходить точки, рисуя отрезки, при этом углы принудительно делать прямыми.
UgN>( Угол считать по двум прямым, проведенным через точки 1 — 2 и 2 — 3 )

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

Здравствуйте, Kulibin, Вы писали:

K>Здраствуйте

K>Мы наверное конкуренты, я в своей системе эту проблемму
K>решел, алгоритм давльно хитрый с распределением ошибки, и
K>выбором оптимальных расположений.

Ну что вы, это же "этюд"
У меня алгоритм совсем несложный получился..
В том то и вся прелесть..

K>Чем вы занимаетесь конкретно, может можно будет по сотрудничать

Ну, два года назад я занимался ГИС (конкретно, написанием редакторов)
Сейчас работаю в несколько другой облаcти (где соотв. платят больше)
Так что я вам не конкурент.
Хотя конечно, коё в чём сотрудничать не прочь

В часности есть задел библиотеки редакторов..
типа Unidraw, по крайней мере то что написал в своё время по функциональности
мало уступало скажем AutoCAD.. Хотя организовано всё было много лучше,
да и для пользователя удобнее.. (некоторых фич я пока просто нигде не видел)
В общем если интересно — пишите, не пропадать же добру..

V>У меня алгоритм совсем несложный получился..

У меня вообм то тоже не сложный всё-таки математик как не как.

тут в начеле февраля будет выставка на ввц я там буду показывать своё

У меня решено огромное колличество алгоритмических приёмов,
Начнем с того что сканированное изображение сшивается в общее, с использованием деформаций, натяжек, все это дело может достигать размеров более 2 милионов на 2 милиона пикселей и занимать сотни гигабайт, а работает очень быстро, более 15 раз в секунду отрисовка идет, все считается в динамике, используется билиненйная фильтрация, и усреднение,
Вся эта красота (подложка) написана на ASM ипользуютс MMX сейчас я буду потключать 3dNow! с SSE пока проблеммы

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

Здравствуйте, vvaizh, Вы писали:

V>Потом растр убирают, показывают результат заказчику, а он говорит:
V>неееее... у домов то прямуе углы, а у вас какие то кривые..

V>Вопрос:

V>Как можно быстро исправить ситуацию (все домики уже есть,
V>нужно только их подкорректировать)?

Я бы сделал так.

1. Оцениваем погрешность тыкания.

2. Рассматриваем множество отрезков, составляющих контур. Сортируем их по углу, взятому по модулю 90 градусов (осторожно с граничными случаями).

3. Если соседние в отсортированном списке отрезки отличаются в пределах погрешности, то их угол считаем одинаковым (берем среднее). Получаем некоторое небольшое кол-во направлений. Если дом имеет только прямоугольные углы, то направление пости наверняка будет одно.

4. Для каждого направления в порядке убывания частоты и для каждой точки рассматриваем точки, лежащие на линии (в пределах погрешности), проведенные через нее в этом направлении (и в +90 градусов). Подравниваем эти точки.

5. Если точку уже подравняли, то дальнейшее подравнивание не должно уводить ее с этого направления. Соответственно, после двух подравниваний точку уже не трогают.

6. При желании можно учитывать направления соседних домов чтобы они вкривь не стояли.

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

Здравствуйте, Kulibin, Вы писали:

V>>У меня алгоритм совсем несложный получился..

K>У меня вообм то тоже не сложный всё-таки математик как не как.
K>тут в начеле февраля будет выставка на ввц я там буду показывать своё
В Москве я буду проездом, числа наверно 5, и 13 на обратном пути).
Зайду, гляну, если скажете куда..

K>У меня решено огромное колличество алгоритмических приёмов,
Да, занимался и этим, хотя ИМХО — лучше наверно взять готовую либу,
коих уже достаточно много (по крайней мере я их смотрел, и никаких
прёимуществ своих алгоритмов перед библиотечными не нашёл, чего не
сказать о редакторах)

K>Начнем с того что сканированное изображение сшивается в общее, с использованием деформаций, натяжек,
У нас такое было уже 5 лет назад
(http://ugp.udm.ru/ru/struct/1/06/automap/tour/page4.shtml),
причём нам было дешевле юзать дешёвые сканеры A3 или A4 со
своей спец программамой
(http://ugp.udm.ru/ru/struct/1/06/automap/tour/page6.shtml),
чем покупать дорогущий большой сканер..

K>все это дело может достигать размеров более 2 милионов на 2
K>милиона пикселей и занимать сотни гигабайт, а работает очень
K>быстро, более 15 раз в секунду отрисовка идет, все считается в
K>динамике, используется билиненйная фильтрация, и усреднение,
Ну Ижевск не Москва, сотни Гб нам тестировать особо не на чем..
Но 500-масштаб нашего города сплошным растром (~2.3Гб, тогда винты такие были..)
у нас очень хорошо работал..
А всё остальное естественно ограничивается не столько алгоритмами, сколько быстрой,
специализированной системой хранения на диске..

Сколько раз в секунду, я точно уже не помню, но векторный "город Ижевск"
(~30000 домов + куча другой мишуры) наша система рисовала в ~10 раз быстрее MapInfo
(короче, уже тогда всё практически помещалось в память, хотя система написана так,
что это не очень важно, и идёт и на 8 Mb)
А "растровый" рисовался даже побыстрее, так как мы как правило никаких сложных
преобразований непосредственно перед прорисовкой не делали, а сразу пихали готовый
растр на экран..

K>Вся эта красота (подложка) написана на ASM ипользуютс MMX сейчас я
K>буду потключать 3dNow! с SSE пока проблеммы
Крута..
Мы поступили проще, при вклейке планшета в карту, заранее масштабировали
(и, если нужно, поворачивали) его в 3-4 основных масштабах,
которых пользователю хватало..
Так что основная часть тут у нас была — система хранения,
и "летало" это всё ещё на Pentium I c 32 Mb..
(см. требования http://ugp.udm.ru/ru/struct/1/06/automap/techpar.shtml)
Конечно, был режим и получения "произвольного" масштаба
(который на тех тачках конечно был помедленнее, но сейчас наверно "летает",
так как хранили всё в bmp (чтобы не тратится на распаковку), и масштабировали
из ближайшего уже отмасштабированного уровня), но им редко пользовались..

K>На счет графического редактора интересует делалось ли создание
K>сложных приметивов (с использованием сплайнов, других кривых
K>совместно с другими приметивами, то что называется путями), я этим буду сейсас заниматься,
Были спец. редакторы:
— дорожной сети (граф, с перекрйстками и скруглениями)
— кульман (редко пользовались, но зато он гарантировал "любое" построение..)
— сплайны для ГИС как то не очень использовались, так что был простой, без
коромысел (положения коромысел я вычислял по вершинам, так что сам
редактор мало отличается от редактора ломаной)

Что такое "пути" и зачем это нужно, я не очень понимаю..
(Наверно для поддержки линейно-узловой топологии?)
Но, имеющаяся технология написания редакторов
довольно легко позволяет писать редакторы любой сложности, с высокой
долей повторного использования кода..
В часности, насколько я понимаю уту задачу — тут граф, соединённый различными
модификациями polyline (с точки зрения редактора ессно)

K>так же буду делать трех мерку, всего этого хозяйства, а там алгоритмы куда сложнее
Делали нечто подобное
(http://ugp.udm.ru/ru/struct/1/06/geoart/index.shtml)
В том числе была и модель рельефа с триангуляцией, но наши "манахеры" рынка сбыта толком
не нашли, поэтому эта часть в "неопробованном" толком пользавателями виде..

Вообще, если интересно, наверно лучше писать дальше в приват (vva@udm.ru)

Здравствуйте, mihoshi, Вы писали:

M>Здравствуйте, vvaizh, Вы писали:

V>>Потом растр убирают, показывают результат заказчику, а он говорит:
V>>неееее... у домов то прямуе углы, а у вас какие то кривые..

V>>Вопрос:

V>>Как можно быстро исправить ситуацию (все домики уже есть,
V>>нужно только их подкорректировать)?

M>Я бы сделал так.

M>1. Оцениваем погрешность тыкания.
M>2. Рассматриваем множество отрезков, составляющих контур. Сортируем их по углу, взятому по модулю 90 градусов (осторожно с граничными случаями).
M>3. Если соседние в отсортированном списке отрезки отличаются в пределах погрешности, то их угол считаем одинаковым (берем среднее). Получаем некоторое небольшое кол-во направлений. Если дом имеет только прямоугольные углы, то направление пости наверняка будет одно.

Браво, начало правильное!

M>4. Для каждого направления в порядке убывания частоты и для каждой точки рассматриваем точки, лежащие на линии (в пределах погрешности), проведенные через нее в этом направлении (и в +90 градусов). Подравниваем эти точки.
M>5. Если точку уже подравняли, то дальнейшее подравнивание не должно уводить ее с этого направления. Соответственно, после двух подравниваний точку уже не трогают.

Вот конец какой то неконкретный..
Это же "этюд"..
Тут никаких "подравниваний", только простые, "бесспорные" формулы..

В конце недели ответ дам..

M>6. При желании можно учитывать направления соседних домов чтобы они вкривь не стояли.
M>Вот, достаточно универсально и относительно несложно в реализации.
M>Алгоритм можно использовать как для отдельных домов, так и для их множества разом.

Да, такое поможет, проще даже в качестве направления брать красные линии

Здравствуйте, vvaizh, Вы писали:


M>>4. Для каждого направления в порядке убывания частоты и для каждой точки рассматриваем точки, лежащие на линии (в пределах погрешности), проведенные через нее в этом направлении (и в +90 градусов). Подравниваем эти точки.
M>>5. Если точку уже подравняли, то дальнейшее подравнивание не должно уводить ее с этого направления. Соответственно, после двух подравниваний точку уже не трогают.

V>Вот конец какой то неконкретный..
V>Это же "этюд"..
V>Тут никаких "подравниваний", только простые, "бесспорные" формулы..

Если необходимо точное описание...
4.1 Если точка еще не связана другим направлением, то проецируем ее на линию "подравнивания".

4.2 Если связана, то перемещаем ее на пересечение линии "подравнивания" и связывающего направления. Если это приводит к перемещению точки больше, чем на величину погрешности, то используем 4.1

4.3 При всех операциях при определении порядка выполнении действий точки и направления того же дома имеют приоритет над точками и направлениям других домов. Более используемые направления над менее используемыми. И, возможно, более длинные отрезки над более короткими.

V>В конце недели ответ дам..

M>>6. При желании можно учитывать направления соседних домов чтобы они вкривь не стояли.
M>>Вот, достаточно универсально и относительно несложно в реализации.
M>>Алгоритм можно использовать как для отдельных домов, так и для их множества разом.

V>Да, такое поможет, проще даже в качестве направления брать красные линии

Что есть красные линии?

Здравствуйте, mihoshi, Вы писали:

M>Здравствуйте, vvaizh, Вы писали:

M>
M>>>4. Для каждого направления в порядке убывания частоты и для каждой точки рассматриваем точки, лежащие на линии (в пределах погрешности), проведенные через нее в этом направлении (и в +90 градусов). Подравниваем эти точки.
M>>>5. Если точку уже подравняли, то дальнейшее подравнивание не должно уводить ее с этого направления. Соответственно, после двух подравниваний точку уже не трогают.

V>>Вот конец какой то неконкретный..
V>>Это же "этюд"..
V>>Тут никаких "подравниваний", только простые, "бесспорные" формулы..

M>Если необходимо точное описание...
M>4.1 Если точка еще не связана другим направлением, то проецируем ее на линию "подравнивания".

M>4.2 Если связана, то перемещаем ее на пересечение линии "подравнивания" и связывающего направления. Если это приводит к перемещению точки больше, чем на величину погрешности, то используем 4.1

M>4.3 При всех операциях при определении порядка выполнении действий точки и направления того же дома имеют приоритет над точками и направлениям других домов. Более используемые направления над менее используемыми. И, возможно, более длинные отрезки над более короткими.

V>>В конце недели ответ дам..

M>>>6. При желании можно учитывать направления соседних домов чтобы они вкривь не стояли.
M>>>Вот, достаточно универсально и относительно несложно в реализации.
M>>>Алгоритм можно использовать как для отдельных домов, так и для их множества разом.

V>>Да, такое поможет, проще даже в качестве направления брать красные линии

M>Что есть красные линии?

Проще говоря проектные границы кварталов (границы между тем что называется
"улица/дорога", и "застройка"), как правило дома выстроены строго вдоль них
Но это к делу не отностися (как выбрать "каноническое" направление, уже вроде понятно..)

Здравствуйте, vvaizh, Вы писали:

Короче предполагаемое мной решение:

Отбрасываем случай с нечётным количеством вершин.

Собираем все векторы через соседние точки,
каждый второй из них поворачиваем на 90 градусов,
Нормируем их все и направляем в одну сторону
(чтобы угол между ними был меньше 90 шоадусов некоторые из них придётся повернуть)
Действительно получаем некоторое множество "направлений" (углов от оси скажем x)
Проверяем, что погрешность направлений не превышает какой то погрешности
(хоть 45 градусов, это в принципе не важно)
Находим среднее арифметическое от всех углов (каноническое направление)..


Теперь (то до чего здесь не догадались):

Поворачиваем весь контур на найдённный "усреднённый" угол..

В таком состоянии у любых двух вершин однгого отрезка должна совпадать
одна из координат (по очереди, x и y)

Дык вот, проще всего взять опять же среднеарифметическое..

Поворачиваем контур назад..

Т.е. алгоритм вообще не итеративный, и с погрешностями не работает..
(формально только отбрасываются совсем уж "кривые контуры..")

В общем, не знаю как вам, а мне погравилось именно это решение

Здравствуйте, vvaizh, Вы писали:

V>Короче предполагаемое мной решение:

V>Отбрасываем случай с нечётным количеством вершин.

...

V>В общем, не знаю как вам, а мне погравилось именно это решение

Я искал решение для более общего случая. Кроме того, твое решение может привести к непараллеьлности соседних домов.

Здравствуйте, mihoshi, Вы писали:

M>Здравствуйте, vvaizh, Вы писали:

V>>Короче предполагаемое мной решение:

V>>Отбрасываем случай с нечётным количеством вершин.

M>...

V>>В общем, не знаю как вам, а мне погравилось именно это решение

M>Я искал решение для более общего случая. Кроме того, твое решение может привести к непараллеьлности соседних домов.

1. Для случая "группа парралельных домов" меняется только нахождение канонической
системы координат, общей для всех домов..
2. В условиях __своей__задачи__ я ничего про параллельность домов не говорил.. (сорри)
3. С парралельностью ещё веселей..

У нас эта тётенька не стала поначалу обводить каждый "деревянный" пятистенок..
форма/размеры у них примерно одинаковая, поэтому она просто накопировала их..
чтобы примерно на местах стояли

— т.е. они даже улицам не параллельны были.. поэтому для них проще искать
ближайшую улицу, и поворачивать на неё, а ещё лучше спец команду написать
"дома по линейке становись", чтобы тётенька эту линейку руками ввела

Здравствуйте, vvaizh, Вы писали:

V> У нас эта тётенька не стала поначалу обводить каждый "деревянный" пятистенок..
V> форма/размеры у них примерно одинаковая, поэтому она просто накопировала их..
V> чтобы примерно на местах стояли

V> — т.е. они даже улицам не параллельны были.. поэтому для них проще искать
V> ближайшую улицу, и поворачивать на неё, а ещё лучше спец команду написать
V> "дома по линейке становись", чтобы тётенька эту линейку руками ввела
V>

Да, тетеньки это тетеньки. Я недаром их тетеньками назвали.