Здравствуйте! У меня появилась задача, которую, к своему удивлению, никак не могу решить.

Итак: есть дуга заданная центром, радиусом и конечными точками.
Задача: Постоить эту дугу попеременным перемещением по осям х, у

Если не очень понятно, то поясняю: Например, есть дуга, заданная центром (x0, y0) и радиусом r. Тогда чтобы ее построить попеременным движением по осям делаем следующее:

1. Берем точку (x0-r, y0)
2. постепенно прибавляя к координате х по некоторой константе(шагу) вычисляем соответствующий этому иксу

y:= Round(sqrt(sqr(circle.radius) - sqr(x - circle.centre.X)) + circle.centre.Y);

3. Находим разность между координатами последней нарисованной точки и соответственно передвигаемся по осям на dx, dy
4. Делаем так до тех пор пока текущее значение х <= x0 + r
5. Повторяем те же пункты, но во 2 считаем

Round(-sqrt(sqr(circle.radius) - sqr(x - circle.centre.X)) + circle.centre.Y);

Надеюсь, что хоть кто-нибудь понял, что я имел ввиду.

P.S. Другие подобные ветки читал, но путного ответа не нашел...

Заранее спасибо!

Здравствуйте, ShimoN, Вы писали:

SN>Здравствуйте! У меня появилась задача, которую, к своему удивлению, никак не могу решить.

SN>Итак: есть дуга заданная центром, радиусом и конечными точками.
SN>Задача: Постоить эту дугу попеременным перемещением по осям х, у

Эта штука называется google: алгоритм Брезенхейма для окружности
Например, на Алголисте: http://algolist.manual.ru/graphics/painting/circle.php

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, ShimoN, Вы писали:

SN>>Здравствуйте! У меня появилась задача, которую, к своему удивлению, никак не могу решить.

SN>>Итак: есть дуга заданная центром, радиусом и конечными точками.
SN>>Задача: Постоить эту дугу попеременным перемещением по осям х, у

К>Эта штука называется google: алгоритм Брезенхейма для окружности
К>Например, на Алголисте: http://algolist.manual.ru/graphics/painting/circle.php

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

Здравствуйте, ShimoN, Вы писали:

SN>Так то оно так, но вы не учли один ньюанс. Мне не нужны сами точки, мне нужны дельты — расстояния по каждой из осей на которые надо переместиться.

Для этого надо взять каноническое уравнение окружности X^2 + Y^2 = R^2. Далее предположим, что у нас уже есть некая "затравочная" точка на окружности (почти на окружности). Для нее считаем выражение

abs(X*X + Y*Y — R*R)

Это будет значение оценочной функции. Далее выполняем три пробных шага — вычисляем для (X+1,Y), (X,Y+1) и (X+1,Y+1) и шагаем в ту сторону, в которой значение оценочной функции минимально.

Вместо "+1" может быть "-1". В первом квадранте dx=-1, dy=+1, во втором -1,-1 и т.д.

Фишка еще в том, что на каждом шаге нам не обязательно умножать. X^2 и Y^2 легко вычисляются инкрементальным способом. Ну, для затравочной точки надо посчитать все честным способом.

Здравствуйте, McSeem2, Вы писали:

MS>Для этого надо взять каноническое уравнение окружности X^2 + Y^2 = R^2. Далее предположим, что у нас уже есть некая "затравочная" точка на окружности (почти на окружности). Для нее считаем выражение

MS>abs(X*X + Y*Y — R*R)

MS>Это будет значение оценочной функции. Далее выполняем три пробных шага — вычисляем для (X+1,Y), (X,Y+1) и (X+1,Y+1) и шагаем в ту сторону, в которой значение оценочной функции минимально.

MS>Вместо "+1" может быть "-1". В первом квадранте dx=-1, dy=+1, во втором -1,-1 и т.д.

MS>Фишка еще в том, что на каждом шаге нам не обязательно умножать. X^2 и Y^2 легко вычисляются инкрементальным способом. Ну, для затравочной точки надо посчитать все честным способом.

Хм... Что за оценочная функция??? Что она оценивает??? Я не очень понял эту математику. Главной проблемой для меня является как раз определение в каком квадранте начинается и в каком заканчивается дуга, а также, зная что рисуется дуга против часовой стрелки, как определить в какие квадранты она вообще пересекает. А зная это, я смогу воспользоваться процедурой наподобии описанной в первом посте для круга но только первую половину рисовать от какой-то точки и вторую.

Здравствуйте, ShimoN, Вы писали:

MS>>abs(X*X + Y*Y — R*R)

