Algoritme for doubling a line

howdy !
i'm working on a program with VC++ 6.0, a part of it consits of importing a BMP file that contains in it a drawing of a non closed line or curve.

In that file i've already set the background color to Black and the curve color to Green so that my program can locate easily the green pixels of the curve then buffering them in the desired order.

please take a look at the picture bellow.

well this is a simple of the result i want to get .

actualy i want to double the green line by drawin two parallel red lines that follow the green one !

but !!
as you can see thoes lines arn't a duplicate of the green one !

the external red line gets more pixels than the internal one, obviousely cause they don't use the same angle when the green line changes direction!

i managed to make programe tha can do this operation for horizontal and vertical line, as well for curves with 45 Dergrees rotation angle, but i fount it a bit hard to automate the procedure for the other angles.

i don't know if there is a mathematical function that can do this easily or i have to figure out one :sick:


please...a litle help here would be verry apreciated ! :)

i need just head lines

thanks in advance :)

:eek:
well.... after 24 Hours and no still answer yet !
i understand why i couldn't solve it !

I suggest that you post the question over in the forum for "Algorithms & Data Structures ": http://forums.codeguru.com/forumdisplay.php?f=65

In the meantime, one suggestion is to modify the "marching square" algorithm so that instead of painting a pixel at the edge of a shape, it paints a pixel at an offset from the edge of the shape. See "Detecting edge pixels with Marching Squares Algorithm
" at http://www.sakri.net/blog/2009/05/28...res-algorithm/

Lets say you have defined your first line with x and y coordinates as its 2D

possibilty to dublicate the line

pseudo code

Code:

---

vector<2DARRAY> iterator;
vector<2DARRAY> vertices;

for(iterator = vertices.begin();iterator<= vertices.end; iterator++)
{

Drawfirst line from vertices vector... which is middle line say.

then for every x and y coordinate + X units from current vertices in the vector to produce the same line but moved over.
}

---

Quote:

---

Originally Posted by gaar321

Lets say you have defined your first line with x and y coordinates as its 2D

---

He doesn't have XY coordinates of his line. As stated in his OP, he has a bitmap, with a green line on a black background.

Quote:

---

Originally Posted by gaar321

possibilty to dublicate the line

pseudo code

Code:

---

vector<2DARRAY> iterator;
vector<2DARRAY> vertices;

for(iterator = vertices.begin();iterator<= vertices.end; iterator++)
{

Drawfirst line from vertices vector... which is middle line say.

then for every x and y coordinate + X units from current vertices in the vector to produce the same line but moved over.
}

---

---

This won't work since it always offsets the line in the X-direction (i.e., horizontally). For example, for a horizontal line, the offset would be drawn directly on top of the original line, and there would be no visible offset.

The challenge at each point along the original line is to draw a point at a fixed distance away, in the direction of the perpendicular to the line (sometimes called the "normal" to the line). If there were XY coordinates for each point of the original line, it might be possbile to calculate an approximation to the perpendicular direction, and then draw a new point at a fixed offset in that direction. But there aren't any XY coordinates, so the problem must be solved graphically.

Why not load the bitmap then get its area and then get the amount of pixels the bitmap covers. set some offsets then get some x and y coordinates.

Quote:

---

Originally Posted by MikeAThon

I suggest that you post the question over in the forum for "Algorithms & Data Structures ": http://forums.codeguru.com/forumdisplay.php?f=65

In the meantime, one suggestion is to modify the "marching square" algorithm so that instead of painting a pixel at the edge of a shape, it paints a pixel at an offset from the edge of the shape. See "Detecting edge pixels with Marching Squares Algorithm
" at http://www.sakri.net/blog/2009/05/28...res-algorithm/

---

Didn't open the link :L

well....looks like i missed the action here :)
first of all, thanks for your answers and suggestions.
ok let's see.....

Quote:

---

Originally Posted by MikeAThon

He doesn't have XY coordinates of his line. As stated in his OP, he has a bitmap, with a green line on a black background.


