Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Найти точки, которые определяют замкнутый контур 
:(
    Опции темы
rudolfninja
Дата 27.8.2017, 22:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 341
Регистрация: 19.2.2013
Где: г. Минск

Репутация: нет
Всего: 6



Ребята, приветствую.
Стоит такая задача: есть массив примитивовов (отрезки, дуги) для каждого из котороых известны начальные и конечные точки (координаты в 2D плосколсти). Нужно определить какие из этих примитивов определяют замкнутый контур. Не все элементы массива образуют замкнутый контур (в массиве есть элементы, которые находтся внутри контура). Так же проблема в том, что элементы в массиве не обязательно идут по порядку (то есть начальная точка следующего элемента не равна предыдущей точки текущего).
Подскажите, пожалуйста, алгоритм по которому можно решить мою задачу.

Спасибо.
PM MAIL Skype   Вверх
Alexeis
Дата 27.8.2017, 23:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Амеба
Group Icon


Профиль
Группа: Админ
Сообщений: 11743
Регистрация: 12.10.2005
Где: Зеленоград

Репутация: нет
Всего: 459



Все элементы входящие в замкнутый контур должны иметь строго по 2е пары, у которых есть по одной общей точке. Думаю что этого условия будет достаточно для решения задачи. Берем любой примитив и ищем к нему 2е пары. Если не нашли берем другой примитив. Если нашли то для найденных пар ищем еще по 1 одной паре с общими вершинами и так пока контур не замкнется. Если не замкнулся значит берем следующий примитив. 


--------------------
Vit вечная память.

Обсуждение действий администрации форума производятся только в этом форуме

гениальность идеи состоит в том, что ее невозможно придумать
PM ICQ Skype   Вверх
Akina
Дата 28.8.2017, 07:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20570
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 453



Цитата(Alexeis @  28.8.2017,  00:22 Найти цитируемый пост)
Все элементы входящие в замкнутый контур должны иметь строго по 2е пары, у которых есть по одной общей точке.

Это с чего бы? Есть условие, что
Цитата(rudolfninja @  27.8.2017,  23:59 Найти цитируемый пост)
в массиве есть элементы, которые находтся внутри контура

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

Цитата(rudolfninja @  27.8.2017,  23:59 Найти цитируемый пост)
Стоит такая задача:

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


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
rudolfninja
Дата 28.8.2017, 09:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 341
Регистрация: 19.2.2013
Где: г. Минск

Репутация: нет
Всего: 6



Цитата(Akina @  28.8.2017,  07:47 Найти цитируемый пост)
но нет указания, что они там находятся полностью

Все примитивы, которые находятся внутри контура, полностью находятся там, т.е. за пределы контура не выходят.

Цитата(Akina @  28.8.2017,  07:47 Найти цитируемый пост)
возможно же, что один из концов примитива является вершиной контура, а сам он лежит внутри контура.

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

PM MAIL Skype   Вверх
rudolfninja
Дата 28.8.2017, 10:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 341
Регистрация: 19.2.2013
Где: г. Минск

Репутация: нет
Всего: 6



Я вот еще подумал, что может быть ситуация, когда есть замкнутый контур внутри замкнутого контура...это усложняет работу алгоритма.
PM MAIL Skype   Вверх
Akina
Дата 28.8.2017, 10:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20570
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 453



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

Это сообщение отредактировал(а) Akina - 28.8.2017, 10:36


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
rudolfninja
Дата 29.8.2017, 09:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 341
Регистрация: 19.2.2013
Где: г. Минск

Репутация: нет
Всего: 6



Цитата(Akina @  28.8.2017,  10:34 Найти цитируемый пост)
С учётом всего озвученного могу сформулировать следующее - имеется ненаправленный граф, содержащий один или более непересекающихся циклов, причём ни одна вершина не принадлежит более чем двум рёбрам.

По сути да, так и есть.

Цитата(Akina @  28.8.2017,  10:34 Найти цитируемый пост)
красим в тот же цвет прилежащие к ней вершины

Что имеется в виду под "прилежащими вершинами"? Те вершины, которые соединены с текущей ребром?

Вроде, ваш алгоритм понятен. Буду пробовать реализовать.
Спасибо.
PM MAIL Skype   Вверх
Akina
Дата 29.8.2017, 11:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20570
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 453



Цитата(rudolfninja @  29.8.2017,  10:40 Найти цитируемый пост)
Что имеется в виду под "прилежащими вершинами"? Те вершины, которые соединены с текущей ребром?

Именно. 
Цитата(rudolfninja @  29.8.2017,  10:40 Найти цитируемый пост)
Буду пробовать реализовать.

С программной точки зрения посмотрите, что проще красить - вершины или рёбра. Алгоритму-то в общем пофиг.


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
rudolfninja
Дата 30.8.2017, 09:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 341
Регистрация: 19.2.2013
Где: г. Минск

Репутация: нет
Всего: 6



Ну вроде как получилось определить замкнутые контуры.
Теперь вопрос в том, как определить внешний и внутренние контуры?
PM MAIL Skype   Вверх
Akina
Дата 30.8.2017, 10:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20570
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 453



Цитата(rudolfninja @  30.8.2017,  10:33 Найти цитируемый пост)
как определить внешний и внутренние контуры? 

Пфф... Если контур 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


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
rudolfninja
Дата 30.8.2017, 13:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 341
Регистрация: 19.2.2013
Где: г. Минск

Репутация: нет
Всего: 6



Первый вариант мне понравился больше =)
Вот только что значит "в профиле" в этой цитате?