MS>>Это будет значение оценочной функции. Далее выполняем три пробных шага — вычисляем для (X+1,Y), (X,Y+1) и (X+1,Y+1) и шагаем в ту сторону, в которой значение оценочной функции минимально.

SN>Хм... Что за оценочная функция??? Что она оценивает??? Я не очень понял эту математику.

Это теорема Пифагора. X,Y — катеты, R — гипотенуза (в преположении, что центр окружности нажодится в начале координат).

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

Для определения квадранта надо определить угол. Если у нас угол задан не значением, а неким вектором (X,Y), то для вычисления значения есть функция atan2(Y,X).

Здравствуйте, ShimoN, Вы писали:

SN>Так то оно так, но вы не учли один ньюанс. Мне не нужны сами точки, мне нужны дельты — расстояния по каждой из осей на которые надо переместиться.

А что здесь тяжёлого?
Если ты обнаруживаешь, что с k-го по k+n-ный шаг перемещаешься только на +1 по оси X, то очевидно, dX=n.
Тебе всё равно придётся это сделать, ты же сам написал: "построить дугу". Значит, будешь эти точки прорисовывать.

Причём алгоритм Брезенхейма даже не требует постоянного вычисления квадратов (не говоря уже о квадратных корнях)!
Если для данной точки (x,y) известны значения xx = x^2 и yy = y^2 (просто запомнили их), то (x+1)^2 = x^2+2*x+1 = xx+2*x+1.

---

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

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, ShimoN, Вы писали:
К>Поскольку пошаговое рисование дуги тебя не удовлетворило, я подозреваю, что ты неточно сформулировал вопрос.
К>Расскажи, "что" ты хочешь сделать, а не сразу "как".

Мне надо запрограммировать фрезерный станок, который должен рисовать на заготовке то, что нарисовано на картинке в моем графическом редакторе.
У меня есть возможность двигать моторами по оси х и у. Я в своем графическом редакторе запоминаю данные про каждую нарисованную фигуру и затем пытаюсь нарисовать ее высчитывая дельты и перемещая фрезу на них. Если я хочу нарисовать быстрее (реже менять направление осей и их самих), то просто прибавляю к x не по 1 а заданное число. Поэтому мне не подходит алгоритм поточечного рисования, учитывая тем более то, что я его так и не понял, замысел его мне не понятен.

Здравствуйте, ShimoN, Вы писали:

SN>Мне надо запрограммировать фрезерный станок, который должен рисовать на заготовке то, что нарисовано на картинке в моем графическом редакторе.
SN>У меня есть возможность двигать моторами по оси х и у.

Вот это очень существенный момент и с него надо было начинать.
1) Можно ли включить одновременно оба мотора?
2) Можно ли управлять скоростью моторов?
3) Если можно, то с какими градациями?

SN>Я в своем графическом редакторе запоминаю данные про каждую нарисованную фигуру и затем пытаюсь нарисовать ее высчитывая дельты и перемещая фрезу на них. Если я хочу нарисовать быстрее (реже менять направление осей и их самих), то просто прибавляю к x не по 1 а заданное число.

Алгоритм Брезенхема для этого тоже подходит. Никто не мешает накапливать и объединять шаги с динаковым направлением.

SN>Поэтому мне не подходит алгоритм поточечного рисования, учитывая тем более то, что я его так и не понял, замысел его мне не понятен.

Значит надо понять. Тогда, возможно и решение для станка возникнет.

Здравствуйте, McSeem2, Вы писали:

MS>Вот это очень существенный момент и с него надо было начинать.
MS>1) Можно ли включить одновременно оба мотора?

Нет, нельзя, в основном из за ответа на следущий вопрос

MS>2) Можно ли управлять скоростью моторов?

Нет, моторы шаговые, т.е. реагируют на смену 0 на 1 и никто не гарантируют, что реагировать два мотора будут одинаково, даже наоборот.

MS>3) Если можно, то с какими градациями?

см. ответы выше.

Расскажите, пожалуйста, что вы имели ввиду, сказав, что "можно объединять шаги"?

.

ShimoN wrote:
> Расскажите, пожалуйста, что вы имели ввиду, сказав, что "можно
> объединять шаги"?

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

Здравствуйте, ShimoN, Вы писали:

SN>Нет, моторы шаговые, т.е. реагируют на смену 0 на 1 и никто не гарантируют, что реагировать два мотора будут одинаково, даже наоборот.

Пожалуйста, подробнее — как они реагируют? Что конкретно происходит при смене 0/1 — мотор выполняет один шаг или запускается до тех пор, пока не выключат? Или мотор понимает команду типа "сделать 5 шагов"?

SN>Расскажите, пожалуйста, что вы имели ввиду, сказав, что "можно объединять шаги"?

