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 ★★★
()
Ответ на: комментарий от 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 ★
() автор топика

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

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

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

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

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

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

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

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

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

Необязательно выпуклая, скорее наоборот.

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

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

Sphinx ★★☆☆
()

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

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

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

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

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

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

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

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

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

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

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

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

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

Для такой

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

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