Цитата(Akina @  30.8.2017,  10:11 Найти цитируемый пост)
Имеются в виду истинные, в профиле, минимумы и максимумы, а не среди координат вершин.


PM MAIL Skype   Вверх
Akina
Дата 30.8.2017, 14:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20570
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 453



Цитата(rudolfninja @  30.8.2017,  14:50 Найти цитируемый пост)
что значит "в профиле" в этой цитате?

См. аттач. Размеры по координатам примитивов красной фигуры не равны истинным в профиле. Дуги-с...

Присоединённый файл ( Кол-во скачиваний: 8 )
Присоединённый файл  1.png 5,91 Kb


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
basilcat314
Дата 7.8.2022, 15:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 8
Регистрация: 9.8.2011

Репутация: нет
Всего: нет



Цитата(Akina @ 30.8.2017,  14:52)
Цитата(rudolfninja @  30.8.2017,  14:50 Найти цитируемый пост)
что значит "в профиле" в этой цитате?

См. аттач. Размеры по координатам примитивов красной фигуры не равны истинным в профиле. Дуги-с...

Осталось найти эти 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
PM MAIL   Вверх
basilcat314
Дата 7.8.2022, 18:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 8
Регистрация: 9.8.2011

Репутация: нет
Всего: нет



Цитата(rudolfninja @ 27.8.2017,  22:59)
Ребята, приветствую.
Стоит такая задача: есть массив примитивовов (отрезки, дуги) для каждого из котороых известны начальные и конечные точки (координаты в 2D плосколсти). Нужно определить какие из этих примитивов определяют замкнутый контур. Не все элементы массива образуют замкнутый контур (в массиве есть элементы, которые находтся внутри контура). Так же проблема в том, что элементы в массиве не обязательно идут по порядку (то есть начальная точка следующего элемента не равна предыдущей точки текущего).
Подскажите, пожалуйста, алгоритм по которому можно решить мою задачу.

Спасибо.

Но всё таки я это поборол в своём САПРе.


Присоединённый файл ( Кол-во скачиваний: 3 )
Присоединённый файл  1OK.png 171,60 Kb
PM MAIL   Вверх
basilcat314
Дата 7.8.2022, 18:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 8
Регистрация: 9.8.2011

Репутация: нет
Всего: нет



Цитата(rudolfninja @ 27.8.2017,  22:59)
Ребята, приветствую.
Стоит такая задача: есть массив примитивовов (отрезки, дуги) для каждого из котороых известны начальные и конечные точки (координаты в 2D плосколсти). Нужно определить какие из этих примитивов определяют замкнутый контур. Не все элементы массива образуют замкнутый контур (в массиве есть элементы, которые находтся внутри контура). Так же проблема в том, что элементы в массиве не обязательно идут по порядку (то есть начальная точка следующего элемента не равна предыдущей точки текущего).
Подскажите, пожалуйста, алгоритм по которому можно решить мою задачу.

Спасибо.

Но всё таки я это поборол в своём САПРе.


Присоединённый файл ( Кол-во скачиваний: 0 )
Присоединённый файл  2OK.png 122,90 Kb
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

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


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.1882 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.