10 шагов с dx=1 эквивалентны одному шагу с dx=10.

Здравствуйте, McSeem2, Вы писали:

MS>Пожалуйста, подробнее — как они реагируют? Что конкретно происходит при смене 0/1 — мотор выполняет один шаг или запускается до тех пор, пока не выключат? Или мотор понимает команду типа "сделать 5 шагов"?

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

Кстати, предвижу следущий вопрос, двигатели на то и шаговые,что гарантируют только одинаковый "размер" шага. Кстати, вы еще можете спросить, почему бы не брать тогда и попиксельно, переводя в шаги, не рисовать. Я отвечу: У двигателей есть люфт, он достаточно велик (по отношению к количеству шагов) так что чем реже придется останавливать\возобновлять движение — тем лучше — от того и вопрос возник. А то я мог бы просто вычислять черные пиксели и отрисовывать их на заготовке.

Надеюсь теперь я достаточно хорошо объяснил задачу и проблему...

Здравствуйте, ShimoN, Вы писали:

SN>При смене нуля на еденицу двигатель выполняет один шаг. У меня есть возможность вычислить сколько надо сделать шагов, чтобы пройти расстояние в один пиксель. (просто я могу посчитать количество шагов, которые нужно сделать,чтобы добраться от конца до конца и поделить их на размер области для рисования)

SN>Кстати, предвижу следущий вопрос, двигатели на то и шаговые,что гарантируют только одинаковый "размер" шага. Кстати, вы еще можете спросить, почему бы не брать тогда и попиксельно, переводя в шаги, не рисовать. Я отвечу: У двигателей есть люфт, он достаточно велик (по отношению к количеству шагов) так что чем реже придется останавливать\возобновлять движение — тем лучше — от того и вопрос возник. А то я мог бы просто вычислять черные пиксели и отрисовывать их на заготовке.

SN>Надеюсь теперь я достаточно хорошо объяснил задачу и проблему...

Честно сказать, не очень. Извиняюсь за назойливость, что происходит при смене с 1 на 0?
Из первого абзаца следует, что двигатель действительно шаговый, значит все, что он может, это повернуться на один шаг вперед или назад. Потом еще на один. И т.д. Но после каждого шага он все равно останавливается (так работает, например, привод магнитной головки во флопповоде). Но из второго абзаца — "чем реже придется останавливать\возобновлять движение — тем лучше" следует, что двигатель может вращаться непрерывно, с некой фиксированной скоростью. Но тогда он уже не шаговый. Ну или он может выполнять N шагов в единицу времени. Значит двигателю все-таки можно дать команду — сдвинуться на N шагов? Или нельзя? И каждый шаг надо инициировать отдельным импульсом?

Что же касается люфта, то это как правило важно только при смене направления вращения. Бороться с этим тяжело — надо при каждой смене направления давать некое дополнительное число обратных импульсов, чтобы "выбрать люфт". А вот сколько конкретно — зависит от точного значения этого люфта. А определить это точное значение может быть нетривиальной задачей. Более того — оно меняется со временем в результате механического износа.
Так же, наличие люфта может иметь неприятные последствия, если между шагами проходит значительный интервал времени, в течение которого из за вибраций подающий механизм может отъехать дальше. Но здесь уже ничего не поделаешь — при "рисовании" верхней части окружности (очень плоская часть) шаги по Y становятся весьма редкими.

Здравствуйте, McSeem2, Вы писали:

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

Да, так оно и есть.

MS>Но из второго абзаца — "чем реже придется останавливать\возобновлять движение — тем лучше" следует, что двигатель может вращаться непрерывно, с некой фиксированной скоростью. Но тогда он уже не шаговый. Ну или он может выполнять N шагов в единицу времени. Значит двигателю все-таки можно дать команду — сдвинуться на N шагов? Или нельзя? И каждый шаг надо инициировать отдельным импульсом?

Выполнять N шагов в единицу времени он может только если я за это количество времени с одинаковым интервалом сменю 1 на 0. Именно так я и собирался продвигать двигатель, но ко времени привязываться не собирался, двигатели то с разными характеристиками (кроме шага). НО! Вы, скорее всего, правы, моя фраза про "реже — лучше" не совсем правильна. Но все же, вы согласитесь со мной, что чем реже я буду останавливать одну ось и подключать другую — тем медленнее будет происходить "отрисовка".