This won't work since it always offsets the line in the X-direction (i.e., horizontally). For example, for a horizontal line, the offset would be drawn directly on top of the original line, and there would be no visible offset.
................................................................................................................
.......... If there were XY coordinates for each point of the original line, it might be possbile to calculate an approximation to the perpendicular direction, and then draw a new point at a fixed offset in that direction. But there aren't any XY coordinates, so the problem must be solved graphically.

---

As i said getting Xs and Ys for each pixel of my green line make part of my program, and basing on it i managed to made my first version that can offset only , horizontal, vertivcal and 45 degrees lines.

Quote:

---

Originally Posted by MikeAThon

The challenge at each point along the original line is to draw a point at a fixed distance away, in the direction of the perpendicular to the line (sometimes called the "normal" to the line).

---

Exactly !!!! that's what i'm seeking !


since my first message i've been googling with some key words, and sudently i found this : An offset algorithm for polyline curves

and it explains what i'm exactly looking for, but :sick:........it layes on serious math formulas



so improvised again and tried to make a heading CAP for each pixel while scaning and following the green line but it returns funny results, an the problem is due to that pixels in a curve don't turn, but are positioned like the staires, so with a zoom-out it gave us the impression of the curve, so at final , they still horizontal and vertical lines, even within the curve !
i'me sure that there is a solution if we use trigonomitric functions as Sin or Cos, acctualy i'm digging deep in my search and i'm pritty close to something,...once sure i'll share it with you guys !

otherwise every one are welcome to add their suggestions.

and for the link Mr . gaar321 , looks interesting, i'll study it and give you my report later ;)

thanks again guys for the help ! :)

Well, if you have the XY coordiantes of the curve, and the coordiantes are relatively smooth, then it's not too hard to generate something like the first image below.

However, the algorithm does not work well on complex curves, or on curves with sharp vertices, as shown in the second image below.

Quote:

---

Originally Posted by bimo

since my first message i've been googling with some key words, and sudently i found this : An offset algorithm for polyline curves

and it explains what i'm exactly looking for ...

---

The link you gave doesn't work, but I think you mean this: "An offset algorithm for polyline curves" at http://hal.inria.fr/docs/00/51/80/05...ngLiu2007a.pdf

The algorithm in that paper seems to work very well, even on complex curves with sharp vertices. But it's complex, as you point out.

On the other hand, the algorithm used to generate the images below is simple. Let me know if the results shown in the attached image are good enough.

thanks Mr. MikeAThon for your answer !
the results in the pictures you drew looks verry interresting.
you said that the Algorithm that can generate it is very easy..
how so ?...
(well exuse me...i'm not questioning your inteligence :) )
i just want you to explain how this algorithm works please !

thanks in advance !

The algorithm for these images was easy. For each point P0 on the curve, do the following:

1. estimate the derivative of the curve at P0
2. calculate the direction perpendicular to the derivative and normalize it
3. derive XY coordinates of a point Pd displaced from P0 by a distance d in the perpendicular direction

For the above images, the estimate of derivative was obtained using the forward difference from the next point P1 on the curve. If the direction in equation form is written algebraically as a vector <a,b>, then the perpendicular direction is <b,-a> and normalization is sqrt(a^2+b^2). The displaced point Pd is simple, given the distance d.

I used Excel to generate the above images, so I do not have C++ code. Here is sample (but untested) C++ code that you can try. It uses the fabs() and sqrt() functions, so you will need to #include math.h:

Code:

---

bool DeriveDisplacedPoint( double P0x, double P0y, double P1x, double P1y, double &Pdx, double &Pdy, double d)
{
        /*
        Function to calculate a displaced point Pd from a point P0 on an arbitrary curve
        For each point P0 on the curve, do the following:

        1. estimate the derivative of the curve at P0, using a forward difference from the next successive point P1 on the curve
        2. calculate the direction perpendicular to the derivative and normalize it
        3. derive XY coordinates of a point Pd displaced from P0 by a distance d in the perpendicular direction

        */

        double dx = P1x - P0x;
        double dy = P1y - P0y;
        double mag = sqrt( dx*dx + dy*dy );
        if ( fabs(mag) < 1.e-6 )  // 10^-6 is an arbitrary small value
        {
                // the magnitude is so small that P0 and P1 are either the same point or so close to the same point
                // that no meaningful information can be derived on the derivative

                return false;
        }

        // derive the perpendicular vector, and normalize it

        double nx = dy / mag;
        double ny = -dx / mag;

        // derive coordinates of the displaced point Pd

        Pdx = P0x + d*nx;
        Pdy = P0y + d*ny;
       
        return true;
}

---

The code is untested and uncompiled, so let us know if it needs tweaking.

The code returns false if it can't caluculate a meaningful derivative whose magnitude is large enough to avoid a divide-by-zero error. So you need to test the returned value of the function before you use the returned point Pd.

Mike

thanks again for the help :)

