Привет!
Я создаю графический редактор типа AutoCAD или Компас. И проблема возникла в штриховке. А именно в том, что нужен алгоритм, который бы позволял определять границы штрихуемого контура, а затем собственно заштризовывал контур проверяя на наличие в нем дырок и прочих тонкостей. Алгоритм заливки, который приведен в книге "Е.В. Шикин А.В. Боресков "Компьютерная графика Полигональные модели"" не подойдет поскольку в нет просто каждая точка в контуре зажигается нужным цветом. У меня же штриховка выполняется отрезками (в общем случае). т.е нужно расчитывать координаты начала и конца. Подскажите какую-нибудь книжку, статью где можно было бы найти информацию по этой проблеме

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

_MM>Привет!
_MM>Я создаю графический редактор типа AutoCAD или Компас. И проблема возникла в штриховке. А именно в том, что нужен алгоритм, который бы позволял определять границы штрихуемого контура, а затем собственно заштризовывал контур проверяя на наличие в нем дырок и прочих тонкостей. Алгоритм заливки, который приведен в книге "Е.В. Шикин А.В. Боресков "Компьютерная графика Полигональные модели"" не подойдет поскольку в нет просто каждая точка в контуре зажигается нужным цветом. У меня же штриховка выполняется отрезками (в общем случае). т.е нужно расчитывать координаты начала и конца. Подскажите какую-нибудь книжку, статью где можно было бы найти информацию по этой проблеме
Когда то давно я делал так — поворачивал фигуру на угол штриховки, а далее тривиально — определение точек пересечения контура с горизонтальной линией в цикле. Обратный поворот результирующего массива точек давал искомое.

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

_MM>Я создаю графический редактор типа AutoCAD или Компас. И проблема возникла в штриховке. А именно в том, что нужен алгоритм, который бы позволял определять границы штрихуемого контура, а затем собственно заштризовывал контур проверяя на наличие в нем дырок и прочих тонкостей.

Здесь может помочь GPC (General Polygon Clipping) by Alan Murta. http://www.cs.man.ac.uk/aig/staff/alan/software/

Общая идея — создаем много узких длинных прямоугольников, гарантированно покрыващих фигуру, а потом применяем операцию пересечения. Корректность результата гарантирована.
Ну а если не хочется таких сложностей, то надо пользоваться методом, предложенным migel — повернуть фигуру, чтобы штриховка была горизонтальной, результат штриховки повернуть обратно.

Привет

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

Лень рисовать, так бы нагляднее объяснил.

Если тебе нужна штриховка растра, то проще всего сделать так:

Алгоритм заливки
{
   const int step = 5;
   const int angleFactor = 1; // 45 градусов

   // something...

   if( точку нужно закрасить )
   {
       if( 0 == (x + (y/angleFactor)) % step )
       {
           drawDot( x, y );
       }
   }
}

step -- шаг штриховки
angleFactor -- определяет угол штриховки

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

Более гибкий вариант:

WM>

WM>Алгоритм заливки
WM>{
WM>   const int step = 5;
WM>   const int angleFactor1 = 1;
WM>   const int angleFactor2 = 1;

WM>   // something...

WM>   if( точку нужно закрасить )
WM>   {
WM>       if( 0 == (x + ((y*angleFactor1)/angleFactor2)) % step )
WM>       {
WM>           drawDot( x, y );
WM>       }
WM>   }
WM>}
WM>

Отношение angleFactor1/angleFactor2 -- тангенс (или котангенс, не помню) угла наклона.

Здравствуйте, defrag, Вы писали:
D>Есть идея. Сделать темплейт штриховки квадратным битмапом, таим,чтобы при соприкасновении сторон темплейта целостность штриховки сохранялась (можно небольшого размера). Условно заполняем все бесконечное пространство этими квадратиками.
D>Теперь применяем, упомянутый Вами алгоритм, только вместо нужного цвета берем цвет с соответственной точки темплейта. Таким образом можно штриховку любой сложности сделать.

