Расчет линий, наиболее подходящих для эллипса - PullRequest
3 голосов
/ 03 апреля 2012

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

Мое решение для единичного круга было таким образом.

def f(u, v, r):
    mid_uv = (u + v) * 0.5
    N = normalized(mid_uv)

    return N * r

И повторите v = f(u, v, r) до radius - |v| < error.

Затем просто возьмите 2^i (i - количество итераций) в качестве необходимого количества сегментов.Этот алгоритм, вероятно, может быть O(1) и не работает для эллипсов (для чего он мне нужен).

Как я могу его адаптировать?Или еще лучше, есть ли другое решение?

Ответы [ 2 ]

3 голосов
/ 03 апреля 2012

Я не могу сформулировать хороший аккуратный ответ - работа с эллипсами намного сложнее, чем круги - но пошагово:

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

error = 1 - math.cos( angle / 2 )

(Вы можете увидеть это, если нарисуете диаграмму с окружностью, хордой и биссектрисой аккорда.) Инвертируя эту формулу, вы можете вычислить угол с учетом допустимой ошибки. Первая строка кода дает точный угол; вторая строка сжимает угол, если это необходимо, так что он является точной долей всего круга.

angle = 2 * math.acos( 1 - error )
angle = (2*math.pi) / math.ceil( (2*math.pi) / angle )

Получив угол, легко рассчитать точки вокруг единичного круга для конечных точек аккордов: [(1,0), (cos(angle),sin(angle)), cos(2*angle),sin(2*angle)), ... ]. Вы получите правильный многоугольник.

Второе - Для круга с радиусом radius выполните приведенные выше формулы, скорректированные следующим образом:

angle = 2 * math.acos( 1 - error/radius )
angle = (2*math.pi) / math.ceil( (2*math.pi) / angle )

И вычислите конечные точки хорды, умножив значения sin и cos на радиус.

Третий - Для эллипса с максимальными и минимальными радиусами major и minor, я бы использовал формулу круга, чтобы снова вычислить угол:

radius = max( major, minor )
angle = 2 * math.acos( 1 - error/radius )
angle = (2*math.pi) / math.ceil( (2*math.pi) / angle )

Если основной радиус находится в направлении x, а младший радиус - в направлении y, то вы можете рассчитать конечные точки хорды следующим образом:

[ (major, 0),
  (major*cos(angle), minor*sin(angle)),
  (major*cos(2*angle), minor*sin(2*angle)),
  ... ]

Это не всегда дает вам минимальный многоугольник для эллипса (у него будет больше аккордов, чем необходимо около малой оси, особенно для очень сжатых эллипсов), но вы должны выполнить вычисление угла только один раз. Если вам действительно нужно свести к минимуму количество аккордов, то после прорисовки каждого аккорда вам потребуется пересчитать угол после каждого аккорда, и формула не является прямой (где «не прямой» = «трудно мне разобраться ").

1 голос
/ 03 апреля 2012

Существует решение O (1) для круга: вы можете вычислить количество равных сегментов, чтобы получить необходимое сагитта . Эллипс - более сложный случай. Максимальная сагитта будет для аккорда, перпендикулярного большей полуоси (ближний фокус), поэтому представляется разумным выбрать точки соединения сегментов на концах большой полуоси (как минимум - в первом приближении)

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...