so....i took your code and pluged it in to my application
i work with Visual C++ 6.0 (old i know, but very efficiant :thumb:)
and i put your code behind a button

my pixels cordinates are stored in two vectors X[800] and Y[800].
i took the distance d = 10;

and by the way you didn't talk about P1, so i assumed that it represents the pixel after P0

so i took :
P0 = X[i] and P1 = X[i+1]


ofcourse i had to make some changes on the code and here is the transformed code :

Quote:

---

void CProjectDlg::OnButton7()
{
int d = 10;
double dx ;
double dy;
double mag;
double nx;
double ny;

CClientDC dc(this);

for(int i = 0 ; i < 800 ; i++ )
{

dx = X[i+1] - X[i]; //P1x - P0x;
dy = Y[i+1] - Y[i]; // P1y - P0y;
mag = sqrt( dx*dx + dy*dy );

/* if ( fabs(mag) < 1.e-6 ) // 10^-6 is an arbitrary small value
{
// the magnitude is so small that P0 and P1 are either the same point or so close to the same point
// that no meaningful information can be derived on the derivative

return false;
}*/

// derive the perpendicular vector, and normalize it

nx = dy / mag;
ny = -dx / mag;

// derive coordinates of the displaced point Pd

SetPixel(dc,(X[i] + d*nx),(Y[i] + d*ny),RGB(0,0,255));
//Pdx = P0x + d*nx;
//Pdy = P0y + d*ny;
}
}

---

when i executed my code i got the result on picture 1
and when i changed the Red Bold lines by this

dx = X[i];
dy = Y[i];

i got the result on picture 2

and as you can see, there is something wrong some where !

can you basing on theses result give me an explanation or indicate what i missed ?

thanks again !

NB : sorry if the pictures quality is poor, i was fast and forgot to save them as bmps
the original curve is the RED one and generated one is the Blue !

Picture #2 is completely wrong since it does not rely on the derivative. Throw it away.

Picture #1 is close except that you ran the algorithm only once, for +d. You need to run it a second time, for -d.

After that, you will see the same shortcomings that I mentioned before: good performance for simple curves, but poor performance around sharp vertices (e.g., the areas of your curve with right angles) and for complex curves.

Incidentally, there are two clear errors in your code. 1 - In your "for" loop, test your index i against "i < 799", or else X[i+1] will go past the end of the array. 2 - You commented out the test for divide-by-zero. This test must be included. To do so, un-comment the "if" statement and change "return false" to "continue".

Good luck.

Mike

PS: Yes, P1 is the next point in the array, but I didn't omit that explanation. In fact, my post mentions it twice.

thanks for the correction and sorry you are right you did mentioned P1 earlier
...my mistake :D

i inserted the magnitude test as an IF condition that controls the pixels drawing.

ok after many plastic surgery operations for my code i came to this :

Quote:

---