Эта идея называется "паттерн" и задачу штриховки в растровом представлении, она в общем решает. Проблема в том, что иногда требуется все-таки чисто векторная штриховка. Например, для плоттера. Да даже и для принтера с 1600dpi — гораздо эффективнее "накормить" его векторными PostScript командами, чем растеризовать все самому, а потом гнать этот жирный битмап через всю сеть на принтер.

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

WM>Более гибкий вариант:
WM>[. . .]

WM>   if( точку нужно закрасить )

Вот в этой-то строке и заключается вся засада...

Это примерно так же, как сказать:

if (путь комивояжера оптимален)
{
  . . .
}

Чего тут думать?

WM>>Более гибкий вариант:
WM>>[. . .]
MS>

WM>>   if( точку нужно закрасить )
MS>

MS>Вот в этой-то строке и заключается вся засада...

MS>Это примерно так же, как сказать:
MS>

MS>if (путь комивояжера оптимален)
MS>{
MS>  . . .
MS>}
MS>

Может я не правильно понял, но сначала я подумал, он знает алгоритм заливки, а если это так, то в условии "if( точку нужно закрасить )" нет ничего непонятного.

Растровый алгоритм заливки (если точка принадлежит контуру, то установить ее цвет равный такому-то) явно не подойдет. Штриховка является, если так можно выразиться векторной. Она состоит из отрезков. Нужно вычислять начало и конец отрезка. Ну у размется отслеживать разные там дырки. Эту задачу в принципе можно решить воспользовшишь алгоритмом удаления невидимых ребер. (Там для каждого ребра делается то ли 6 то ли 8 тестов). Задача состоит еще и в том, чтобы правильно обойти контур. У меня есть штриховка ("естественный грунт") так вот он штрихует область находящюся на теле на раастоянии, например 5 см, от контура.

У меня имеется алгоритм векторной штриховки. По этому алгоритму была разработана программа. Работает без каких-либо проблем.

P.S. У меня есть еще много алгоритмов для CADа, готовые куски программ Если Вы дадите ссылку на описание своего CADа, то я, ознакомившись, смогу сообщить Вам, чем я смогу помочь Вам и на каких условиях.

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

_MM>Привет!
_MM>Я создаю графический редактор типа AutoCAD или Компас. И проблема возникла в штриховке. А именно в том, что нужен алгоритм, который бы позволял определять границы штрихуемого контура, а затем собственно заштризовывал контур проверяя на наличие в нем дырок и прочих тонкостей. Алгоритм заливки, который приведен в книге "Е.В. Шикин А.В. Боресков "Компьютерная графика Полигональные модели"" не подойдет поскольку в нет просто каждая точка в контуре зажигается нужным цветом. У меня же штриховка выполняется отрезками (в общем случае). т.е нужно расчитывать координаты начала и конца. Подскажите какую-нибудь книжку, статью где можно было бы найти информацию по этой проблеме


Примерно так?



СMyCurve curve ; // 2D контур
CLine c_line ; // неогр. линия
CFline f_line ; // fixed line
CPoints points ; // множество точек
CPoint p0,p1,p_check, old_p, get_p; // 2D point
double hatch_step = 1 ; // шаг штриховки
double hatch_angle = PI/4 ; // угол штриховки

Box (curve, p0, p1); // нахожу границы контура (прямоугольник, опред. двумя точками слева внизу, справа вверху)


p_check.x = p0.x — (p1.x — p0.x) ; // cтартовая точка штриховки должна лежать за пределами прямоугольника и пересекать всю плосокость box(a)
p_check.y = p0.y — (p1.y — p0.y) ;

while (p_check.y < p1.y + ((p1.y — p0.y)) ){

CreateСLine (p_check, hatch_angle, c_line ); // создаю бесконечную линию через точку p_check и под углом штриховки
if (Itersection(curve , c_line, points) ){// линия пересекается с 2D контуром
while (1){
if (i >= points.GetSize()) break;
get_p = points.GetAt(i) ;
if (i > 0 && !i%2 ){
CreateFLine(old_p, get_p, f_line); //создаю ограниченную линию штриховки
AddCADObject (f_line); // актуализирую СAD

}
old_p = get_p;
i ++;

}// while


}
p_check.x += hatch_step;
p_check.y += hatch_step;

}