Optimize trigonometric calculations?

[Andreas]

Hi,

I was debating if I should be posting this in the drawing newsgroup but
finally decided that it wasn't drawing related (even if that's what I'm
ultimatly doing) but instead optimization / math. In a sense it's not
c-sharp specific either but I hope someone can share some suggestions. So
what I'm doing can be viewed as graphis a graph (Vertex and Edges).

I have a series of points drawn on a bitmap and some of them should be
connected with a line. That itself is no problem, it would be a basic
DrawLine call. However what I need to do is to have the line not start/end
in the center of each point but instead at a certain distance from it, i.e
having a sort of safe radius around each point

So instead of this (sorry for the poor ascii)

*----*

I want this

* ---- *

Now please note that this would not be a problem is all points where lined
up on the horizontal and vertical axis but they are not, meaning that I will
be drawing diagonale lines. So what I came up with was some basic
trigonomety to calculate where the line coordinates are. My problem is
performance and the need to optimize. I have about 5000 points and they are
all connected in a web. I have a need to redraw this when ever scrolling
occures (yeah I only redraw the things that are visible in my viewing pane)
and performance is a bit slow

So is there any math-tricks / optimizations anyone could recommend to do the
same? Below is the code I use to calculate and draw the line. For the sake
of the argument, assume I cannot cache the calculation after the first time
it's been drawn and have a need to run it each time

int safeRadius = 7;

Point p1 = new Point(x1, y1);
Point p2 = new Point(x2, y2);

double angleX = Math.Abs(p2.X - p1.X);
if (angleX == 0)
angleX = 1;

double angleY = Math.Abs(p2.Y - p1.Y);
if (angleY == 0)
angleY = 1;

double angle1 = Math.Atan(angleY / angleX);

int xoff = (int)Math.Cos(angle1) * safeRadius;
if (p1.X > p2.X)
xoff = -xoff;

double yoff = Math.Sin(angle1) * safeRadius;
if (p1.Y > p2.Y)
yoff = -yoff;

gfx.DrawLine(p, p1.X + xoff, p1.Y + yoff, p2.X - xoff, p2.Y - yoff);

 

[Marc Gravell]

Do you even need trig here? I haven't run through all the logic, but I'm
wondering if you can't simply multiply by the y/x quotient? I'd need a scrap
of paper to check it, admittedly...

For the cos/sin - how accurate does it need to be? Would the trick of an
array of pre-calculated values work? (picking your scale accordingly) - for
instance, with degrees (which is very rare in reality) you might choose a
double[360] and round to the nearest degree... obviously with radians you
would choose some suitable factor, multiple and round etc...

Marc

 

[Marc Gravell]

Just checking my math... the atan is the nuicance - perhaps needed after
all. Unfortunately this is likely to be the most expensive operation...

But you can reduce some of the math - since (Y,X = full offsets, y,x =
scaled)

tan(angle) = Y/X= y/x
=> y=xY/X
So you can remove of of the sin/cos, and pehaps use the lookup for the other
(so only one lookup table - suggest "sin" is easier as easy to scale for
0-90 [or 0-Pi/4]

That just leaves the atan...

Marc

 

[Andreas]

A resonable approximation should be ok.. I'm trying out some stuff atm.
Will report back if I get something worked out. I could cheat by just going

endPoint1 = new Point(p1.X+safeRadius, p1.Y+safeRadius)
endPoitn2 = ...

it wont give me the EXACT position as it would do with trig but I think it's
an ok trade-off in this case

 

[tony lock]

Hi,

I was debating if I should be posting this in the drawing newsgroup but
finally decided that it wasn't drawing related (even if that's what I'm
ultimatly doing) but instead optimization / math. In a sense it's not
c-sharp specific either but I hope someone can share some suggestions. So
what I'm doing can be viewed as graphis a graph (Vertex and Edges).

I have a series of points drawn on a bitmap and some of them should be
connected with a line. That itself is no problem, it would be a basic
DrawLine call. However what I need to do is to have the line not start/end
in the center of each point but instead at a certain distance from it, i.e
having a sort of safe radius around each point

So instead of this (sorry for the poor ascii)

*----*

I want this

* ---- *