MS>Что же касается люфта, то это как правило важно только при смене направления вращения. Бороться с этим тяжело — надо при каждой смене направления давать некое дополнительное число обратных импульсов, чтобы "выбрать люфт". А вот сколько конкретно — зависит от точного значения этого люфта. А определить это точное значение может быть нетривиальной задачей. Более того — оно меняется со временем в результате механического износа.
MS>Так же, наличие люфта может иметь неприятные последствия, если между шагами проходит значительный интервал времени, в течение которого из за вибраций подающий механизм может отъехать дальше. Но здесь уже ничего не поделаешь — при "рисовании" верхней части окружности (очень плоская часть) шаги по Y становятся весьма редкими.

Вы простите, но мы ушли от темы. Как же с рисованием дуги в данных условиях?

Здравствуйте, ShimoN, Вы писали:

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

Если принять один пиксел == один шаг, то все получается. Если для каждого шага требуется отдельный импульс, то классический алгоритм Брезенхема здесь вполне работает. Если же двигателю можно сказать "сделай N шагов", то мы просто накапливаем одинаковые шаги в программе, а потом выдаем одной командой. Если двигатели по X и Y нельзя использовать одновременно, то мы должны исключить из алгоритма диагональные шаги и анализировать только два пробных случая — (X+dx,Y) и (X,Y+dy), где dx,dy = +1 или -1, в зависимости от текущего направления.

Такой вопрос — а как выполняется движение по прямой под углом ровно в 45 градусов? Поочередными шагами по X и Y?

Здравствуйте, McSeem2, Вы писали:

MS>Если принять один пиксел == один шаг, то все получается. Если для каждого шага требуется отдельный импульс, то классический алгоритм Брезенхема здесь вполне работает. Если же двигателю можно сказать "сделай N шагов", то мы просто накапливаем одинаковые шаги в программе, а потом выдаем одной командой. Если двигатели по X и Y нельзя использовать одновременно, то мы должны исключить из алгоритма диагональные шаги и анализировать только два пробных случая — (X+dx,Y) и (X,Y+dy), где dx,dy = +1 или -1, в зависимости от текущего направления.

Хм, а не могли бы вы мне в двух словах объяснить суть кода написанного в качестве примера этого алгоритма и как его применить, учитывая, что мне надо нарисовать дугу, причем не отрывая фрезы?

MS>Такой вопрос — а как выполняется движение по прямой под углом ровно в 45 градусов? Поочередными шагами по X и Y?

Да, именно так. И под любым другим тоже.

Здравствуйте, ShimoN, Вы писали:

SN>Выполнять N шагов в единицу времени он может только если я за это количество времени с одинаковым интервалом сменю 1 на 0. Именно так я и собирался продвигать двигатель, но ко времени привязываться не собирался, двигатели то с разными характеристиками (кроме шага). НО! Вы, скорее всего, правы, моя фраза про "реже — лучше" не совсем правильна. Но все же, вы согласитесь со мной, что чем реже я буду останавливать одну ось и подключать другую — тем медленнее будет происходить "отрисовка".

Алгоритм Брехенхема как раз и дает минимально возможное количество смен осей. Ага, кажется я начинаю понимать. Нам не важна супер-точность, мы можем ей пожертвовать, двигая оси по 10 шагов напрмер, так? Ну тогда все просто — рисуем окружность тем же Брезенхемом, но в 10 раз меньшего диаметра, а на каждый шаг алгоритма даем 10 импульсов. Нам даже не требуется ничего программно объединять — оно само объединится. Просто если текущий шаг по X или Y равен 0, то мы ничего и не включаем.

Здравствуйте, McSeem2, Вы писали:

MS>Алгоритм Брехенхема как раз и дает минимально возможное количество смен осей. Ага, кажется я начинаю понимать. Нам не важна супер-точность, мы можем ей пожертвовать, двигая оси по 10 шагов напрмер, так? Ну тогда все просто — рисуем окружность тем же Брезенхемом, но в 10 раз меньшего диаметра, а на каждый шаг алгоритма даем 10 импульсов. Нам даже не требуется ничего программно объединять — оно само объединится. Просто если текущий шаг по X или Y равен 0, то мы ничего и не включаем.

ГЕНИАЛЬНО!!! Эта идея мне очень понравилась, понять бы теперь алгоритм...

Здравствуйте, ShimoN, Вы писали:

SN>Хм, а не могли бы вы мне в двух словах объяснить суть кода написанного в качестве примера этого алгоритма и как его применить, учитывая, что мне надо нарисовать дугу, причем не отрывая фрезы?

//================================================== 
#include <stdio.h> 
#include <string.h> 


static char test_array[50][79]; 


inline void put_pixel(int x, int y) 
{ 
    test_array[y][x] = 'X'; 



} 


