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
please...a litle help here would be verry apreciated !
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.
}
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.
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.
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/
well....looks like i missed the action here
first of all, thanks for your answers and suggestions.
ok let's see.....
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.
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).
and it explains what i'm exactly looking for, but ........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
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.
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 !
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.
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 )
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 :
void CProjectDlg::OnButton7()
{
int d = 10;
double dx ;
double dy;
double mag;
double nx;
double ny;
/* 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
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.
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 ?!
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));
}
}
* The Best Reasons to Target Windows 8
Learn some of the best reasons why you should seriously consider bringing your Android mobile development expertise to bear on the Windows 8 platform.
Algoritme for doubling a line
Reply With Quote
Re: Algoritme for doubling a line
Re: Algoritme for doubling a line
Originally Posted by gaar321
)
