Нахождение точки удовл. правилу Делоне
 

Дано: массив точек представленых в виде пары координат Х и Y на плоскости. И отрезок соединяющий 2е из точек массива образуя начальное ребро.

Найти такую точку массива чтобы она удовлетворяла следущему правилу:
Окружность описаная вокруг трёх точек(2х точек ребра и искомой) должна быть минимально возможного радиуса из всех возможных вариантов в это массиве.

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

Оценка производительности: O(N-2) в худшем случае и O((N-2)/2) в среднем.

Вопрос как бы это дело ускорить...непребигая к полному перебору...

Возможно есть способы предварительной сортировки...

Re: Нахождение точки удовл. правилу Делоне
 

SBJoker, хм разумееться есть. Неуверен, но нужно найти такую простенькую формулку, которая находит золотую середину между близости к перпендикуляром и расстоянием (она ведь меньше будет требовать). Либо простой алгоритм, чем больше разница между длинами A-C и B-C (A и B соеденены). Вот, и отпровляя ввыделенный список сразу. Далее если следующий найденный по вычислениям, к примеру разница меж двух длин больше, то ставить за, если меньше, то смещать все эллементы на 1 вправо начиная с промежутка куда вставляем новый. Конечно имхо может быть ещё хуже :)

Re: Нахождение точки удовл. правилу Делоне
 

имхо юзай деревья :)

Re: Нахождение точки удовл. правилу Делоне
 

Это ясно что деревья... Но как определить какая точка больше? И чтобы создать список всёравно нужно сделать полный перебор всех точек... и дерево будет правильно тока по отношению к текущему отрезку а для других его строить поновой..так что тут дерево ничего недаёт..

Или я что-то недогоняю?

Re: Нахождение точки удовл. правилу Делоне
 

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

суть в том что в 50% случаем мы найдем ету точку в заданых ветках
aka другими словами - таким способом достигается
простая сортировка по дистанции, самые далекие точки
будут проверятся последними

я вот не помню можно ли через любые 3 точки провести круг
если да - то алгоритм снижается до O(log(N))
но само создание дерева занимает O(N log^2(N))

почитать можеж тут http://en.wikipedia.org/wiki/Kd-tree
http://en.wikipedia.org/wiki/Octree

ps. из-за не знания - минимальный радиус будет с ближайшей точкой ?
или с какой вообще ... :/

Re: Нахождение точки удовл. правилу Делоне
 

Для 3х точек минимальный радиус это пол растояния между самыми далёкими точками... справедливо для равнобедреных и правильных треугольников..
спасибо буду думать... курил винарные деревья но они неподходят..а квадродерево рулит тут.

Re: Нахождение точки удовл. правилу Делоне
 

Вот нашел файлик с описаниями кучи алгоритмов триангуляции по Делоне http://srcc.msu.su/num-meth/zhurnal/...02/art1_2.html

Re: Нахождение точки удовл. правилу Делоне
 

да курил эту книжецу... много там всего..спсб

Re: Нахождение точки удовл. правилу Делоне
 

А про што речь, это я так пологаю для оптимезации?