Алгоритм поиска крайних точек среди множества #676660

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

бинарный поиск

в трехмерном пространстве?

вот работающий пример на

+ на javascript

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

Не совсем в теме, но разве нельзя, для данной задачи, точки с трехмерными координатами представить в виде проекций на 3 плоскости?

Насколько я понимаю, при стандартной развертке, прямые на плоскости превратятся в кривые на сфере и наоборот.

Сомнения понял.

задача автора это часть алгоритма

вот еще ссылки

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

кто-то использовал пакет R хочу его приспособить для задачи

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

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

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

Это все варианты алгоритма Джарвиса. По сути одно и тоже.

сказали, что там есть. В алгоритме предполагается что фигура выпуклая, а у меня может быть любая. Аналогия с проведением точек в конверте (центральная точка). Задачу я сформулировал не корректно. Мне надо "обтянуть" точки, а не просто выделить крайние. Т.е может получиться и "сосиска" и "полумесяц" и т.д.

если проводить фигуру по крайним точкам то НЕ может получиться полумесяц

левый или правый вариант?

левый

а если усложнить ? )))

Сформулируй задачу корректно - и люди к тебе потянутся. (Но тебе это будет уже не нужно - поскольку при правильной формулировке решение будет сразу видно).

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

что-то мне подсказывает: данная задача гарантировано лежив в алгоритме из

а почему не ?

Август... Опытные телепяты - лечатся от жары на пляжах Египта. и уже кучу алгоритмов предложили. Но, видать, телепатией они не страдают.

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

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

тут есть маленькая загвостка... если у нас 10 000 точек сколько будет отрезков "Построй отрезки между всеми точками" ??? а если точек будет лям :) я реализовывал в 1с триангуляцию на подобных массивах точек :)

Тут есть большая загвоздка - а что именно хочет ТС? Насчёт "маленькой загвоздки" - это да. Поэтому на тебя и ссылаюсь. Но пусть сначала хоть какое-то решение найдёт. При малых n. И убедится, что это - то, что ему надо. А то будет искать эффективный алгоритм не для того. ведь не зря примерчики подкидывал.

попробую в начале и хоть посмотрю, что получиться

Получишь правый вариант из .

вот еще прикольный алгоритм, пригодный например для минимальной топологиии сети

мдя..судя по рисунку меньше играть в танки надо. Почему внутренние точки сверху удостоились войти в крайние, а внизу нет. Это типа гравитация сверху вниз и нить провисла?))

Построение выпуклой оболочки обходом Грэхэма Даны N точек на плоскости. Построить их выпуклую оболочку, т.е. наименьший выпуклый многоугольник, содержащий все эти точки. Мы рассмотрим метод Грэхэма (Graham) (предложен в 1972 г.) с улучшениями Эндрю (Andrew) (1979 г.). С его помощью можно построить выпуклую оболочку за время O (N log N) с использованием только операций сравнения, сложения и умножения. Алгоритм является асимптотически оптимальным (доказано, что не существует алгоритма с лучшей асимптотикой), хотя в некоторых задачах он неприемлем (в случае параллельной обработки или при online-обработке).

в 90х я использовал поиск по наименьшему углу, не знаю есть такие алгоритмы так сказать академически, но тогда сам придумал и само работало, на XT контур из 10 000 точек строило около минуты, работало :)

Наименьший угол - это сложность O(n^2), что неприемлемо на практике.

не совсем, там для каждой точки есть 4 четверти, и в зависимости от ее расположение анализировать нужно максимум 1/2 а идеале 1/4 углов

это наихудший вариант

? О(1/4*n*n)=O(n*n), по определению. Всегда O(n^2)

А если решать задачу последовательно: 1) Берём три точки - получаем треугольник. 2) Последовательно добавляем точки - если точка оказывается внутри фигуры-многогранника, то она внутренняя, если она выходит за какую-то грань, то добавляется два отрезка, если за несколько граней, то происходит спрямление, то есть выкидываются точки, ставшие внутренними.

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

Так я и не претендую на лучший. Для реализации достаточно, чтобы алгоритм был понятный. P.S. если переходить к тетраэдрам и плоскостям, то можно и в объёме также действовать.

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

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

Читай и смотри . Там ясно написано, что он хочет не обязательно выпуклую оболочку ) А критериев не приводится. Сдается мне что ему придется копать в сторону разделов кластерного анализа, а именно построения оболочек кластера (cluster hull)

Если он сам не знает чего хочет - никто помочь не сможет.

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

сделал по принципу черного ящика. Использовал пакет R. Вот сценарий для выполнения: X<-read.table("//1c/Coordinates/InPutCoord.txt", dec=",", sep = " ") #X<-read.table("D:/R/InPutCoord.txt", dec=",", sep = " ") as.matrix(X) chull(as.matrix(X)) Y<-chull(as.matrix(X)) write(Y, "//1c/Coordinates/ExtremeCoord.txt", 1)

почему Chull?

потому, что сказали использовать chull . Вот так. Что еще можно использовать?