Найти дырки

[Igors]

Добрый день

Есть массив/контейнер точек образующий сложный замкнутый контур (аттач). Некоторые отрезки могут совпадать.
Задача: удалить совпадающие отрезки и разбить исходный контур на N новых

- первый новый = внешний (вмещающий)
- остальные = "дырки"

Результат выдать в виде массивов индексов. Напр дырок нет, значит на выходе один std::vector <int> со значениями 0..N-1 (где N -число точек). Есть дырка - значит какие-то индексы перенесены во второй вектор и.т.д

Мысли?

Спасибо

[V1KT0P]

Если я правильно понял то по точкам строится контур, где линии могут пересекаться?
Тогда самый банальный, это разбить контур на линии, там где линии налаживаются или пересекаются разбивать эти линии на новый. Получится избыток линий в которых простым сравнением начала и конца координат можно отсеять дублирующие. Затем найти точки из которых идут только два луча под углом в 180 градусов, в результате будет убран избыток линий. Что-то типа такого?

[Igors]

Привет, Витя, давно Вас не было видно

Уточним. Каждый отрезок получается при соединении последующей точки с предыдущей. Гарантируется что контур замкнут - последняя соединена с первой. Поэтому

1) Рассматривается только случай совпадения 2 отрезков - ну это тоже можно считать пересечением. Никакого "физического" удаления нет, если контур дырки выделен, такие отрезки сами и отпадут.

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

[_OLEGator_]

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

UPD
Не, такой алгоритм не катит.

[V1KT0P]

Привет, Витя, давно Вас не было видно

Да пока был безработным ездил по Украине =).

Ты лучше уточни что тебе надо. Дай хотя-бы два маленьких примера как было до и как должно быть после. А то я тебя наверно неправильно понял.

[Igors]

Внешний контур найти достаточно просто.

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

Ты лучше уточни что тебе надо. Дай хотя-бы два маленьких примера как было до и как должно быть после. А то я тебя наверно неправильно понял.

А что неясно-то? Что один массив (индексов) надо разбить на несколько? Что такое совпадающие отрезки? Ну вот в аттаче "что нужно получить" - каждый массив нарисован своим цветом

[V1KT0P]

Внешний контур найти достаточно просто.

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

Ты лучше уточни что тебе надо. Дай хотя-бы два маленьких примера как было до и как должно быть после. А то я тебя наверно неправильно понял.

А что неясно-то? Что один массив (индексов) надо разбить на несколько? Что такое совпадающие отрезки? Ну вот в аттаче "что нужно получить" - каждый массив нарисован своим цветом

Вот теперь наконец-то стало ясно =).
1) Находим внешний контур и переносим эти точки в новый массив.
2) Берем самую левую верхнюю точку и если взять направление вправо то постоянно выбирать направление вправо. Как только достигнута точка с которой начали, то все эти точки переносим в новый массив.
3) Проверяем есть ли еще точки, если есть то п.2.

[Igors]

Вот теперь наконец-то стало ясно =).
1) Находим внешний контур и переносим эти точки в новый массив.
2) Берем самую левую верхнюю точку и если взять направление вправо то постоянно выбирать направление вправо. Как только достигнута точка с которой начали, то все эти точки переносим в новый массив.
3) Проверяем есть ли еще точки, если есть то п.2.

Как уже сказано выше найти внешний контур - геморрой порядочный. А главное 2. 3 работать не будут т.к. предложены "глядя на разноцветные контуры" - но ведь это уже результат. А посмотрите на исходную картинку - там есть "перепонка" соединяющая "синюю" и "черную" комнаты. Она останется после выделения внешнего контура.

К слову: одна точка самая левая, другая самая верхняя - какая же из них "самую левая верхняя"? 

[Fat-Zer]

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

[Igors]

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

Установлено правило/соглашение - каждая точка соединена с последующей и предыдущей (как они следуют в массиве), последняя соединена с первой. Поэтому точки задают и отрезки.

Почему "самая внешняя-левая"? Мне кажется что и "самая правая (нижняя, верхняя)" также принадлежат внешнему контуру 

Ну и хотелось бы что-то поконкретнее вместо многочисленных многоточий...   

[Fat-Zer]

Установлено правило/соглашение - каждая точка соединена с последующей и предыдущей (как они следуют в массиве), последняя соединена с первой. Поэтому точки задают и отрезки.

понял... рисунок нарисован «не отрывая пера»

Почему "самая внешняя-левая"? Мне кажется что и "самая правая (нижняя, верхняя)" также принадлежат внешнему контуру 

нуда... я к тому, что выбрать первую точку не проблема...

Ну и хотелось бы что-то поконкретнее вместо многочисленных многоточий...   

