LINUX.ORG.RU

Сортировка точек

 ,


0

1

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

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

Может быть кто подскажет, как их отсортировать?

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

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

geekless ★★ ()
Последнее исправление: geekless (всего исправлений: 2)
Ответ на: комментарий от geekless

Ближайшая точка - необязательно следующая. ТС'у надо отсортировать точки в том порядке, в котором они образуют контур фигуры.

Dragon59 ★★ ()

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

Harald ★★★★★ ()
Ответ на: комментарий от Harald

Лол, поняша же, уже привёл ссылку на нормальный вариант.

anonymous ()
Ответ на: комментарий от geekless

Алгоритмы по твоей ссылке решают другую задачу.

А нужно их отсортировать в той последовательности, в какой они очерчивают замкнутую область (по периметру)

Dragon59 ★★ ()
Ответ на: комментарий от Dragon59

Ближайшая точка - необязательно следующая.

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

geekless ★★ ()
Ответ на: комментарий от Dragon59

Чем читаешь?

«Все множество точек принадлежит граням геометрической фигуры.»

А в твоей задаче точкам допустимо лежать внутри.

geekless ★★ ()
Ответ на: комментарий от geekless

А в твоей задаче точкам допустимо лежать внутри

это общий случай,ИМХО не противоречащий

Все множество точек принадлежит граням геометрической фигуры.

Harald ★★★★★ ()

Это по сути нахождение выпуклой оболочки же. В Алгоритмах Кормена есть этот алгоритм.
Хотя насчёт случая неправильной формы вроде не то.

aptyp ★★★★ ()
Ответ на: комментарий от geekless

Там надо из первого алгоритма вырезать срезание углов и всё.

anonymous ()

Может быть кто подскажет, как их отсортировать?

Разве сортировка по полярному углу не то, что тебе нужно?
1) Взять любую крайнюю точку O (например, самую нижнюю, а если таких несколько, то самую левую)
2) Сортировать остальные точки по возрастанию полярного угла: то бишь, точка P1 меньше P2, если поворот от OP1 до OP2 против (или по — главное, чтоб всегда в одну сторону) часовой стрелки.

metar ★★★ ()
Последнее исправление: metar (всего исправлений: 1)
Ответ на: комментарий от geekless

«Все множество точек принадлежит граням геометрической фигуры.»

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

rimsleur ()
Ответ на: комментарий от rimsleur

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

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

Dragon59 ★★ ()
Ответ на: комментарий от anonymous

Это так ты хочешь мне сказать, что невнимательно читал пост?

metar ★★★ ()
Ответ на: комментарий от anonymous

а где там по ссылке словесное описание алгоритма?

Harald ★★★★★ ()
Ответ на: комментарий от roof

М-м-м, да, действительно с невыпуклыми это неправильно, даже если в качестве O угадать точку внутри фигуры.

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

metar ★★★ ()
Последнее исправление: metar (всего исправлений: 1)
Ответ на: комментарий от Harald

Это был пример, опровергающий решение geekless.

anonymous ()
Ответ на: комментарий от metar

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

roof ★★ ()

Вычисляешь центр тяжести фигуры. Принимаешь его за начало отсчета. Координаты всех точек переводишь в полярную систему. Сортируешь по углу.

Если фигура самопересекающаяся, придется выдумывать что-нибудь еще

Eddy_Em ☆☆☆☆☆ ()
Последнее исправление: Eddy_Em (всего исправлений: 1)
Ответ на: комментарий от roof

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

Вычисляешь центр тяжести фигуры. Принимаешь его за начало отсчета. Координаты всех точек переводишь в полярную систему. Сортируешь по углу.

Аналогично, можно проебать точку, если правльно понял.

anonymous ()
Ответ на: комментарий от Eddy_Em

Так мы про фигуру вроде ничего не знаем по условию. Только массив с точками есть и все. Как же ж нам центр тяжести вычислить? Знали бы мы фигуру, мы б просто ребра по порядку перебрали, находя все точки, им принадлежащие.

