Форум программистов [Powered by Invision Power Board]

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

Форум программистов > Алгоритмы > Найти точки, которые определяют замкнутый контур

Автор: rudolfninja 27.8.2017, 22:59

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

Спасибо.

Автор: Alexeis 27.8.2017, 23:22

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

Автор: Akina 28.8.2017, 07:47

Цитата(Alexeis @ 28.8.2017, 00:22

)

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

Это с чего бы? Есть условие, что

Цитата(rudolfninja @ 27.8.2017, 23:59

)

в массиве есть элементы, которые находтся внутри контура

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

Цитата(rudolfninja @ 27.8.2017, 23:59

)

Стоит такая задача:

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

Автор: rudolfninja 28.8.2017, 09:17

Цитата(Akina @ 28.8.2017, 07:47

)

но нет указания, что они там находятся полностью

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

Цитата(Akina @ 28.8.2017, 07:47

)

возможно же, что один из концов примитива является вершиной контура, а сам он лежит внутри контура.

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

Автор: rudolfninja 28.8.2017, 10:05

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

Автор: Akina 28.8.2017, 10:34

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

Автор: rudolfninja 29.8.2017, 09:40

Цитата(Akina @ 28.8.2017, 10:34

)

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

Цитата(Akina @ 28.8.2017, 10:34

)

красим в тот же цвет прилежащие к ней вершины

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

Вроде, ваш алгоритм понятен. Буду пробовать реализовать.
Спасибо.

Автор: Akina 29.8.2017, 11:47

Цитата(rudolfninja @ 29.8.2017, 10:40

)

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

Именно.

Цитата(rudolfninja @ 29.8.2017, 10:40

)

Буду пробовать реализовать.

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

Автор: rudolfninja 30.8.2017, 09:33

Ну вроде как получилось определить замкнутые контуры.
Теперь вопрос в том, как определить внешний и внутренние контуры?

Автор: Akina 30.8.2017, 10:11

Цитата(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 секунды
Альтернативный вариант - закрашиваем всю область, ограниченную одним из контуров, и проверяем цвет любой точки другого контура. Если второй внутри первого - она окажется окрашенной, иначе нет.

Автор: rudolfninja 30.8.2017, 13:50

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

Цитата(Akina @ 30.8.2017, 10:11

)

Имеются в виду истинные, в профиле, минимумы и максимумы, а не среди координат вершин.

Автор: Akina 30.8.2017, 14:52

Цитата(rudolfninja @ 30.8.2017, 14:50

)

что значит "в профиле" в этой цитате?

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

Автор: basilcat314 7.8.2022, 15:08

Цитата(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, 18:09