Now please note that this would not be a problem is all points where lined
up on the horizontal and vertical axis but they are not, meaning that I will
be drawing diagonale lines. So what I came up with was some basic
trigonomety to calculate where the line coordinates are. My problem is
performance and the need to optimize. I have about 5000 points and they are
all connected in a web. I have a need to redraw this when ever scrolling
occures (yeah I only redraw the things that are visible in my viewing pane)
and performance is a bit slow

So is there any math-tricks / optimizations anyone could recommend to do the
same? Below is the code I use to calculate and draw the line. For the sake
of the argument, assume I cannot cache the calculation after the first time
it's been drawn and have a need to run it each time

int safeRadius = 7;

Point p1 = new Point(x1, y1);
Point p2 = new Point(x2, y2);

double angleX = Math.Abs(p2.X - p1.X);
if (angleX == 0)
angleX = 1;

double angleY = Math.Abs(p2.Y - p1.Y);
if (angleY == 0)
angleY = 1;

double angle1 = Math.Atan(angleY / angleX);

int xoff = (int)Math.Cos(angle1) * safeRadius;
if (p1.X > p2.X)
xoff = -xoff;

double yoff = Math.Sin(angle1) * safeRadius;
if (p1.Y > p2.Y)
yoff = -yoff;

gfx.DrawLine(p, p1.X + xoff, p1.Y + yoff, p2.X - xoff, p2.Y - yoff);

Wil not Pythagoras give you what you want

int safeRadius = 7;

Point p1 = new Point(x1, y1);
Point p2 = new Point(x2, y2);

double angleX = Math.Abs(p2.X - p1.X);
double angleY = Math.Abs(p2.Y - p1.Y);

double hypot = Math.Sqr(angleX*angleX + angleY*angleY)

int xoff = (int)safeRadius * angleX / hypot
int yoff = (int)safeRadius * angleY / hypot

gfx.DrawLine(p, p1.X + xoff, p1.Y + yoff, p2.X - xoff, p2.Y - yoff);

Tony

 

[tony lock]

Sorry should have been

int xoff = (int)(safeRadius * angleX / hypot)
int yoff = (int)(safeRadius * angleY / hypot)


Tony

 

[tony lock]

Also should be

double angleX = p2.X - p1.X
double angleY = p2.Y - p1.Y

Tony

 

[Andreas]

You know... this is what I wanted to do but I ended up taking the long
route.. =/
Thank you

 

[Fred Mellender]

The slope of the line: m = dy/dx = (p2.y-p1.y)/(p2.x-p1.x).
If p1 and p2 have the same x coord, then the line is vertical which you
handle as an easy special case.

then:
newPt.x = p1.x + safeRadius, and newPt.y = p1.y + safeRadius*m.

The actual distance between the newPt and p1 is not safeRadius, but only
approximately so (=safeR*sqrt(1+m^2)). However, the newPt is on the line.

 

[Fred Mellender]

More exactly:

The slope of the line: m = dy/dx = (p2.y-p1.y)/(p2.x-p1.x).
If p1 and p2 have the same x coord, then the line is vertical which you
handle as an easy special case.

then:
safeRad^2 = ndy^2 + ndx^2, so that ndx = safeRad/sqrt(m^2+1) and
ndy = m*safeRadius/sqrt(1+m^2);

Thus newPt = (x1+ndx, y1+ndy).

 

[Ben Voigt [C++ MVP]]

Hi,

I was debating if I should be posting this in the drawing newsgroup
but finally decided that it wasn't drawing related (even if that's
what I'm ultimatly doing) but instead optimization / math. In a sense
it's not c-sharp specific either but I hope someone can share some
suggestions. So what I'm doing can be viewed as graphis a graph
(Vertex and Edges).
I have a series of points drawn on a bitmap and some of them should be
connected with a line. That itself is no problem, it would be a basic
DrawLine call. However what I need to do is to have the line not
start/end in the center of each point but instead at a certain
distance from it, i.e having a sort of safe radius around each point

And now for something completely different (Using ratios instead of calling
the trig functions is already a very good optimization):

You could always draw the lines, endpoint to endpoint, then draw white
circles over each point. This may or may not be faster than adjusting the
lines.

 

[Martin Bonner]

Hi,