roof ★★ ()
Ответ на: комментарий от roof

Как же ж нам центр тяжести вычислить?

\frac{1}{N}\sum_{i=1}{N} (\vec\i\cdot x_i + \vec\j\cdot y_i)

Знали бы мы фигуру, мы б просто ребра по порядку перебрали, находя все точки, им принадлежащие.

Можно что-нибудь придумать. От конкретной задачи зависит

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от roof

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

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

metar ★★★ ()
Ответ на: комментарий от metar

Пусть программа выдаёт множество решений.

anonymous ()
Ответ на: комментарий от metar

Если расстояние между точками достаточно мало по сравнению с характерными размерами фигуры, можно вычленить связи (правда, долго придется перебирать) между соседними точками. Если каждая точка имеет лишь двух соседей, фигура не является самопересекающейся — сортировка по φ элементарно решает задачу. Если же есть точки с бóльшим числом связей, нужно будет разбить фигуру на более простые, а потом уже сортировать.

Еще я про Вороного вспомнил и связанного с ним де Лоне.

Eddy_Em ☆☆☆☆☆ ()
Последнее исправление: Eddy_Em (всего исправлений: 1)
Ответ на: комментарий от Eddy_Em

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

Сортировка по полярному углу не работает для невыпуклых фигур без самопересечений. Пример (вообрази хвост достаточно длинным).

metar ★★★ ()
Ответ на: комментарий от metar

Строим диаграмму Вороного, выделяем соседей, сортируем

Eddy_Em ☆☆☆☆☆ ()

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

anonymous ()
Ответ на: комментарий от metar

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

Граней как таковых нет. Точки описывают замкнутую кривую. Кривая может быть плавной.

rimsleur ()
Ответ на: комментарий от Dragon59

Тут будут сложности если фигура самопересекающаяся.

rimsleur ()

Поправка. Самопересечений не будет, но фигура может быть невыпуклой. Тогда сортировка по углу может не сработать.

rimsleur ()
Ответ на: комментарий от rimsleur

Так у тебя фигура не задана. Множество точек не задают фигуру и любая замкнутая ломанная, проходящая через каждую точку один раз и неперекающая саму себя будет периметром.

anonymous ()
Ответ на: комментарий от anonymous

Поправка. Самопересечений не будет, но фигура может быть невыпуклой. Тогда сортировка по углу может не сработать.

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

anonymous ()

Фигура выпуклая или впуклая?

J ★★★★ ()
Ответ на: комментарий от anonymous

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

rimsleur ()
Ответ на: комментарий от rimsleur

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

Sphinx ★★☆☆ ()

А изначально известно, какая это должна фигура? Или просто нужен произвольный многогранник, без самопересечений, составленный из данного набора точек?

buddhist ★★★★★ ()
Ответ на: комментарий от rimsleur

А в чем проблема сортировать и по углу, и по радиусу? Здесь, например, я использовал двухступенчатую сортировку для определения принадлежности точек, расположенных на восьми концентрических окружностях, к окружности заданного номера.

В общем случае делаем так: берем отсортированный по углу массив точек, и проходимся по всем точкам, проверяя разницу по радиусу. Если она больше какого-то предела, точка считается «чужой». Однако, здесь может быть «косяк» при определении принадлежности точек двум параллельным линиям на больших R.

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

фигура не является самопересекающейся — сортировка по φ

Опять же, чтобы она работала, внутренность фигуры должна быть не просто односвязной, но и звёздной.

Sphinx ★★☆☆ ()
Ответ на: комментарий от Eddy_Em

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

Sphinx ★★☆☆ ()
Ответ на: комментарий от Sphinx

Для фигур вроде такой

  .....   ....
 .     ...    ...
.                .
 ...           ..
    ...........

достаточно сортировки по углу

Для такой

  .....   ....
 .     ...    ..
.            ..
 .         ..    ...
 ...         ...    .
    .              .
    ...............
сортировка по радиусу поможет

Eddy_Em ☆☆☆☆☆ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.