[v1talka]

Здравствуйте! Очень нужна помощь с написанием программы на AutoLISP. Условие: квадрантное представление окружности. То есть, пользователь должен выбрать окружность, которая будет представлена в виде квадратиков с точностью (количеством квадратиков), которую введет пользователь. Алгоритм выполнения представляю почти досконально, проблема только с реализацией этого на AutoLISP, который до этого не использовал. Буду очень благодарен, если кто согласится помочь.

[Кулик Алексей aka kpblc]

А можно рисунок глянуть? Чего-то я ничего не понял...

[v1talka]

если кто-то возьмется, могу подробнее всё объяснить. заранее спасибо.

- нужно что-то типа этого, только в 2d

[Дима_]

Ну скажем так если не объяснишь - то точно никто не возьмется.

[v1talka]

Сообщение от Дима_ Ну скажем так если не объяснишь - то точно никто не возьмется.

я понимаю. пытаюсь объяснить. Октантное или воксельное представление есть, оно используется для 3d моделей, а мне нужно квадрантное, т.е. то же самое, но для 2d окружности.

[Кулик Алексей aka kpblc]

Картинку приложи к посту. Подробности - в справке по форуму.

[v1talka]

Сообщение от Кулик Алексей aka kpblc Картинку приложи к посту. Подробности - в справке по форуму.

приложил ко второму посту, спасибо

[Дима_]

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

[v1talka]

в ЛС скинул Вам про октантное дерево информацию, она аналогична тому, что нужно мне.
В общем, есть чертеж, в котором есть окружность. Пользователь должен выбрать любую окружность, для неё я нахожу координаты центра (x,y) и радиус. это потребуется для построения первого описанного вокруг окружности квадрата. затем нужно, чтобы пользователь ввел число квадратов, на которые ему нужно будет еще разделить этот квадрат (точность). т.е. это будет число 1, 4, 9, 16, 25 и т.д. вот до этого момента код я написал. дальше сложнее. я бы делал так: цикл, в котором каждый раз проверяется пересекается ли квадрат окружностью. для первого прохода цикла это не так сложно - проверить всего пересекается ли описанный вокруг окружности квадрат с окружностью. если да, то разделить его на n частей. n будет зависеть от требуемой точности. дальше этот цикл будет проходить до тех пор, пока квадратов не станет n. т.е. делиться на части будут только те квадраты, которые пересекаются с окружностью.
Пример: пользователь ввел число 256. сначала описывается квадрат вокруг окружности, потом он проверяется пересекается ли он с окружностью. ответ - да - делим на 4 части, затем проверка пересекаются ли эти 4 квадрата с окружностью, ответ - да - делим каждый из них еще на 4 и т.д. Когда количество квадратов = n - удаляем квадраты, которые находятся за пределами круга. Приложил картинки для наглядности:
[IMG]http://s002.***********/i199/1112/8f/ae2011d5a76a.png[/IMG][IMG]http://s43.***********/i101/1112/12/974962eb20b3.png[/IMG][IMG]http://i014.***********/1112/ad/d1b8a97032a2.png[/IMG][IMG]http://s017.***********/i424/1112/eb/ee45fb3cc589.png[/IMG][IMG]http://s16.***********/i191/1112/bd/f218cf54f654.png[/IMG][IMG]http://s44.***********/i105/1112/70/4ceb13ef04ae.png[/IMG][IMG]http://s017.***********/i432/1112/26/db40b309d9dd.png[/IMG][IMG]http://s017.***********/i431/1112/d6/ebf38384ffd2.png[/IMG][IMG]http://s017.***********/i418/1112/85/d24fa68086cf.png[/IMG]

[zamtmn]

Описаный выше алгоритм - это модификация алгоритма разбиения пространства, им не достичь ограничения на N квадратов в разбиении

дальше этот цикл будет проходить до тех пор, пока квадратов не станет n

Это будет не цикл, а рекурсия. Каждая итерация может добавлять больше одного квадрата, когда вы достигните ограничения N, у вас в стеке рекурсии останутся вообще не разбитые и "недобитые" квадраты. Такчто ограничение N - не верное. нужно ограничивать размер квадрата и глубину рекурсии.

т.е. это будет число 1, 4, 9, 16, 25

Зачем? разбивать всегда на 4 (или на 2, но тогда нужно смотреть по горизонтали или вертикали буть текущий квадрат\прямоугольник) результат всеравно будет аналогичный.

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

[v1talka]

Сообщение от zamtmn Ну а так как ровно N квадратов таким алгоритмом всеравно не получить, лучше воспользоваться алгоритмом растеризации окружности Брезенхема, пощитав размер квадрата для примерного получения N, либо запросив от пользователя этот размер.

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

[Дима_]

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

[v1talka]

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

оно мне для сдачи лабораторной в универе. требование было - квадрантное представление круга. как пример дали посмотреть октантное представление 3d моделей. всё, кроме этого, мои мысли по этой задаче

[Дима_]

Так с какого Вы решили что задавать надо именно количеством квадратов??

[v1talka]

Сообщение от Дима_ Так с какого Вы решили что задавать надо именно количеством квадратов??

просто предположил, что так будет проще. возможно, это не лучший вариант, не спорю

[_REGEN]

Сообщение от v1talka пользователь должен выбрать окружность, которая будет представлена в виде квадратиков с точностью (количеством квадратиков)

Сообщение от v1talka требование было - квадрантное представление круга

Так в виде квадратов или квадраНтов?

[v1talka]

Сообщение от _REGEN Так в виде квадратов или квадраНтов?

видимо, квадрантов...

[Profan]

Толковый словарь русского языка под редакцией Т. Ф. Ефремовой

КВАДРАНТ
квадрант [квадрант] м. 1) Сектор с центральным углом в 90 градусов; четвертая часть круга. 2) Старинный угломерный астрономический инструмент для измерения высоты небесных светил над горизонтом и угловых расстояний между светилами. 3) Прибор для измерения углов при вертикальной наводке артиллерийских орудий.

[Дима_]

Сообщение от v1talka видимо, квадрантов...

Я плачу - ты сходи в универ что-ли узнай чего нужно-то.
Offtop: А вобще по таким студентам "сапоги" плачут.

[Li6-D]

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

Теперь направляющие косинусы решения:
1) Пусть один такой квадрат найден (в качестве первого квадрата можно принять правую квадрантную точку окружности).
Определяем, через какую сторону или вершину выходит из квадрата окружность (допустим против часовой стрелки).
Думаю, это самая сложная часть алгоритма.
2) В зависимости от направления выхода вычисляем координаты следующего квадрата - это координаты предыдущего квадрата, измененные на шаг сетки (по +x, +y или +x&+y - итого 8 вариантов).
Вычисляем квадраты по цепочке до тех пор, пока не наткнемся на первый квадрат последовательности.