I was debating if I should be posting this in the drawing newsgroup but
finally decided that it wasn't drawing related (even if that's what I'm
ultimatly doing) but instead optimization / math. In a sense it's not
c-sharp specific either but I hope someone can share some suggestions. So
what I'm doing can be viewed as graphis a graph (Vertex and Edges).

I have a series of points drawn on a bitmap and some of them should be
connected with a line. That itself is no problem, it would be a basic
DrawLine call. However what I need to do is to have the line not start/end
in the center of each point but instead at a certain distance from it, i.e
having a sort of safe radius around each point

So instead of this (sorry for the poor ascii)

*----*

I want this

* ---- *

Now please note that this would not be a problem is all points where lined
up on the horizontal and vertical axis but they are not, meaning that I will
be drawing diagonale lines. So what I came up with was some basic
trigonomety to calculate where the line coordinates are. My problem is
performance and the need to optimize. I have about 5000 points and they are
all connected in a web. I have a need to redraw this when ever scrolling
occures (yeah I only redraw the things that are visible in my viewing pane)
and performance is a bit slow

So is there any math-tricks / optimizations anyone could recommend to do the
same? Below is the code I use to calculate and draw the line. For the sake
of the argument, assume I cannot cache the calculation after the first time
it's been drawn and have a need to run it each time

int safeRadius = 7;

Point p1 = new Point(x1, y1);
Point p2 = new Point(x2, y2);

double angleX = Math.Abs(p2.X - p1.X);
if (angleX == 0)
angleX = 1;

double angleY = Math.Abs(p2.Y - p1.Y);
if (angleY == 0)
angleY = 1;

deltaX, deltaY would be better names here.

double angle1 = Math.Atan(angleY / angleX);

You almost NEVER want to use Math.Atan. a) It only gives you an angle
in the range -90..90 degrees; b) it won't like deltaX == 0 (yes, I
know you kludge round that above).

Instead use Math.Atan2 which a) gets you an angle in the full circle;
b) only has problems if /both/ it's arguments are zero.

However, read on:

int xoff = (int)Math.Cos(angle1) * safeRadius;

You rarely want to use Cos(angle). Instead remember that the dot
product of two vectors is the product of their lengths and the cosine
of the angle.

Just calculate the unit vector in the direction p1->p2, and then
calculate the dot product of that with a unit vector along the X-axis.

if (p1.X > p2.X)
xoff = -xoff;

double yoff = Math.Sin(angle1) * safeRadius;

Sin(angle) can be done in two ways: It is either the length of the
cross product vector, OR you can just calculate the cosine of the
complementary angle (90-angle). In this case, the latter is easier;
just calculate the dot product with a unit vector along the Y-axis.

if (p1.Y > p2.Y)
yoff = -yoff;

gfx.DrawLine(p, p1.X + xoff, p1.Y + yoff, p2.X - xoff, p2.Y - yoff);

So. Code looks like:

void DrawShortenedLine( Pen pen, Point p1, Point p2, int safeRadius )
{
// Calculate the delta's etc in double.
// It makes handling rounding *so* much simpler.
double deltaX = p2.X - p1.X; // Do this in double
double deltaY = p2.Y - p2.Y;
double hypot = Math.Sqrt( deltaX*deltaX + deltaY*deltaY );
if (hypot <= safeRadius*2)
{
return; // Nothing to do
}

deltaX /= hypot;
deltaY /= hypot;

// deltaX/Y now represents a unit vector from p1 to p2.

int xoff = (int)Math.Round( deltaX*safeRadius );
int yoff = (int)Math.Round( deltaY*safeRadius );

this.gfx.DrawLine(pen, p1.X + xoff, p1.Y + yoff, p2.X - xoff, p2.Y
- yoff);
}


(Note. At some loss of clarity, one can use integer deltaX/deltaY/
hypot and write

xOff = (deltaX*safeRadius + Math.Sign(deltaX)*(hypot/2)) / hypot;

One would have to profile to see if this was faster or not.)

 

[Andreas]

Actually I did that first but then the drawing evolved to have underlaying
graphics which got erased when I drew the circles, so I needed a way of
getting the same effect. Tony Lock helped me come to my senses, I was
overlooking the most basic mathmatical solution