Алгоритм обхода вершин правильного многоугольника
Версия для печати

Конференция: Конференция iXBT.com (http://forum.ixbt.com/)
Форум: Программирование (http://forum.ixbt.com/?id=26)
URL: http://forum.ixbt.com/topic.cgi?id=26:33544

Время GMT +03. Даты в формате dd.mm.yyyy.


Невидимка, 21.12.2005 21:33
Имеется правильный (выпуклый; все стороны равны, углы тоже) N-угольник на декартовой системе координат.

Нам известен угол в градусах(например, a) и длины сторон(L). Заданы координаты одной из вершины (x,y:вещественный тип), а так же двух соседней с ней вершин (x1,y1 ; x2,y2).

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

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

1. Akina, 21.12.2005 22:34
Перейти в полярную систему координат с центром в центре многоугольника и первой вершиной, лежащей на оси нулевого угла.

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

3. Lamn, 22.12.2005 00:51
1) Вычисляем векторы, соответствующие уже известным сторонам многоугольника: v1=(xv1, yv1)=(x-x1, y-y1) и v2=(xv2,yv2)=(x2-x, y2-y)
2) Вычисляем матрицу поворта, переводящую вектор v1 в вектор v2:
xv2 = c*xv1 + s*yv1
yv2 =-s*xv1 + c*yv1
Имеем:
c = (xv1*xv2 + yv1*yv2)/(xv12+yv12)
s = (xv2*yv1 - xv1*yv2)/(xv12+yv12)
3) Вычисляем вектор v3, соответствующий третьей стороне многоугольника:
xv3 = c*xv2 + s*yv2
yv3 =-s*xv2 + c*yv2
4) "Прикладываем" вектор v3 к концу вектора v2:
x3=x2+xv3
y3=y2+yv3
5) Аналогично шагам 3 и 4 получаем все недостающие вершины многоугольника: (x4, y4)...(xN, yN)

Преимущества этого решения:
1) не надо искать центр многоугольника
2) не надо переходить в другие системы координат

PS прошу прощения за флуд, форум подглючивает

4. Невидимка, 22.12.2005 01:09
Мм.. А можно поподробней с вычислением третьего вектора?

5. Lamn, 22.12.2005 01:11
Невидимка
Уже Форум все время норовил проглотить третий пункт: в предпросмотре показывает, а тут - нет.

6. OXPEHOMETP, 22.12.2005 13:57
Невидимка: Имейте в виду, что при таком подходе ошибки вычислений будут накапливаться.

7. KPAH, 22.12.2005 14:33
Можно сделать на одних арифметических операциях и вычислении квадратного корня. Писать долго, поэтому просто нарисуйте 4 подряд идущих точки многоугольника А, В, С, Д (А, В и С мы знаем, Д надо найти). соедините отрезками АС и ВД. Точка пересечения этих отрезков - К. Середина отрезка АС - точка Р. Чтобы найти Д надо из В через К отложить отрезок длиной АС. К каждый раз искать не надо, К = А + АС*т, т находим один раз по формуле т=(3*АС/4-(ВР)2/АС)/АС. Вроде ничего не напутал...

8. CrazyElk, 22.12.2005 17:23
KPAH К каждый раз искать не над Ну не совсем так. Длинну отрезка |AK| (и анологичных ) найти надо 1 раз. А вот сами точки (используя эту длинну) надо всякий раз заново. Но поскольку все равно эту и все остальные промежуточные точки искать нафиг не надо, а можно выразить координаты D сразу через координаты ABC то это замечание (что искать таки точки надо) придирочное брюзжание перфекциониста . Вот там в формулке для D и будет фигурировать отношение |KC|/|AС|. Которое и вычислять то ненадо особо по а по подобию треугольников |KC|/|BC| = |BC|/|AC| получить |KC|/|AС| = (|BC|/|AC|)^2 а уж |BC|/|AC| ищется элементарно. Ну а получив формулку для D дальше рекурсивно D1 через BCD и т.д. Собственно тоже самое получим немного "поколдовав" с формулками Lamn теже портянки вид с боку.

WBR CrazyElk
Ошибка вычисления естественно накапливатся при рекурсивном подходе будет.

9. KPAH, 22.12.2005 17:40
CrazyElk
Ну конечно же К надо находить на каждом шаге. Я просто хотел сказать что это достаточно просто. А вот подобные треугольники это круто.

10. Lamn, 22.12.2005 21:49
CrazyElk
получим немного "поколдовав" с формулками Lamn
А как надо поколдовать, чтобы уменьшить число операций (4 уможения и 4 сложения), приходящихся на одну вершину?

11. Невидимка, 23.12.2005 03:13
набросал я метод, предложенный Lamn'ом на cpp:

код:

long double x,y, x1,y1, x2,y2, x3,y3;
long double xv1,yv1, xv2,yv2, xv3,yv3;

x2=-800;
y2=0;

x=-400;
y=692.8203230276;


x1=400;
y1=692.8203230276;

int n=6;