void CProjectDlg::OnButton7()
{
int d = 10;
double dx ;
double dy;
double mag;
double nx;
double ny;
CClientDC dc(this);



for(int i = 0 ; i < 799 ; i++ )
{
if ( fabs(mag) >= 1.e-6 ) // 10^-6 is an arbitrary small value
{
dx = X[i+1] - X[i];//P1x - P0x;
dy = Y[i+1] - Y[i];// P1y - P0y;
mag = sqrt( dx*dx + dy*dy );


// derive the perpendicular vector, and normalize it

nx = dy / mag;
ny = -dx / mag;

// derive coordinates of the displaced point Pd

SetPixel(dc,(X[i] + d*nx),(Y[i] + d*ny),RGB(0,255,0));


}
}


for( i = 0 ; i < 799 ; i++ )
{
if ( fabs(mag) >= 1.e-6 ) // 10^-6 is an arbitrary small value
{
dx = X[i+1] - X[i];//P1x - P0x;
dy = Y[i+1] - Y[i];// P1y - P0y;
mag = sqrt( dx*dx + dy*dy );


// derive the perpendicular vector, and normalize it

nx = -dy / mag;
ny = dx / mag;

// derive coordinates of the displaced point Pd

SetPixel(dc,(X[i] + d*nx),(Y[i] + d*ny),RGB(0,255,0));
//Pdx = P0x + d*nx;
//Pdy = P0y + d*ny;
}
}
}

---

and witch gave me this result (pictures bellow)

well we can call it a success, but still bothered by the discontinuity of the generated line on curves (look the zoomed picture)
what do you think is responsible of that ?
and what are thoes noisy pixels that doesn't make part of the generated curve ?!

thanks a lot for your help and time !

The discontinuities are caused by the shortcomings already mentioned: The algorithm simply does not work well on complex curves that include sharp vertices. If you need a better algorithm, then it will be much more complicated, such as in the article you found on ""An offset algorithm for polyline curves".

The noisy pixels are caused by the "staircase effect" that you already mentioned. Try pre-filtering the XY coordinates for the curve, so as to smooth it out a bit. Perhaps you could apply a simple moving average, such as over a 5-pixel width, as shown in the code below.

Mike

PS: Your test against divide-by-zero was in the wrong location. The code below corrects it. In addition, since you're using SetPixel as opposed to MoveTo/LineTo, the code below simplifies running of the algorithm twice (i.e., first for +d and the second for -d), and instead simply calls SetPixel twice, first for +d and second for -d.

Code:

---

void CProjectDlg::OnButton7()
{
        int d = 10;

        double dx ;
        double dy;
        double mag;
        double nx;
        double ny;
        double filteredX0, filteredY0;
        double filteredX1, filteredY1;

        CClientDC dc(this);

        for(int i = 2 ; i < 797 ; i++ )  // note: adjustment of i by +/- 2 to account for 5-pixel moving average
        {
                filteredX0 = ( (double)( X[i-2]+X[i-1]+X[i]+X[i+1]+X[i+2] ) )/5.;
                filteredY0 = ( (double)( Y[i-2]+Y[i-1]+Y[i]+Y[i+1]+Y[i+2] ) )/5.;

                filteredX1 = ( (double)( X[i-1]+X[i]+X[i+1]+X[i+2]+X[i+3] ) )/5.;
                filteredY1 = ( (double)( Y[i-1]+Y[i]+Y[i+1]+Y[i+2]+Y[i+3] ) )/5.;

                dx = filteredX1 - filteredX0;
                dy = filteredY1 - filteredY0;
               
                mag = sqrt( dx*dx + dy*dy );

                if ( fabs(mag) < 1.e-6 ) // 10^-6 is an arbitrary small value to prevent divide-by-zero
                {
                        continue;
                }

                // derive the perpendicular vector, and normalize it

                nx = dy / mag;
                ny = -dx / mag;

                // derive coordinates of the displaced point Pd, and draw it for +/- d

                SetPixel(dc,(X[i] + d*nx),(Y[i] + d*ny),RGB(0,255,0));
                SetPixel(dc,(X[i] - d*nx),(Y[i] - d*ny),RGB(0,255,0));

        }
       
}

---