у меня уже половина седьмого на часах и внятно записать свои мысли уже не получается...
в общем тоже самое, что писал V1KT0P...
внешний контур находится точно также, пунктами 2-3: представь что из угла идёшь по линии (по часовой стрелке для определённости)... встретил развилку и выбрал поворот налево... так ты гарантированно пройдёшь по контуру, а не по перемычкам, автоматом обоходя их...
самая левая-верхняя или верхняя-левая - не важно... главное, чтобы она была на краю [и может быть чтобы это был угол]

[V1KT0P]

Вот теперь наконец-то стало ясно =).
1) Находим внешний контур и переносим эти точки в новый массив.
2) Берем самую левую верхнюю точку и если взять направление вправо то постоянно выбирать направление вправо. Как только достигнута точка с которой начали, то все эти точки переносим в новый массив.
3) Проверяем есть ли еще точки, если есть то п.2.

Как уже сказано выше найти внешний контур - геморрой порядочный. А главное 2. 3 работать не будут т.к. предложены "глядя на разноцветные контуры" - но ведь это уже результат. А посмотрите на исходную картинку - там есть "перепонка" соединяющая "синюю" и "черную" комнаты. Она останется после выделения внешнего контура.

К слову: одна точка самая левая, другая самая верхняя - какая же из них "самую левая верхняя"? 

Обход как внешнего так и внутренних контуров делается по одному и тому-же алгоритму, с той ли разницей что направление для контура выбирается влево, а для комнат вправо. Это если берем самую верхнюю левую точку.
Вот по подробней:
1) Сперва находим самые левые верхнии точки, далее выбираем самую левую из них. Теперь если строго вправо 0 градусов и градусы по часовой.
2) Эта первоначальная точка имеет вектор 0, теперь из нее смотрим какие есть направления к другим точкам. Для каждого считаем вектор, поворачиваем векторы так чтоб для текущей точки он был 180 и градус между текучим вектором и возможными путями. Для контура нас интересует наименьший градус.
3) Повторяем п.2 пока не дойдем до первоначальной точки. После этого все точки что мы обошли изымаем из общего массива. В итоге те перепонки что соединяли комнаты с контуром исчезнут ибо этих точек в общем массиве нету. Остались только перепонки между комнатами.
4) Снова берем самые верхнии точки, снова самую левую из них. И для каждого действия повторяем п.2-3 с той лишь разницей что направление выбираем угол которого между векторами текущим и следующим был самый большой.
5) В итоге начальный массив опустеет, и мы будем иметь кучу новых среди которых отдельно контур и отдельно каждая комната.

Тут еще надо подумать над тем не ошибся ли я с градусами при выборе направления, ибо щас думать над этим времени нет, но думаю что должно быть правильно.

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

[Igors]

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

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

Тут еще надо подумать над тем не ошибся ли я с градусами при выборе направления, ибо щас думать над этим времени нет, но думаю что должно быть правильно.

Ответ тот же что и выше, плюс понравилась идея "опустеет" - логично вообще не возиться с внешним а считать его "остатком"

А что если один раз найти все "перемычки" и запомнить их в контейнере? Как дальше раскрутить? И как найти? (надеюсь я в приличном обществе, и линейный перебор предлагаться не будет  )

[V1KT0P]

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

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

Тут еще надо подумать над тем не ошибся ли я с градусами при выборе направления, ибо щас думать над этим времени нет, но думаю что должно быть правильно.

Ответ тот же что и выше, плюс понравилась идея "опустеет" - логично вообще не возиться с внешним а считать его "остатком"

А что если один раз найти все "перемычки" и запомнить их в контейнере? Как дальше раскрутить? И как найти? (надеюсь я в приличном обществе, и линейный перебор предлагаться не будет  )

Да все там не так уж и сложно. В реале я бы тебе быстро на бумаге объяснил. Если тебе надо попроще то вот три варианта, но уже с ограничениями к входным данным:
1) Убираем перепонки между комнатами и контуром. В итоге в массиве будут раздельно связанные точки. Для этого надо чтоб перепонка гарантированно была не больше N, а стороны комнаты или контура гарантированно больше N. Проходим все линии и там где длина меньше N удаляем.
2) Так как глядя на картинку видно что п.1 не подходит, то чуть усложняем. Теперь сторона комнаты может быть больше N. Также проходим и все линии меньше N удаляем, при условии что обе точки имеют три связи.
3) Как по мне так самый простой, правда что-то не сразу пришел в голову =). Перебираем по очереди все линии, если у линии обе точки имеют три связи то удаляем ее. В итоге и контур и комнаты не будут связанны.

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

[Igors]

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

Видать на новой работе особо лазить в инете не разрешают, поэтому у Вити активность к вечеру 

Ну а что такое "удалить линии"? Формально никаких линий/отрезков нет, на входе есть точки. "Перепонка" выглядит так

точка 10 (например) совпадает с  точкой 20
точка 11 совпадает с  точкой 19

Ну эти совпадения еще надо найти. И что мы собрались удалять?

Просьба: цитированием не злоупотребляйте, и так понятно о чем речь