for (int i=1;i<=n-3;i++)
{

xv1=x-x1;
yv1=y-y1;
xv2=x2-x;
yv2=y2-y;

xv3=((xv1*xv2+yv1*yv2)*xv2 + (xv2*yv1-xv1*yv2)*yv2 ) / (xv1*xv1+yv1*yv1);
yv3=((xv1*xv2+yv1*yv2)*yv2 - (xv2*yv1-xv1*yv2)*xv2 ) / (xv1*xv1+yv1*yv1);

x3=x2 + xv3;
y3=y2 + yv3;

cout << "x >>>>>>" <<x3 <<"\n";
cout << "y >>>>>>" <<y3 <<"\n";
x1=x;
y1=y;
x=x2;
y=y2;
x2=x3;
y2=y3;
}



В принципе все работает. Пасиб.

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

Если не сложно, посоветуйте, с чего бы начать:




Имеется массив неповторяющихся точек на декартовой сист.координат(кол-во n=2000). Они лежат на окружности произвольного радиуса. Необходимо найти все правильные многоугольники (число сторон от 3 до 2000), которые можно построить на данных точках (точки являются вершинами правильных многоугольников). В финале необходимо вывести сколько (шт.) и «сколькиугольных» (3-х, 10-ти и т.д.) правильных многоугольников можно построить на данных точках…





Т.е. получается, что если рассматривать только одну точку, то на ней можно построить только один единственный экземпляр правильного многоугольника со стороной k (3<=k<=2000). Так что я представляю себе алгоритм следующим образом:

(Вариант 1)
- Берем точку из массива и рассматриваем относительно нее возможные присутствия каждого из правильного k-угольника (в зависимости от k вычисляем по формуле угол, а далее определяем координаты оставшихся точек многоугольника)
- Если после обхода всех оставшихся точек оказалось, что они присутствуют в массиве, делаем пометку что в массиве присутствует такой то k-угольник.
- Рассматриваем следующий k-угольник (3<=k<=2000)
- Рассматриваем следующую точку из массива

(Вариант 2)
- Ищем расстояние от выбранной точки до каждой из оставшихся. Заносим эти данные во временный массив.
- Ищем в этом массиве пары точек, до которых от выбранной одинаковое расстояние.
- Зная координаты этих точек узнаем угол.
- Проверяем по найденному углу возможность существования такого многоугольника.
- По алгоритму Lamn'а находим предположительные координаты оставшихся точек.
- Если после обхода всех оставшихся точек оказалось, что они присутствуют в массиве, делаем пометку что в массиве присутствует такой то k-угольник; так же делаем пометку у об этом у выбранной точки.
- Рассматриваем следующую точку из массива.

Какой из вариантов вам кажется более предпочтительным?

12. CrazyElk, 23.12.2005 09:28
Lamn а я разве говорил что получится меньше операций? я просто заметил что оба способа эквиваленты. Боле того это один и тотже способ изложенный разными словами - У тебя берутся два базовых вектора и по ним строится 3 - у KPAH берутся три базовые точки (определяющие 2 вектроа) по ним строится 4-ая. Далее и там и там рекусия используя полученное значение. Если взять формулы получемые из построения KPAH то они с тождественно эквивалентны тем что у тебя с точностью до формы записи.

WBR CrazyElk

13. Lamn, 23.12.2005 10:59
Невидимка
В общем случае лежащие на окружности точки имеют иррациональные координаты. Если записать координаты таких точек в long double (не способном вместить даже произвольное рациональное число), то они формально перстанут лежать на одной окружности Эти погрешности будут везде мешаться, и их нужно везде учитывать. Например, при последовательном обходе вершин, очередную найденную вершину нужно подменять почти совпадающей вершиной из заданных пользователем.

Если критична скорость (тупой перебор не подходит), я бы сделал так:
1) Для простоты считаем что точки перечислены в порядке движения по часовой стрелке вдоль окружности. Сохраним все вершины в массиве P[N], N=2000.
2) Для каждой пары индексов 0<=i<j<N заполним структуру {dist(P[i],P[j]), i, j}, и все структуры сложим в массив D[K], K=N*(N-1)/2 (поскольку удовлетворяющих неравенству пар индексов (i,j) будет ровно K штук).
3) Отсортируем массив D по по полю dist структуры. Для простоты считаем, что быстро сортировать мы умеем.
4) Для простоты считаем радиус R окружности известным. Тогда по длине dist стороны предполагаемого правильного многоугольника можно сказать:
a) количество L вершин в многоугольнике
b) если L (с учетом погрешностей) оказалось не целым, то многоугольник с такой стороной в эту окружность вписать нельзя
Пользуясь этим соображением разрезаем массив D[] на подмассивы DL, каждый из которых соответсвует допустимой длине стороны L-угольника.
5) Для каждого из массивов DL строим граф:
a) вершины графа - индексы массива P
b) ребра графа - элементы нашего массива DL (в каждом элементе лежат как раз два индекса массива P)
Каждому из графов припишем число L вершин в предполагаемом многоугольнике.
6) В каждом графе DL ищем циклы на ровно L вершинах, такие, что:
a) при каждом переходе по ребру цикла номер в веришне графа должен возрастать (тут мы используем тот факт, что точки в массиве P перечислены в порядке движения по часовой стрелке вдоль окружности)
b) только одно ребро в цикле не удовлетворяет условию 6a

Удачи

PS Чуть подправил описание алгоритма. Кроме того, есть сомнения насчет требования упордоченности исходных точек в пункте 1, и требований 6a и 6b. При длине стороны K-угольника, значительно превосходящей умноженную на K ошибку округления, от указанных требований почти наверняка можно отказаться.

PPS Оценка времени работы. Если не принимать во внимание поиск циклов, то время работы будет O(N2logN) - столько стоит сортировка массива D. Время поиска циклов, думаю, очень сильно определяется спецификой данной задачи, и на практике окажется близко к линейному. Кажется, "тупой перебор" можно организовать так же эффективно

14. CrazyElk, 23.12.2005 12:42
Невидимка Не так и не так. Задача поиска координат углов правильного многоугольника и задача поиска правильного многоугольника на заданном наборе точек расположенных на окружности пипердикулярны. Для начала сделай преобразование (по трем точкам) переводящее окружность произвольного радиуса - в окружность единичного радиуса (для твоей задачи размер безразличен) и вырази координаты точек в полярных координатах. Собственно говоря тебе нужен исключительно угол каждой точки в полярных координатах (так что к единичной можно и не приводить ). Упорядочи точки по возрастанию угла.
И для затраdки 2 подсказки
1. Набор точек N точек образует правильный многоугольник если все углы в этом наборе кратны минимальному углу в наборе (так что ничего искать по формулкам не надо просто кратность).
2. Если набор точек образует правильный многоугольниук с числом вершин N то этот набор также образует k m-угольников где k*m = N. Точки этого набора не образуют ни с какими другими точками правильных N или m-угольников. (то есть если ты нашел 1(один) 30 угольник то смело считай что есть еще 10 3-угольников, 6 5-угольников, 5 6-угольников и 3 10-угольника + ни одна из этих точек ни с какими другими из оставшихся не образует 30, 10, 6, 5 и 3 трех угольников соотвественно при поиске таковых в последствии эти точки считать отсутсвующими)

... звиняй пора бежать. Но думаю идею ты понял

WBR CrazyElk

P.S. в догонку к 1. И более того этот минимальный угол равен .... ну ты понял (тоже самое что с расстояниями постом выше)

15. Невидимка, 23.12.2005 16:41
http://www.college.ru/mathematics/courses/function/c…raph2/theory.html

нашел вот описалово полярной системы коолрдинат.

349x349, 23,8Kb

"
Полярная система координат ставит в соответствие каждой точке на плоскости пару чисел (ρ; φ . Основными понятиями этой системы являются точка отсчета – полюс – и луч, начинающийся в этой точке, – полярная ось. Координата ρ – расстояние от точки до полюса, координата φ – угол между полярной осью и отрезком, соединяющим полюс и рассматриваемую точку, который берется со знаком «+», если угол от оси до отрезка вычисляется против часовой стрелки, и со знаком «–» в противоположном случае. Важно понимать, что число φ в полярной системе определено не однозначно: парам чисел (ρ; φ + 2πn) соответствует одна и та же точка при любых натуральных n. Для полюса ρ = 0, а угол φ не определен.

Полярные координаты легко преобразовать в декартовы. Пусть (x; y) – координаты точки в декартовой системе координат, (ρ; φ – в полярной. Тогда очевидно, что"
84x42, 0,3Kb
"Формулы обратного перехода:"
195x170, 1,1Kb


Получается надо для начала максимально точно определить центр произвольной окружности, на которой лежат эти точки. Насколько я себе это представляю - берется 4 точки. строится 2 хоры. И берутся серединные перпендикуляры от этих хорд. И точка пересечения этих серединных перпендикуляров и должна являться центром окружности, я прав?

картинка не прикрепилась. вот линк: http://open-save.narod.ru/open/img/1.jpg

Добавление от 23.12.2005 21:25:

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

16. Lamn, 25.12.2005 12:51
Га! Немного модифицировав предложенный выше алгоритм, можно решать задачу для _произвольного_ набора попарно несовпадающих точек. То есть об окружностях можно забыть.

1) Сохраним все точки в массиве P[N], N=2000.
2) Для каждой пары индексов 0<=i<j<N заполним структуру {dist(P[i],P[j]), i, j}, и все структуры сложим в массив D[K], K=N*(N-1)/2 (поскольку удовлетворяющих неравенству пар индексов (i,j) будет ровно K штук).
3) Отсортируем массив D по по полю dist структуры, от меньшего к большему.
4) Для каждого индекса l (0<=l<K) в массиве D находим пару индексов rl<=l<=sl, таких, что:
a) D[l].dist - D[rl].dist < eps && ( rl == 0 || D[l].dist - D[rl-1].dist >= eps )
b) D[sl].dist - D[l].dist < eps && ( sl == K-1 || D[sl+1].dist - D[l].dist >= eps )
где eps - погрешность вычислений/входных данных
5) Для каждой пары индексов (rl,sl), такой, что sl-rl >= 3 строим граф Gl:
a) вершины графа - индексы массива P
b) ребра графа - элементы массива D с индексами от rl до sl (в каждом элементе массива D лежат как раз два индекса массива P)
6) В каждом таком графе Gl ищем циклы, начинающиеся с ребра D[l]. Вершины графа, через которые проходит цикл, интерпретируем как вершины многоугольника. Ребра графа, через которые проходит цикл, интерпретируем как стороны многоугольника. Для сокращения поиска используем тот факт, что углы между сторонами правильного многоугольника не меньше 180-360/p градусов (где p-число ребер, уже попавих в цикл), и что эти углы попарно равны (с точностью до погрешности).

На "случайных" входных данных, думаю, обычно будет отрабатывать за O(N2logN). В худшем случае - O(N3 + T), где T - время поиска циклов.

Добавление от 25.12.2005 13:07:

Хотел бы я посмотреть на алгоритм, который решит задачу (пускай с использованием сведений об окружности) хотя бы за O(N2+A), где A - число правильных многоугольников

Добавление от 25.12.2005 13:16:

Интересно, может ли А быть асимптотически больше, чем N2?

17. CrazyElk, 26.12.2005 15:38
Невидимка
берется 4 точки Хватит 3.

Lamn
в графе Gl ищем циклы ... где T - время поиска циклов - Оценку T не обнародуеш? ПОиск все возможных циклов на графе тоже не самое быстрое дело однако (причем бесполезное см. ниже).

Если не возражаеш я переизложу то что ты предлогаеш.
1+2+3+4 - Составим таблицу всевозможных раастояний между заданными точками и кластеризуем ее выделив наборы отрезков одинаковой длинны. - таких наборов может оказатся от 1 до O(K) и все будут содержать не меньше трех отрезков - Для иллюстрации - ситуация элементарная берем точку и шагаем по окружности с углом (звини я углами и по окружности но тебе несложно будет думаю в расстояния перевести) alpha + n*eps/4. Соотвественно разница между двумя соседними (по окружности) всегда eps/4, а между четырмя последовательными уже eps. Так что три подряд кластер, а четвертый уже нет но если выкинуть первый то с двумя среднеми опять кластер. Это для последовательно идущих точек и цепочки отрезков их соединяющих. Для не последовательно через сколько кластер, а через сколько нет чуть сложнее но в целом анологично. Рядом стоящие кластер чуть отодвинулись упс. Ну да ладно это цветочки.
5+6. Для каждого выделенного кластера содержащего 3 и более отрезков строим граф связей отрезками одинаковой длинны. Ищем циклы на графах. Далее Если в графе обнаружится цикл есть правильный многоугольник
-- УУУПС а как насчет ромба тоже однако все стороны равны, цикл в наличии но рука правильным многоугольником назвать его не поднимится. А уж какие красоты, в том числе и не выпуклые но с равными по длинне ребрами мы могем построить при большем числе строн тут уж даже дух захватывает - так что от факта расположенности точек на по окружности открестится явно поспешили.

Если не учитывать факт того что точки лежат на окружности то алгоритм просто ОШИБОЧНЫЙ.

Ну а насчет хотел бы я посмотреть на алгоритм - ну посмотри то что я предложил. Совершенно не гоняясь за скоростью. На N точках можно построить мксимум N угольник или менее. Стрим матрицу N*N. По вертикали точки (в порядке возрастания полярного угла) по горизонтали N угольник. Пересечение участвует точка I в Кугольнике или нет (точка на окружности не может одновременно участвовать в двух разных К угольниках если участвует то только в одном). Дале при самом тупом раскладе проверка существания K угольника на массиве N точек (и если он находится то все точки в него входящие отмечаются и в дальнейшем поиске K не используются уже хинт но я даже это в оценке скороти не возму) - это N сканов N точек (Ну не нашлось К угольников причем всякий раз K-1 вершин находилась а на K-ой облом и оптимизацией поиска по величине мы не озабачивальсь тупым перебором шли). ИТОГОВАЯ СЛОЖНОСТЬ ТАКОГО ТУПЕЙШЕГО ПЕРЕБОРА O(N3). И никаких магических T.

Это если не пользоваться фактом кратности и не оптимизировать поиски и т.д. Про в среднем и при оптимизации проверок и поисков молчу. Зато правда фактом того что точки лежат на окружности мы естественно пользуемся поскольку сравниваим углы и на кратность заданному и т.д.

Будь проще

WBR CrazyElk

18. Lamn, 27.12.2005 01:27
CrazyElk

Начнем с корректности.
Если в графе обнаружится цикл есть правильный многоугольник
Это Ваше утверждение, а не мое
а как насчет ромба тоже однако все стороны равны, цикл в наличии но рука правильным многоугольником назвать его не поднимится
Наверное, Вы невнимательно прочитали:
цитата (Lamn):
Для сокращения поиска используем тот факт, что углы между сторонами правильного многоугольника <skipped> попарно равны (с точностью до погрешности).
Как там с равенством углов у ромба?
А уж какие красоты, в том числе и не выпуклые но с равными по длинне ребрами мы могем построить при большем числе строн тут уж даже дух захватывает - так что от факта расположенности точек на по окружности открестится явно поспешили.
Замкнутая ломаная, у которой все звенья равны, и углы между звеньями (с учетом направления обхода) тоже равны, является правильным многоугольником по определению.
Если не учитывать факт того что точки лежат на окружности то алгоритм просто ОШИБОЧНЫЙ.
В свете вышеизложенного, не согласен.

Далее оценка времени работы.
таких наборов может оказатся от 1 до O(K)
В самом плохом случае кластеров не может оказаться более чем O(N2). Оценим максимальный размер одного кластера. Забудем на минуту о погрешности, и постараемся расположить N точек на плоскости так, чтобы они образовали как можно больше отрезков фиксированной длины d. Фиксируем первую точку. В качестве второй нас устроит любая точка с окружности радуса d с центром в первой точке. Фиксируем и вторую точку. В качестве третьей точки нас устроит любая, лежащая в пересечении d-окружностей с центрами в первых двух точках. Получился равносторонний треугольник. Выбрать в этой же плоскости четвертую точку так, чтобы она была на рассоянии d от каждой первых трех невозможно (соответствующие три окружности не имеют общих точек). Очевидно, лучшее, что мы можем сделать - это замостить плоскость равносторонними треугольниками с стороной d. Оценим число отрезков длины d: к каждой точке прилегает не более 6 отрезков, то есть O(N). Вспомним про погрешность: с ее учетом две точки, лежащие на расстоянии менее eps считаются совпадающими, и запрещены по условию задачи. Если отказаться от такой трактовки погрешности, то все точки можно расположить на окружности радиуса eps, и радоваться N-факториалу равносторонних и выпуклых с точностью до погрешности многоугольников Причем, Ваш агоритм окажется еще и некорректен, так как не сможет найти их все. В общем, не вижу, как погрешность могла бы испортить оценку.. Поскольку размер кластера не превышает O(N), то общее время этого участка алгоритма не превысит O(N3). Однако в случае с окружностью число кластеров не превзойдет O(N) (по одному кластеру для каждой из N возможных длин стороны правильного многоугольника -- см первый вариант алгоритма), а общее время этого участка - O(N2).

Оценку T не обнародуеш?
Если использовать связанную с углами информацию, то сложность поиска _имхо_ соответствует сложности самой задачи (по сути, исходная задача оказывается переформулирована в терминах графов, и абстрагирована от несущественных деталей). В случае, когда точки лежат на окружности, у каждой из вершин графа будет не более двух ребер. В таком графе поиск цикла уложится в линейное время, а графов у нас - не более O(N) .... так что и этот участок имеет общее время O(N2) Самым узким местом оказывается сортировка - O(N2logN).

ну посмотри то что я предложил <skipped> ИТОГОВАЯ СЛОЖНОСТЬ ТАКОГО ТУПЕЙШЕГО ПЕРЕБОРА O(N3)
Не сомневаюсь, что в случае с окружностью тупой перебор легко уложится в O(N2logN). Однако - повторюсь - хотел бы я посмотреть на алгоритм, который решит задачу хотя бы за O(N2+A), где A - число правильных многоугольников.

Добавление от 27.12.2005 01:53:

таких наборов может оказатся от 1 до O(K)
Кстати, в примере, который Вы построили, очевидно существование не менее чем O(N) кластеров (грубо говоря, на каждую новую точку по отдельному кластеру). Можете придумать пример с O(N2) кластерами? У меня как-то не получается...



Определенно пора спать

19. CrazyElk, 27.12.2005 10:46
- Мне наверное показалось но в совокупность
цитата:
То есть об окружностях можно забыть. ....Вершины графа, через которые проходит цикл, интерпретируем как вершины многоугольника.
- приводит к найденый цикл есть правильный многоугольник

Что качается углов - Да действительно про углы было
цитата:
Для сокращения поиска используем тот факт, ...

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

Можете придумать пример с O(N2) кластерами В рамках ТВОИХ предположений ЛиииХко. Как ты утвеждаеш
об окружностях можно забыть
+ можно решать задачу для _произвольного_ набора попарно несовпадающих точек . Отсюда и танцуем - распологаем (xi, yi) следующим образом (a*i+eps*(i+1)*i/8, imod2). Да точки не на окружности - линия'с но твоему то алгоритму это по баробану - надеюсь я правильно понимаю исходные постулаты. Число кластеров посчитать несложно - порядок оцени сам у меня как раз порядок O(N2) вышел - может я чего и упустил но IMHO так.

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

Причем, Ваш агоритм окажется еще и некорректен, так как не сможет найти их все. Мой сможет поскольку я не определял алгоритм проверки кратности углов. Как посчитает реализующий алгоритм так это сравнение и будет происходить. И в выбранной реализующим и нужной для конкретного человека метрике и точности алогитм сравнивающий углы даст корректный ответ. Надо будет будут сравниватся углы с погрешностю не надо не будут. НАдо будет перевести в абсолютное расстояние переведет ненадо поступит по другому. К тому же мой алгритм (точнее зачатки и подсказки) ОПИРАЕТСЯ на факт расположенности точек на окружности применять его к _произвольному_ набору как минимум не корректно.

Посто стиль твоего изложения претендавал на математическую точность и законченность алгоритма. Так вот все что я заметил что в том виде в каком он изложен он формально не верен - по целому ряду причин в том числе нечетких формулировок в стиле ну даже ламеру понятно что IRQ15 это IDE. Естественно можно все исправить но это тогда другой алгоритм.

WBR CrazyElk

P.S Тупой перебор легко уложится в O(N2logN) - IMHO тупой не уложится, как минимум оптимизацию поиска прейдется сделать чтобы logN появился. Тупой это N^3

20. Lamn, 27.12.2005 21:44
CrazyElk
цитата (CrazyElk):
- Мне наверное показалось но в совокупность
цитата (Lamn):
То есть об окружностях можно забыть. ....Вершины графа, через которые проходит цикл, интерпретируем как вершины многоугольника.
- приводит к найденый цикл есть правильный многоугольник
Вовсе не приводит В этой цитате предлагается забыть про окружности, а но не про правильность многоугольника. Цикл предлагается интерпретировать как _некий_ многоугольник, не обязательно правильный.
цитата (CrazyElk):
дополнительное условие для ускорения поиска цикла а не дополнительное условие на цикл
Нигде не написано, что это условие является дополнительным, опциональным, или еще что-то в этом духе. Напротив, оно - неотъемлемая часть алгоритма. Взамен предложенного условия можно придумать что-то еще, так что алгоритм останется корректным, но, как Вы верно заметили, "это уже будет другой алгоритм".
цитата (CrazyElk):
И оборот речи
цитата (Lamn):
Для сокращения поиска ...
Подразумевает что этот факт опциональный
Немедленный учет ограничений на углы позволяет "сократить поиск" циклов (то есть поиск может завершится быстрее, а некоторые циклы могут остаться не найденными - да они нам и не нужны). И в результате работы такого алгоритма получатся правильные многоугольники. Никакой опциональности не подразумевается. Русский язык богат, и многие высказывания можно истолковать ошибочно, но теперь, я думаю, это недоразумение исчерпано
цитата (CrazyElk):
Число кластеров посчитать несложно - порядок оцени сам у меня как раз порядок O(N2) вышел
Пересчитывать лениво, но - кажется - действительно O(N2). Спасибо за пример.
цитата (CrazyElk):
Посто стиль твоего изложения претендавал на математическую точность и законченность алгоритма. Так вот все что я заметил что в том виде в каком он изложен он формально не верен - по целому ряду причин в том числе нечетких формулировок
Честно говоря, я писал этот алгоритм чтобы поделиться идеей с наделенными чувством здравого смысла людьми, а не для формального разбора Так что цели обеспечить математическую точность и законченность не преследовал. Что касается стиля - всё разбито на пункты, так как в таком виде алгоритм легче читать, и легче ссылаться на какие-то его фрагменты при обсуждении. Не люблю читать "кашу".

цитата (CrazyElk):
К тому же мой алгритм (точнее зачатки и подсказки) ОПИРАЕТСЯ на факт расположенности точек на окружности применять его к _произвольному_ набору как минимум не корректно.
Так набор не произвольный - все точки лежат на окружности радиуса eps
цитата (Lamn):
Причем, Ваш агоритм окажется еще и некорректен, так как не сможет найти их все.
цитата (CrazyElk):
Мой сможет поскольку я не определял алгоритм проверки кратности углов.
За то Вы оценили время работы своего алгоритма - O(N3). Так что посчитать, сколько там будет правильных точностью до eps многоугольников, он заведомо не сможет - их будет примерно N-факториал Впрочем, я склонен трактовать условия задачи, как запрещающие точкам лежать друг к другу ближе, чем eps -- чтобы таких бредовых ситуаций не возникало.

21. CrazyElk, 28.12.2005 12:35
Мажорантная оценка. Поскольку правильный многоугольник одназначно может быть задан двумя упорядоченными точками и числом вершин (точки дают - длинну, упорядоченность - направление отсчета угла, число вершин - угол) то число правильных к-угольников не может превосходить количество упорядоченных пар точек. Число упорядоченных пар точек O(N2). Из N точек максимум можно построить правильный N угольник кто бы мог подумать . Значить максимум максиморум число различных ПРАВИЛЬНЫХ многоуголников вершины которых находятся в массиве точек размерности N не может превосходить оценку O(N3).

Сам найдеш ошибку в рассуждениях приводящих к факториалам? в P.S. подсказка

WBR CrazyElk

P.S. Нельзя жить наполовину, если с заданной точностью на роль текущей вершины у тебя нашлось 2 точки в наборе значить в наборе задана дважды одна и таже точка (в пределх заданной точности) а не существуют два разных правильных многоугольника. Нельзя если специально не оговаривать для одних целей иметь одну точность (абсолютную) а для других другую (через eps). Короче тут или точки надо считать за одну совпадающими или многоугольники - на выбор. Или что самое правильное АККУРАТНО формулировать что значить РАЗЛИЧНЫЕ многоугольники в условиях приближенных вычислений. В зависмости от формулировки число РАЗЛИЧНЫХ многоугольников может драматически поменятся (я вот так на вскидку уже вижу пару тройку взаимно перпендикулярных опеределений все разумные а итоговое число еще как поменяется). как впрочем и понятие ПРАВИЛЬНОСТИ. Многоугольник станет не "правильный" а "почти правильный" и это сааапсем другая история однако - это как с поиском максимума - абсолютный максимум он один (сам максимум а не число точек области значения где он достигается ) а вот почти максимумомов (экстремумомов) ууууууууу ). Да утебя заданно неявно такое определение просто нет там понятие РАЗЛИЧНЫЕ почти правильные - а еще точнее молчаливо предпологвется что различные это построенные из различных вершин неглядя на их взаимное расположение. Собственно это не совсем та задача которую первоначално огласил автор.

22. Lamn, 29.12.2005 00:29
CrazyElk
Пусть дана замкнутая ломаная P0,P1,P2,P3, причем координаты вершин известны с точностью до eps. Нужно ответить на вопрос: является она правильным многоугольником или нет. Возможны два подхода:
1) Если сдвинув каждую точку не более чем на eps, можно получить ломаную, не являющуюся в точности правильным многоугольником, то ответ: "не является".
2) Если сдвинув каждую точку не более чем на eps, можно получить ломаную, являющуюся в точности правильным многоугольником, то ответ: "является".
С первым подходом при eps>0 вообще никакой набор точек нельзя назвать правильным многоугольником. Со вторым подходом - если все точки лежат внутри круга с диаметром eps - то это заведомо правильный многоугольник.

Со вторым подходом ответ на задачу
цитата (Невидимка):
Имеется массив неповторяющихся точек на декартовой сист.координат(кол-во n=2000). Они лежат на окружности произвольного радиуса. Необходимо найти все правильные многоугольники (число сторон от 3 до 2000), которые можно построить на данных точках (точки являются вершинами правильных многоугольников). В финале необходимо вывести сколько (шт.) и «сколькиугольных» (3-х, 10-ти и т.д.) правильных многоугольников можно построить на данных точках…
вполне может иметь порядок N-факториал. И все многоугольники будут попарно различны в том смысле, что будут обходить исходные точки в различном порядке (а то и вовсе иметь различное число вершин).

Даже жестче. Если все точки лежат внутри круга с диаметром eps, любое (размером больше 2) подмножество исходного множества точек может образовывать правильный многоугольник. Всего различных подмножеств существует 2N, а подмножеств размером больше двух - O(2N). Соответствующие двум разным подмножествам правильные многоугольники будут _существенно_ различны: в одном из них _обязательно_ найдется вершина, которой _вообще_ нет в другом.

Разумеется, замкнутые ломаные P0,P1,P2 и P0,P1,P2,P3 не могут быть правильными многоугольниками одновременно. Хорошо, если условия задачи не требуют "одновременности", а то придется искать все возможные непротиворечивые решения -- безнадёга

если с заданной точностью на роль текущей вершины у тебя нашлось 2 точки в наборе значить в наборе задана дважды одна и таже точка (в пределх заданной точности)
Вот-вот, и я о том же Дружно считаем такие входные данные некорректными Хотя в реальной жизни может оказаться, что из построения входных данных точно изветно, что это 2 _различных_ точки, кроме того у них не совсем совпадают eps-окрестности, вот их и кормят алгоритму. И мой алгорим, кстати, такую задачу успешно решит, хотя и с менее привлекательной оценкой времени работы.

Добавление от 29.12.2005 00:34:

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

23. CrazyElk, 29.12.2005 12:23
Lamn - И мой алгорим, кстати, такую задачу успешно решит - Если все еще незаметно.

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

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

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

Замечание 1- Для абсолютной точности оба этих определения ЭКВИВАЛЕНТЫ. При попыке добавить к словам равно и одинаково добавку с заданной точностью (eps) определения становятся НЕЭКВИВАЛЕНТЫМИ. При одной и тойже точности (eps) по одному определению моногоугольник правильный по другому нет. запомнили и ползем дальше

Совпадающие правильные многоугольники
Определение 1 - правильными многоугольники совпадают если все их вершины общие (вершины одного являются вершинами другого и наоборот)
Определение 2 - правильные многоугольники совпадают если они имеют общую описанную окружность одинаковое количество вершин и хотябы одну общую вершину (остальные станут общими автоматом)

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

Комбинируюя определения "Правильный многоугольник " и определения "Совпадающие многоугольники" (я специально ограничился по 2 штуки каждого но "если Вам надо свежих определений у нас их есть" сколько угодно). Получаем оно и тоже число различных (несовпадающих) правильных многоугольников при абсолютной точности и потенцеально 4 разных числа при попытке ввести понятие с точностью до eps в определения.

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

Если вводить с точностью до ... и не оговаривать строго терминов "Правильный многоугольник" и "Совпадающие многоугольники" то алгоритмов правильных но дающих разные результаты вагон и маленькая тележка. Каждый правильный - но по своему. Ты выбрал одно из возможных (и Imho не самых логичных хотя и имеющих право на жизнь) определений этих двух понятий - это не значить что другие определения и алгоритмы их реализующие ошибочны и неправильны - даже если они дают совершенно другой ответ.

В чем по твоему нелогичность определения правильного многоугольника по варианту 2 в котором слово одинаково дополненно с точностью до eps (а результат другой однако при той же заданной точности eps).

Что до эквивалентных многоугольников чем плохи определения - правильные монгоугольники с одинаковым числом вершин совпадают
1) если их вершины совпадают с точностью до eps
2) если площадь их пересечения с точностью до eps^2 равна площади многоугольника
....
Продолжи сам.
Самостоятельная работа определить когда для каких случаев и твой алгоритм даст ошибку в числе многоугольников. Значить ли что твой алгоритм ошибочен решай сам. IMHO он просто о другом и один из возможных вариантов.

IMHO Полагатся на то что всем все и так понятно в таких тонких вопросах как приближенные вычисления не следует. Особенно если решено с шашкой наголо выяснить "истинну в последней инстанции" которой увы нет и не предвидится.

Больше спорить не буду и так уже думаю давно все всем понятно. Так что пьем . Считаем так как считаем нужным и радуемся жизни. Задачи убедить коголибо в чем либо у меня нет. Свободного времени тоже не особо много. А продемонстировать разнообразие вариантов я и так думаю на 110% уже выполнил.

WBR CrazyElk

P.S. Молчаливо обычно предпологают что числа равны если они равны с точностью до текущего машинного представления. Ошибки сравнения и погрешности расчетов в этом случае относятся не к ошибками алгоритма, а к ошибкам округления и оговариваются отдельно. Так что различие ответов двух алгоритмов вызванное неточностью машинного представления данных или конверсией не говорит об ошибочности или правильности одного из них.
Если нужн алгоритм с точностью до ... то способы и правила оценки этого самого точность до .... требуют корректного и тщательного формулирования. Это так к слову.

24. Lamn, 29.12.2005 20:08
CrazyElk
С наступающим!

25. Невидимка, 29.12.2005 22:42
пасиб всем за идеи

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

26. CrazyElk, 30.12.2005 10:09
Lamn & Невидимка

Невидимка - Оценка драматически зависит от выбора определений точнее будеш ли ты искать решение с точностью до .... или точно. Если ищещ точные решения то она (оценка) обычно не превышает O(N3) для самых "прямолинейных" реализаций практически любых идей (а для конгкреных прозвучавших мы давали). Полиноминальная сложность алгоритма обычно считается приемлемой. Тем более что любой из прозвучавших здесь Hint-ов как то
1. Предварительное выделение вершин кандидатов (неважно по длинне отрезков по равенству уголов еще как ... )
2. Поиск начиная с максимальных T угольников с немедленным определением всех производных k и m угольников (Т=k*m) и исключением вершин из наборов кандидатов для поиска k и m угольников.
3. Предварительная сортировка (например постронием Hash map) для величин (углов, расстояний ... ) которые предпологается использовать при проверки првильности и несовпадения и предварительное построение вспомогательних структур данных.

Только уменьшит или оставит эту оценку неизменной (для самого плохого случая). А в среднем (для случаного набора) сократит время работы (IMHO существенно). (даю в порядке уменьшения полезности для уменьшения среднего времени работы - но это субьективно)

Если ты будеш искать "правильные с точностью до " то тут очень важно определится с видом исходных данных если они не попадают в "граничные" для твоих определений условия, то все тоже самое что и для точных алгоритмов. А вот если возможны случаии граничные - например описанный Lamn, все точки в eps окружност, - тонкости определений начинают играть определяющую роль в деле оценки сложности алгоритма.

IMHO - Не заморачивайся. То очем тут была баталия это маргинальные (граничные) случаи и борьба за "чистую идею" для практики эти случаи редкое (хотя и встречающееся) явление. Для курсовой думаю достаточно упомянуть что мы считаем что данные достаточно хорошие чтобы таких ситуаций не возникало - лично я считаю что отражение в курсовой самого факта знания о существовании граничных случаев (можно с примером) даже если твой алгоритм их не учитывает это выше крыши. Если преподавателю надо чтобы алгоритм и граничне варианты учитывал пусть уточняет термины "правильный многоугольник" и "совпадающие правильные многоугольники" тогда уже и о алгоритмах думать можно.

WBR CrazyElk

Еще раз

27. WreWolf, 01.10.2006 10:45
Данн масив точек в декартовой системе координат.
Необходимо описать вокруг них окружность минимального радиуса.

28. MBo, 01.10.2006 12:44
>Необходимо описать вокруг них окружность минимального радиуса
гуглить miniball

29. Harkonnen, 02.10.2006 07:24
WreWolf
Данн масив точек в декартовой системе координат.
Необходимо описать вокруг них окружность минимального радиуса.

По простому - перебором. Да-да... там неоднозначности, если её просто тупо наращивать. Есть оптимизации - получается приемлемо.

По-умному - строятся диаграммы Воронова (afaik O(N^3)) (разбиените плоскости относительно равноудалённости) и ищутся locus points. Для вписанной - тоже самое, только относительно сторон, а не вершин.

30. MBo, 02.10.2006 19:13
Harkonnen

Да наверно, не стоит для описанной окружности Вороного строить, если алгоритм Minidisk (Welzl и модификации) находит решение за амортизированное время O(N)...

31. Harkonnen, 02.10.2006 20:31
MBo
Понял, thanks. Пол-года назад искал по "minimal circumscribed circle" - не напоролся на него

32. WreWolf, 07.10.2006 12:43
А мона ссылку
А то там я ничего не понял(в том что нашел)
А толкового вообше не нашел



URL: http://forum.ixbt.com/topic.cgi?id=26:33544

Время GMT +03. Даты в формате dd.mm.yyyy.
Rambler's Top100