inline void put_step_four_pixels(int center_x, int center_y, int x, int y) 
{ 
   put_pixel(center_x + x, center_y + y); 
   put_pixel(center_x + x, center_y - y); 
   put_pixel(center_x - x, center_y - y); 
   put_pixel(center_x - x, center_y + y); 


} 


//Rendering an ellipse - a modified Brezenham algorithm 
//Copyright (C) 1997 Maxim Shemanarev 
void render_ellipse(int center_x, int center_y, int radius_x, int radius_y) 
{ 
    if(!(radius_x | radius_y)) 
    { 
        put_pixel(center_x, center_y); 
        return; 
    } 

    int  rx2 = radius_x * radius_x; 
    int  ry2 = radius_y * radius_y; 
    int  two_rx2 = rx2 << 1; 
    int  two_ry2 = ry2 << 1; 
    int  cur_x  = 0; 
    int  cur_y  = radius_y; 
    int  inc_x  =  cur_x * two_ry2; 
    int  inc_y  = -cur_y * two_rx2; 
    bool flag; 
    int  mx, my, mxy, min_m; 
    int  fx, fy, fxy, cur_f; 


    cur_f = 0; 
    while(cur_y >= 0) 
    { 
        put_step_four_pixels(center_x, center_y, cur_x, cur_y); 


        //One ellipse step 
        mx = fx = cur_f + inc_x + ry2; 
        if(mx < 0) mx = -mx; 


        my = fy = cur_f + inc_y + rx2; 
        if(my < 0) my = -my; 


//        mxy = fxy = cur_f + inc_x + ry2 + inc_y + rx2; 
//        if(mxy < 0) mxy = -mxy; 


        min_m = mx; 
        flag = true; 


        if(min_m > my)   
        { 
            min_m = my; 
            flag = false; 
        } 


//        if(min_m > mxy) 
//        { 
//            flag = false; 
//            cur_x++; 
//            inc_x += two_ry2; 
//            cur_y--; 
//            inc_y += two_rx2; 
//            cur_f = fxy; 
//            continue; 
//        } 


        if(flag) 
        { 
            cur_x++; 
            inc_x += two_ry2; 
            cur_f = fx; 
            continue; 
        } 
        cur_y--; 
        inc_y += two_rx2; 
        cur_f = fy; 
    } 



} 


int main() 
{ 
    memset(test_array, '.', sizeof(test_array)); 

    render_ellipse(39, 25, 0,  0); 
    render_ellipse(39, 25, 38, 23); 
    render_ellipse(39, 25, 35, 20); 
    render_ellipse(39, 25, 30, 15); 
    render_ellipse(39, 25, 25, 10); 
    render_ellipse(39, 25, 20, 5); 


    unsigned i, j; 
    for(i = 0; i < 50; i++) 
    { 
        for(j = 0; j < 79; j++) 
        { 
            putc(test_array[i][j], stdout); 
        } 
        putc('\n', stdout); 
    } 
    return 0; 
}

Здесь рисуется вторая четверть эллипса против часовой стрелки, начиная с точки (0,R). Я закоментировал код, обрабатывающий диагональные шаги. Ну а для произвльной дуги надо посчитать первую точку, определить начальные dx,dy (вместо cur_x++ надо использовать cur_x += dx) и при пересечении осей корректировать dx,dy и inc_x, inc_y (менять знаки).

Вообще-то, можно значительно упростить, если не использовать прямые умножения (один шаг):

fdx = abs((X+dx)*(X+dx) + Y*Y - R*R);
fdy = abs(X*X + (Y+dy)*(Y+dy) - R*R);

if(fdx < fdy)
{
   X += dx;
}
else
{
   Y += dy;
}

fdx, fdy — это квадрат расстояния между нашей точкой и окружностью. Чем это значение меньше, тем ближе точка к окружности.

Ну а значения dx,dy — в первом квадранте -1,1, во втором — -1,-1, в третьем — 1,-1, в четвертом — 1,1. Они меняются при смене знаков X,Y (ву предположении, что окружность рисуется из центра координат).

Начальные X,Y вычисляются как R*cos(a), R*sin(a). Самая трудная часть — определить, когда надо останавливаться. Можно тупо считать угол на каждом шаге и сравнивать с конечным углом. Но насколько я помню, при целочисленных вычислениях вполне надежно работает проверка на попадание в нужную конечную точку. Мы точно так же считем конечную точку на оружности и крутим до тех пор, пока наша X,Y не встретится с этой точкой.

Вот еще есть, возможно даже более понятно:
http://antigrain.com/__code/include/agg_ellipse_bresenham.h.html

Здравствуйте, McSeem2:

Огромное вам спасибо за помощь! Теперь буду разбираться!!!