|
|
|
rudolfninja |
|
|||
Опытный Профиль Группа: Участник Сообщений: 341 Регистрация: 19.2.2013 Где: г. Минск Репутация: нет Всего: 6 |
Ребята, приветствую.
Стоит такая задача: есть массив примитивовов (отрезки, дуги) для каждого из котороых известны начальные и конечные точки (координаты в 2D плосколсти). Нужно определить какие из этих примитивов определяют замкнутый контур. Не все элементы массива образуют замкнутый контур (в массиве есть элементы, которые находтся внутри контура). Так же проблема в том, что элементы в массиве не обязательно идут по порядку (то есть начальная точка следующего элемента не равна предыдущей точки текущего). Подскажите, пожалуйста, алгоритм по которому можно решить мою задачу. Спасибо. |
|||
|
||||
Alexeis |
|
|||
Амеба Профиль Группа: Админ Сообщений: 11743 Регистрация: 12.10.2005 Где: Зеленоград Репутация: нет Всего: 459 |
Все элементы входящие в замкнутый контур должны иметь строго по 2е пары, у которых есть по одной общей точке. Думаю что этого условия будет достаточно для решения задачи. Берем любой примитив и ищем к нему 2е пары. Если не нашли берем другой примитив. Если нашли то для найденных пар ищем еще по 1 одной паре с общими вершинами и так пока контур не замкнется. Если не замкнулся значит берем следующий примитив.
-------------------- Vit вечная память. Обсуждение действий администрации форума производятся только в этом форуме гениальность идеи состоит в том, что ее невозможно придумать |
|||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
Это с чего бы? Есть условие, что но нет указания, что они там находятся полностью. Вот даже не рассматривая гипотетический случай, что примитив пересекает границу (кстати, неизвестно, есть ли вообще пересечения примитивов, гарантированно ли есть замкнутый контур, и если есть, то гарантированно ли он проходит по вершинам примитивов, а заодно - является ли он единственным) - возможно же, что один из концов примитива является вершиной контура, а сам он лежит внутри контура. Вообще-то это модифицированная задача коммивояжёра, в которой не фиксирован начальный узел и отсутствует требование посещения всех вершин графа. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
rudolfninja |
|
|||
Опытный Профиль Группа: Участник Сообщений: 341 Регистрация: 19.2.2013 Где: г. Минск Репутация: нет Всего: 6 |
Все примитивы, которые находятся внутри контура, полностью находятся там, т.е. за пределы контура не выходят.
Я долго думал над этим, и решил, что в тех задачах, которые нужно решить с помощью моего ПО, такой случай вряд ли будет иметь место. |
|||
|
||||
rudolfninja |
|
|||
Опытный Профиль Группа: Участник Сообщений: 341 Регистрация: 19.2.2013 Где: г. Минск Репутация: нет Всего: 6 |
Я вот еще подумал, что может быть ситуация, когда есть замкнутый контур внутри замкнутого контура...это усложняет работу алгоритма.
|
|||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
С учётом всего озвученного могу сформулировать следующее - имеется ненаправленный граф, содержащий один или более непересекающихся циклов, причём ни одна вершина не принадлежит более чем двум рёбрам. Соответственно решение тривиально - берём произвольную вершину и красим её в некоторый цвет, затем красим в тот же цвет прилежащие к ней вершины, и повторяем, пока есть рёбра, одна вершина которых окрашена, а вторая нет. По завершении проверяем все окрашенные в этот цвет рёбра на образование замкнутого контура (или просто в процессе окраски фиксируем факт, что только что окрашенная вершина принадлежит только одному ребру, т.е. контур этого цвета не может быть замкнутым). Затем, если по окончании имеются неокрашенные вершины - красим любую в другой цвет и повторяем окраску, а затем проверку на замкнутость... и так, пока имеется хотя бы одна неокрашенная вершина (и соответственно ребро). По завершении процесса все образовавшие замкнутые контуры проверяются на вложенность (если один вложен в другой - отменяем окраску внутреннего, если ни один не вложен в другой - отменяем окраску обоих). Если останется единственный окрашенный контур - проверяем, что не образующие замкнутого контура окрашенные наборы лежат внутри него, если это так - то этот контур является решением задачи, иначе контур, описывающий все примитивы, отсутствует.
Это сообщение отредактировал(а) Akina - 28.8.2017, 10:36 -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
rudolfninja |
|
|||
Опытный Профиль Группа: Участник Сообщений: 341 Регистрация: 19.2.2013 Где: г. Минск Репутация: нет Всего: 6 |
По сути да, так и есть. Что имеется в виду под "прилежащими вершинами"? Те вершины, которые соединены с текущей ребром? Вроде, ваш алгоритм понятен. Буду пробовать реализовать. Спасибо. |
|||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
Именно. С программной точки зрения посмотрите, что проще красить - вершины или рёбра. Алгоритму-то в общем пофиг. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
rudolfninja |
|
|||
Опытный Профиль Группа: Участник Сообщений: 341 Регистрация: 19.2.2013 Где: г. Минск Репутация: нет Всего: 6 |
Ну вроде как получилось определить замкнутые контуры.
Теперь вопрос в том, как определить внешний и внутренние контуры? |
|||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
Пфф... Если контур 1 находится строго внутри контура 2, то для него истинно любое из условий: MIN(x1)<MIN(x2) MIN(y1)<MIN(y2) MAX(x1)>MAX(x2) MAX(y1)>MAX(y2) Имеются в виду истинные, в профиле, минимумы и максимумы, а не среди координат вершин. Добавлено через 3 минуты и 33 секунды Альтернативный вариант - закрашиваем всю область, ограниченную одним из контуров, и проверяем цвет любой точки другого контура. Если второй внутри первого - она окажется окрашенной, иначе нет. Это сообщение отредактировал(а) Akina - 30.8.2017, 10:13 -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
rudolfninja |
|
|||
Опытный Профиль Группа: Участник Сообщений: 341 Регистрация: 19.2.2013 Где: г. Минск Репутация: нет Всего: 6 |
||||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
См. аттач. Размеры по координатам примитивов красной фигуры не равны истинным в профиле. Дуги-с... Присоединённый файл ( Кол-во скачиваний: 8 ) 1.png 5,91 Kb -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
basilcat314 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 8 Регистрация: 9.8.2011 Репутация: нет Всего: нет |
Осталось найти эти Max(X1), Min(X1) и Max(Y1) и Min(Y1). А потом Max(X2), Min(X2) и Max(Y2) и Min(Y2). А это не так просто как кажется для наружнего контура особенно. Применял вот такой алгоритм для точки ВНУТРИ любого внутреннего контура: // cn_PnPoly(): crossing number test for a point in a polygon // Input: P = a point, // V[] = vertex points of a polygon V[n+1] with V[n]=V[0] // Return: 0 = outside, 1 = inside // This code is patterned after [Franklin, 2000] function cn_PnPoly( P:TPointR;v:array of TPointR; n:integer ):boolean; // íàõîäèòñÿ ëè òî÷êà âíóòðè êîíòóðà var i,cn:integer; vt:double; begin cn := 0; // the crossing number counter // loop through all edges of the polygon for i:=0 to n-1 do begin // edge from V[i] to V[i+1] if (((V[i].y <= P.y) and (V[i+1].y > P.y)) // an upward crossing or ((V[i].y > P.y) and (V[i+1].y <= P.y))) then // a downward crossing begin // compute the actual edge-ray intersect x-coordinate vt := (P.y - V[i].y) / (V[i+1].y - V[i].y); if (P.x < V[i].x + vt * (V[i+1].x - V[i].x))then // P.x < intersect inc(cn); // a valid crossing of y=P.y right of P.x end; end; result:=((cn mod 2)=0); // 0 if even (out), and 1 if odd (in) end; Это сообщение отредактировал(а) basilcat314 - 7.8.2022, 15:11 Присоединённый файл ( Кол-во скачиваний: 4 ) Контура.png 79,99 Kb |
|||
|
||||
basilcat314 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 8 Регистрация: 9.8.2011 Репутация: нет Всего: нет |
Но всё таки я это поборол в своём САПРе. Присоединённый файл ( Кол-во скачиваний: 3 ) 1OK.png 171,60 Kb |
|||
|
||||
basilcat314 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 8 Регистрация: 9.8.2011 Репутация: нет Всего: нет |
Но всё таки я это поборол в своём САПРе. Присоединённый файл ( Кол-во скачиваний: 0 ) 2OK.png 122,90 Kb |
|||
|
||||
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |