Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 [3]      все
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
Извиняюсь за дидактичность:
Хочу ещё пару слов к постановке. Это одинаково относится и к вопросу ТС, и к моей цели.
Сейчас мы немножко в положении. Я перейду на терминологию рисунков.
+
Нам сказали: "Мы превратили полутоновый рисунок в ч/б. Качественно или плохо, это наша проблема.
Мы хотим теперь минимально оконтурить, чтобы вырезать только рисунок, отбросив лишнее. Вот вы нам оконтурьте, по своим соображениям, не зная исходной фигуры, на которую это д.б. похоже, не зная будущих способов использования вырезки, не зная в какой области на самом деле будет применён алгоритм.
А мы ваше качество оценим (наверное глазками), ибо мы знаем, что может быть, и примерно поймём, качественно это сделано или нет."

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

Если меньше лирики:
- модель (пусть даже их 2-3) должна быть обоснованно адекватна предметной области
- какие-то показатели качества д.б. (мы пока не уверены, на что ориентироваться, даже если не существует "рисунка"-оригинала, показатели качества могут исходить из представлений о предполагаемом использовании)
- какие-то формализованные ограничения д.б.
- оценка кол-ва точек (10^2, ^3, ... ^1000 ...)
- серийность задачи (если нужно только одинажды, то может ручками просто? а сказать, что автоматически).
18 окт 19, 13:54    [21997426]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
xMailer
Member

Откуда:
Сообщений: 62
exp98
xMailer
Упорядочить вершины по полярному кругу не получилось.
а) Почему?

центр для определения угла я определил как
xc = sum(x)/count(x)
yc = sum(y)/count(y)
вес для сортировки относительно центра
angle = atan2(cx - x, cy - y)

Такого рода сортировка будет корректно работать если центр xc,yc находится в примерном центре, в случае выгнутости фигуры у меня не заработало.

Отверстий в фигуре в данной задаче не предусматривается
18 окт 19, 15:26    [21997523]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
Навскидку неск. подходов к показателям качества. От них же можно строить ограничения. Либо наоборот.
- числовой (%точек ...)
- площадной (%площади, макс и мин ширина/площадь разных участков)
- линейный (длина, ширина, периметр, их соотношения ...)
- статистический (М, Д, Д2, Д3 ... плотности, %ошибок, любые фантазии, вкл. корреляции чего-либо)
- когнитивный (похоже на ..., включает в себя ..., формируется из ...)
- оптимизационный (мин/макс некой ф-ции)
18 окт 19, 15:28    [21997525]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
xMailer, а зачем сортировка, послед-сть соединения вершин? а полученный граф из оставшихся точек на что?
Если полученное кач-во достаточно, то, определившись наобум с первой точкой, проложить путь на графе до всех соседей (из оставшихся). И так далее, по типу перебора в ширину.
А в глубину придётся "8"-ки специально обрабатывать.

С учётом 8-к сделать и нумерацию по мере прокладки на графе. В принципе она не линейно-кольцевая, а древовидно-кольцевая.

Кста, ещё показатель кач-ва. В мат-ке он называется что-то вроде индекс вектора вдоль участка кривой. Вычисляется как кол-во оборотов (касательной или нормали). + и - друг друга аннулируют. ИМХО, лучше вычислять "плавающий индекс", на нек-ром кол-ве точек, чтобы не прозевать сильно изъгибистые участки.
18 окт 19, 15:54    [21997543]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
xMailer,
правда я до сих пор не понял, как ограничение по радиусу помогает выявить нужные точки. По-моему, если константа, то только мешает. Взять синусоиду, пару периодов. Центр масс у неё в середине. При константе выкинем всё, что близко к центру, и как с ними тогда тогда соединиться?
Возможно, что выявить методом 1-ранговости все, а из них взять только дальние.

На графе от точки к точке двигаться по периметру. И кста, из графа лучше ничего не выкидывать.
18 окт 19, 16:04    [21997553]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
дополню
exp98
выявить методом 1-ранговости все, а из них взять только дальние.
Остальные окучить выпуклой оболочкой. Но это скорее всего не то, что нужно.
18 окт 19, 16:07    [21997556]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
Aklin
Делайте тестовые сценарии, попробую написать, что придумал...
Можно потренироваться на этом рис. На тему выделения движущихся "объектов" У него отрезать нижнюю половину, бинаризовать, а тёмный треугольник под крылом допилить 2-мя способами:
- чтобы появился остров
- чтобы это оказалось полуостровом поизгибистей.
18 окт 19, 16:31    [21997582]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
xMailer,
мне показалось, что вы хотите ограничить снизу толщину фигуры. Например, чтобы не было слишком тонкой талии.
Метода радиус-векторов часто не прокатывает. Приходит мысль измерять толщину в целом кол-ве клеток (dx<x0 OR dy<y0). Но тогда это делается уже постфактум.
Детектировать нетрудно, а вот ... о способе исправления пока глубоко не задумывался.
18 окт 19, 21:12    [21997774]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
exp98
Aklin
Делайте тестовые сценарии, попробую написать, что придумал...
Подожду пример от мэйтона )) Правда у него ожидается односвязная область.

Эй. Что это за тоталиатор? Я ничего космического не обещал.

P.S. Soryan за остуствие. У меня полетел Wifi адаптер и я конфигурил новый. Какой-то китайский Netis.
Зато двухдиапазонный.
18 окт 19, 21:13    [21997775]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
Dima T
Member

Откуда:
Сообщений: 14096
mayton
У меня полетел Wifi адаптер и я конфигурил новый

Ты же взрослый дядька со взрослым компом, протяни уже провод от роутера (перфоратор на прокат можно взять)
18 окт 19, 21:19    [21997781]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Уже пофиксил.
18 окт 19, 21:29    [21997787]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
По ящикам. На картинке есть груз ящиков по форме буквы Е.

Тривиальная упаковка говорит что надо исключить центральный ящик из привязки. Но мы видели
что в первом посту у автора есть сложная привязка которая учитывает экстремальные точки
внутренних ящиков.

Помогите определить включать ли внутренний ящик. И как.

К сообщению приложен файл. Размер - 56Kb
18 окт 19, 21:43    [21997797]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
exp98
Member

Откуда:
Сообщений: 1846
Из тех крох, что нам известны, у меня имхо, что надо бы к 2 вершинкам срединной перекладины притянуть.

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

2)Почему именно прямоуг-ки? хр3 - это вопрос. Автор нарисовал сетку, мэйтон - нет. Для сетки проще строить граф - вся разница. На самом деле для односвязной (пусть и с дырами) оласти у меня уже практически до конца сложилось в голове. Есть варианты,но они зависят от постановки. Поэтому именно к авторской задаче мой интерес уже испаряется. Её я считаю решённой, ну а кодить ... похожее уже кодил макет 5 лет назад, но тогда постановка была достаточная, и автор всерьёз интересовался.

3) Единственное, чего не могу ТСу однозначно рекомендовать - метод игнорирования слишком глубоких впадин. Вопрос фигня, но метод геометрический и итерационный, если делать по науке, сглаживая окрестностями с целью получить серединку хребта. Наверняка уже есть дискретные способы. Скажем, создать матрицу, охватывающую все точки по Х и У. Да и вообще, неплохо провести предварительный разведочный анализ исходной конфигурации заради параметров алгоритма, "эллипсоида рассеяния" фигуры, степени симметричости и пр.

4) Предполагая, что внутри нет дыр, что надо выдерживать достаточную толщину вырезки, что кол-во точек вменяемо и что даже дана сетка, а не фигурки (хотя последнее необязательно), степень извилистости в качестве тоже ограничения не определяется.
Используется сочетание дискретных и геометрических методов.

а) геометрию перевести в граф
б) построить полный контур, какой бы извилистый он не был. Например методом 1-ранговых вершин. Начать можно практически с любой точки (правда потом по мере выбрасывания вершин из пути придётся начало передвигать).
в) аналитически(не знаю уж как) или по мере обхода периметра замерять текущую ширину (тем самым методом (3)) и, если она маленькая удалиьт из пути именно эту вершину, вернуться к предыдущей и соединить её со след-щей. Соединение происходит по некому правилу (непосредственный отрезок или нет).
г) Может получиться, что оставшаяся часть фигуры вся недостаточно широкая, может даже откат к предыдущей вершине не поможет. Это уж как ТС решит.

Ну и да, случай самопересечения "8" надо правильно обрабатывать.

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

Примерно так.


Как ещё вариант фигуры на карте 2-х Америк отрезать северные штаты США от южных, Отрезать всё, в южном полушарии или по Амазонке, убрать острова Кубу, Гаити и т.д (или сделать их полуостровами). Нарисовать сетку. Очень извилистый пример будет.
19 окт 19, 22:04    [21998099]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Афтор. Прокомментируй пожалуйста наши 2 последних сообщения.
20 окт 19, 23:51    [21998558]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
xMailer
Member

Откуда:
Сообщений: 62
Чтобы была законченность в теме решил написать выбранное решение, которое позволило решить мою задачу и для ящиков подойдет (в такой конфигурации как на рисунке).
Мне помог отслеживающий алгоритм "жука". По ссылке, да и в нете в основном его используют для обработки растра, но и в случае прямоугольников он отработал на ура, шаг отслеживания 0.5, кто прочитает про алгоритм поймет почему.
Всем спасибо!
22 окт 19, 22:42    [22000295]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска контура по набору координат  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Тоесть наши вопросы тебя уже не интересуют. Интересный ты собеседник. Ладно иди читай. Зачем тебе тогда
форум - непонятно.
22 окт 19, 23:02    [22000304]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 [3]      все
Все форумы / Программирование Ответить