ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Равномерное распределение точек на окружности
25 сообщений из 37, страница 1 из 2
  1  все
Равномерное распределение точек на окружности
    #37877791
Димитрий85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Димитрий85
Гость
Даны координаты центра окружности (x0, y0), радиус r, нескольких точек на окружности (x1 y1), (x2 y2),... (xn yn).
Нужно добавить заранее известное и постоянное количество N точек к данной окружности, чтобы распределение было как можно более равномерным.
У меня загвоздка с перебором - не могу додуматься как организовать цикл, на каждой из итераций которого вычислять "равномерность" распределения.
Вычислять "равномерность" планирую по формуле - находим среднюю длину дуг окружности между соседними точками в каждой из комбинаций распределения. Далее считаем сумму абсолютных отклонений длин дуг от среднего значения. Наименьшее значение и покажет оптимальную комбинацию.
Также вижу трудность при вычислении "соседства" двух точек на окружности.
...
Рейтинг: 0 / 0
13.07.2012, 11:15
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37877803
Abstraction
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Abstraction
Участник
Димитрий85,

Преобразуйте в полярные координаты, делов-то. Дальше берем пары ("дуга", "число фрагментов, образуемых дополнительными точками"), на каждом шаге находим пару с максимальной результирующей дугой и добавляем точку.
...
Рейтинг: 0 / 0
13.07.2012, 11:23
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37877814
Димитрий85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Димитрий85
Гость
AbstractionДимитрий85,

Преобразуйте в полярные координаты, делов-то.
Вычисление "соседства" двух точек на окружности это решит. А вот что делать дальше, я все равно не могу понять... Какой цикл и как перебрать все комбинации.
...
Рейтинг: 0 / 0
13.07.2012, 11:29
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37877842
Abstraction
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Abstraction
Участник
Димитрий85,

Вот тянет написать свое предыдущее сообщение еще раз, ей-же-ей.
Соображение номер раз: если между двумя заданными точками поставлено несколько "наших", их расстановка с равными интервалами даст результат не менее равномерный в указанном смысле.
Соображение номер два: тогда у нас есть множество интервалов, по которым надо распределить N точек; если на интервал длины d i выставлено a i точек, результирующие дуги на этом интервале равны d i /a i .
Соображение номер три: жадный алгоритм в нашем случае подходит достаточно хорошо. Дает ли он всегда аналитически оптимальное решение, предлагаю выяснить самостоятельно - это же Ваша задача, в конце концов.
...
Рейтинг: 0 / 0
13.07.2012, 11:43
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37877852
Димитрий85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Димитрий85
Гость
Abstraction,
спасибо за ваши выкладки. Соображения понятны и очевидны.
Однако у меня в стартовом сообщении был ключевой вопрос ,вызвавший у меня затруднения, - как пройти по циклу, как перебрать именно комбинации "каждое расположение наших точек" с "каждым расположением опорных".
...
Рейтинг: 0 / 0
13.07.2012, 11:52
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37877860
Abstraction
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Abstraction
Участник
Димитрий85 Abstraction,
спасибо за ваши выкладки. Соображения понятны и очевидны.
Однако у меня в стартовом сообщении был ключевой вопрос ,вызвавший у меня затруднения, - как пройти по циклу, как перебрать именно комбинации "каждое расположение наших точек" с "каждым расположением опорных".Первый ответ: этого следует избегать, так как там С N+n-1 N вариантов, причем уйма заведомо неоптимальных.
Второй ответ: для построения цикла достаточно проанализировать, как была получена формула в первом ответе.
...
Рейтинг: 0 / 0
13.07.2012, 11:56
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37877874
Димитрий85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Димитрий85
Гость
Abstraction,

уточню что под всеми комбинациями я имею ввиду только те, где добавляемые точки делят существующие на равные части.
...
Рейтинг: 0 / 0
13.07.2012, 11:59
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37877875
Abstraction
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Abstraction
Участник
Димитрий85,

Да. Именно в этом предположении и были даны ответы.
...
Рейтинг: 0 / 0
13.07.2012, 11:59
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37877883
Димитрий85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Димитрий85
Гость
AbstractionДимитрий85,

Да. Именно в этом предположении и были даны ответы.

Так перебрать-то как )
...
Рейтинг: 0 / 0
13.07.2012, 12:03
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37877957
Abstraction
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Abstraction
Участник
Димитрий85AbstractionДимитрий85,

Да. Именно в этом предположении и были даны ответы.

Так перебрать-то как )Это Вам надо или мне?
Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
def split_intervals(intervals, points):
  def acc_interval(index, built, rest):
    if(index==len(intervals)):
      min=6.28;
      max=0;
      for i in range(len(intervals)):
        if(min > interval[i-1]/(built[i-1]+1)):
          min = interval[i-1]/(built[i-1]+1);
        if(max < interval[i-1]/(built[i-1]+1)):
          max = interval[i-1]/(built[i-1]+1);
      return max-min;
    best=6.28;
    for i in range(rest):
      nextbuilt = [];
      nextbuilt.extend(built);
      nextbuilt.add(i);
      result = acc_interval(index+1, nextbuilt, rest-i);
      if(result < best):
        best = result;
    return best;
  
  return acc_interval(0, [], points);
...
Рейтинг: 0 / 0
13.07.2012, 12:31
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37877977
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> У меня загвоздка с перебором - *не могу додуматься как организовать цикл, на
> каждой из итераций которого вычислять "равномерность" распределения.

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

> Вычислять "равномерность" планирую по формуле - находим среднюю длину дуг
> окружности между соседними точками в каждой из комбинаций распределения.
У тебя будет бесконечное множество комбинаций, задоблаешся пересчитывать.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
13.07.2012, 12:43
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37878006
Димитрий85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Димитрий85
Гость
Спасибо всем ответившим.
...
Рейтинг: 0 / 0
13.07.2012, 12:51
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37878155
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
Димитрий85Спасибо всем ответившим.
просто стало интересно)) представим что в задаче дано 2 точки, которые делят нашу окружность на 2 равные полуокружности....
нам надо добавить ещё 3 точки )) какой из вариантов распределения более равномерный?(в соотношениях длин дуг между точками):
1) 1:1:1:1,5:1,5
2) 1:1:1:1:2
3) 0,1 1,4 1,5 1,5 1,5

подскажите как вы считаете :)
...
Рейтинг: 0 / 0
13.07.2012, 13:45
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37878209
Abstraction
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Abstraction
Участник
ПрограмёрДимитрий85Спасибо всем ответившим.
просто стало интересно)) представим что в задаче дано 2 точки, которые делят нашу окружность на 2 равные полуокружности....
нам надо добавить ещё 3 точки )) какой из вариантов распределения более равномерный?(в соотношениях длин дуг между точками):
1) 1:1:1:1,5:1,5
2) 1:1:1:1:2
3) 0,1 1,4 1,5 1,5 1,5

подскажите как вы считаете :)По данному в первом посте описанию (и принимая окружность за 6), "неравномерность":
1) 1.2
2) 1.6
3) 2.2
...
Рейтинг: 0 / 0
13.07.2012, 14:12
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37878326
Димитрий85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Димитрий85
Гость
Програмёр,

по идее, вот так
1/2 1/2 - одна полуокружность
1/3 1/3 1/3 - вторая полуокружность
...
Рейтинг: 0 / 0
13.07.2012, 14:47
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37878331
Димитрий85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Димитрий85
Гость
Димитрий85,

А если изначально две точки и полуокружности не равны, то меньшую делим на две части одной точкой, а большую - на три двумя
...
Рейтинг: 0 / 0
13.07.2012, 14:48
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37878334
Димитрий85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Димитрий85
Гость
Кому интересно, предметная суть задачи - формировать граф. отчет (SVG), где окружность - узел, из центра которого выходят линии и пересекают ее. Задача - оптимально добавить еще несколько линий.
...
Рейтинг: 0 / 0
13.07.2012, 14:49
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37878346
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
Димитрий85Кому интересно, предметная суть задачи - формировать граф. отчет (SVG), где окружность - узел, из центра которого выходят линии и пересекают ее. Задача - оптимально добавить еще несколько линий.

понял)) значит наличие даже 20 одинаково-оптимальных решений не помешают выполнению задачи :)
...
Рейтинг: 0 / 0
13.07.2012, 14:56
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37878372
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
p.s. Хотя я брал бы не "сумму абсолютных отклонений", а "сумму квадратов абсолютных отклонений". так как варианты 1.2:1.2:0.6:1.5:1.5 и 1:1:1:1.5:1.5 по предложенной автором формуле будут одинаково-равномерны (и как тогда выбрать нужный нам вариант?), хотя явно понятно, что второй вариант более равномерен. "сумму квадратов абсолютных отклонений" это явно покажет :)
...
Рейтинг: 0 / 0
13.07.2012, 15:04
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37878376
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Димитрий85Кому интересно, предметная суть задачи - формировать граф. отчет (SVG), где окружность - узел, из центра которого выходят линии и пересекают ее. Задача - оптимально добавить еще несколько линий.Тогда я бы предложил сменить критерий оптимизации. Вместо непонятной "равномерности" - максимизировать минимальное расстояние между точками на окружности.
...
Рейтинг: 0 / 0
13.07.2012, 15:05
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37878395
Димитрий85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Димитрий85
Гость
miksoft,

Интересное предложение, и, скорее всего, более быстродейственное. Визуализация алгоритма тоже может быть интересной. )
Спасибо.
...
Рейтинг: 0 / 0
13.07.2012, 15:11
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37878429
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Продолжаю мысль - тогда "подвижные" точки есть смысл размещать только равномерно на каждом отрезке дуги между "неподвижными". Тогда задача сводится к решению вопроса "сколько напихать точек в тот или иной интервал". Другими словами - найти способ разделения N точек на K групп.
...
Рейтинг: 0 / 0
13.07.2012, 15:19
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37878493
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
miksoftПродолжаю мысль - тогда "подвижные" точки есть смысл размещать только равномерно на каждом отрезке дуги между "неподвижными". Тогда задача сводится к решению вопроса "сколько напихать точек в тот или иной интервал". Другими словами - найти способ разделения N точек на K групп.

может не оптимально, но просто.... делим окружность на k дуг опорными точками..., а далее в цикле (пока не закончатся точки) по принипу:
1. Ищем дугу, которая делится нашими (не опорными) точками на самые длинные промежутки (дуги)
2. Добавляем к числу точек на этой дуге ещё одну

В итоге получим k чисел, каждое соответствует числу точек на данной дуге... распределяем их равномерно по дуге (как и было сказано ранее) и ... готово :)
...
Рейтинг: 0 / 0
13.07.2012, 15:42
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37878512
Abstraction
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Abstraction
Участник
ПрограмёрmiksoftПродолжаю мысль - тогда "подвижные" точки есть смысл размещать только равномерно на каждом отрезке дуги между "неподвижными". Тогда задача сводится к решению вопроса "сколько напихать точек в тот или иной интервал". Другими словами - найти способ разделения N точек на K групп.

может не оптимально, но просто.... делим окружность на k дуг опорными точками..., а далее в цикле (пока не закончатся точки) по принипу:
1. Ищем дугу, которая делится нашими (не опорными) точками на самые длинные промежутки (дуги)
2. Добавляем к числу точек на этой дуге ещё одну

В итоге получим k чисел, каждое соответствует числу точек на данной дуге... распределяем их равномерно по дуге (как и было сказано ранее) и ... готово :)И Вам пирожок с верхней полки.
12861765
...
Рейтинг: 0 / 0
13.07.2012, 15:50
| Ответить | Цитировать | Написать  
Равномерное распределение точек на окружности
    #37878542
Димитрий85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Димитрий85
Гость
Програмёрможет не оптимально, но просто.... делим окружность на k дуг опорными точками..., а далее в цикле (пока не закончатся точки) по принипу:
1. Ищем дугу, которая делится нашими (не опорными) точками на самые длинные промежутки (дуги)
2. Добавляем к числу точек на этой дуге ещё одну

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

Не получится ли, что все наши точки напихаются в один интервал между двумя опорными, а другие интервалы окажутся не заполненными подвижными точками?
...
Рейтинг: 0 / 0
13.07.2012, 16:07
| Ответить | Цитировать | Написать  
25 сообщений из 37, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Равномерное распределение точек на окружности
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&fpage=66&tid=1342194]:
 0ms
get settings:
 8ms
get forum list:
 16ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 49ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 35ms
get tp. blocked users:
 1ms
others: 201ms
total:  326ms
созд. / загр.: 326ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]