473,326 Members | 2,196 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

Slightly mathematical programming problem.

class Point
{
double x, y;

public:
Point(double x_, double y_) : x(x_), y(y_) { }

double get_x() const { return x; }

double get_y() const { return y; }

// returns an angle between 0 and 180 degrees
// pre: y is non-negative
double get_angle() const;
};

double Point::get_angle() const; // TODO: implement this!

// returns the point with greatest angle
// pre: all points have non-negative y-components and points is non-empty
Point find_max_angle(std::vector<Point> points)
{
Point max_point = points[0];
double max_angle = max_point.get_angle();

std::vector<Point>::size_type i;
for (i=1; i < points.size(); i++)
{
Point point = points[i];
double angle = point.get_angle();

if (angle > max_angle)
{
max_point = point;
max_angle = angle;
}
}

return max_point;
}

Not sure how to implement Point::get_angle. Clues anyone?
Jul 23 '05 #1
16 1248
I guess the angle you are trying to find is between X axis and a line
from the origin (0,0) to the point(x,y). Is that correct?

If so, the angle should be

atan(y/x)

or something like that. I dont remember my trigonometry well enough..

hth,
Raghu

Jul 23 '05 #2

You mean the slope made by the vector joining origin(0,0) and point p?
You can take atan(y/x) * 180 / PI, PI=>3.14159...

Jul 23 '05 #3
"Raghu Uppalli" <ra*********@yahoo.com> wrote in message
news:11**********************@g14g2000cwa.googlegr oups.com...
I guess the angle you are trying to find is between X axis and a line
from the origin (0,0) to the point(x,y). Is that correct?

If so, the angle should be

atan(y/x)

or something like that. I dont remember my trigonometry well enough..


I don't think that works. I need an angle between 0 and 180 degrees. You can
measure the angle in radians if you like but I thought degrees would be
clearer.
Jul 23 '05 #4
<ma**********@hotmail.com> wrote in message
news:11**********************@l41g2000cwc.googlegr oups.com...

You mean the slope made by the vector joining origin(0,0) and point p?
You can take atan(y/x) * 180 / PI, PI=>3.14159...


Wouldn't that give me an angle between -90 and 90 degrees? I need an angle
between 0 and 180 degrees.
Jul 23 '05 #5
> class Point
{
double x, y;

public:
Point(double x_, double y_) : x(x_), y(y_) { }

double get_x() const { return x; }

double get_y() const { return y; }

// returns an angle between 0 and 180 degrees
// pre: y is non-negative
double get_angle() const;
};

double Point::get_angle() const; // TODO: implement this!


You should do it this way:

double Point::get_angle() const {
const double PI=acos(-1);
double a=atan2(y, x);
return a*180/PI;
}

atan2 or similar is defined in most math libraries. I do not know if it is
standard C++.

Niels Dybdahl
Jul 23 '05 #6
"Niels Dybdahl" <nd*@fjern.detteesko-graphics.com> wrote in message
news:42*********************@news.dk.uu.net...

You should do it this way:

double Point::get_angle() const {
const double PI=acos(-1);
double a=atan2(y, x);
return a*180/PI;
}

atan2 or similar is defined in most math libraries. I do not know if it is
standard C++.


Hey thanks a bunch. This solves my problem perfectly. I am so grateful!
Jul 23 '05 #7

"Jason Heyes" <ja********@optusnet.com.au> wrote in message
news:42***********************@news.optusnet.com.a u...
"Niels Dybdahl" <nd*@fjern.detteesko-graphics.com> wrote in message
news:42*********************@news.dk.uu.net...

You should do it this way:

double Point::get_angle() const {
const double PI=acos(-1);
double a=atan2(y, x);
return a*180/PI;
}

atan2 or similar is defined in most math libraries. I do not know if it
is
standard C++.


Hey thanks a bunch. This solves my problem perfectly. I am so grateful!


And you might want to replace your function with the following which will
properly handle the case of an empty vector:

typedef std::vector<Point> tPts;

tPts::iterator find_max_angle( tPts& aPts )
{
return std::max_element( aPts.begin()
, aPts.end()
, boost::bind
( std::less<double>()
, boost::bind( &Point::get_angle, _1 )
, _2
)
);
}

You can replace boost::bind above, with std::bind1st and std::mem_fn_ref(?)
where appropriate. You may also consider creating an overload to take a
const tPts& with a tPts::const_iterator return type as well.

Jeff Flinn
Jul 23 '05 #8

"Jeff Flinn" <NO****@nowhere.com> wrote in message
news:d2**********@bluegill.adi.com...

"Jason Heyes" <ja********@optusnet.com.au> wrote in message
news:42***********************@news.optusnet.com.a u...
"Niels Dybdahl" <nd*@fjern.detteesko-graphics.com> wrote in message
news:42*********************@news.dk.uu.net...

You should do it this way:

double Point::get_angle() const {
const double PI=acos(-1);
double a=atan2(y, x);
return a*180/PI;
}

atan2 or similar is defined in most math libraries. I do not know if it
is
standard C++.

Hey thanks a bunch. This solves my problem perfectly. I am so grateful!


And you might want to replace your function with the following which will
properly handle the case of an empty vector:

typedef std::vector<Point> tPts;

tPts::iterator find_max_angle( tPts& aPts )
{
return std::max_element( aPts.begin()
, aPts.end()
, boost::bind
( std::less<double>()
, boost::bind( &Point::get_angle, _1 )
, _2


Oops: replace the previous line with:
, boost::bind( &Point::get_angle, _2 )
)
);
}

You can replace boost::bind above, with std::bind1st and
std::mem_fn_ref(?) where appropriate. You may also consider creating an
overload to take a const tPts& with a tPts::const_iterator return type as
well.


Other options are to use the non-predicate form of std::max_element with
boost's transform_iterator, or to provide and operator< for your Point
class.

Jeff Flinn
Jul 23 '05 #9
"Jeff Flinn" <NO****@nowhere.com> wrote in message
news:d2**********@bluegill.adi.com...
And you might want to replace your function with the following which will
properly handle the case of an empty vector:

typedef std::vector<Point> tPts;

tPts::iterator find_max_angle( tPts& aPts )
{
return std::max_element( aPts.begin()
, aPts.end()
, boost::bind
( std::less<double>()
, boost::bind( &Point::get_angle, _1 )
, _2


Oops: replace the previous line with:
, boost::bind( &Point::get_angle, _2 )


)
);
}

You can replace boost::bind above, with std::bind1st and
std::mem_fn_ref(?) where appropriate. You may also consider creating an
overload to take a const tPts& with a tPts::const_iterator return type as
well.


Other options are to use the non-predicate form of std::max_element with
boost's transform_iterator, or to provide and operator< for your Point
class.


Yes. I was going to ask for a briefer version of find_max_angle. You are one
step ahead of me. Since I would also like to use the original interface, I
will need this:

Point find_max_angle(std::vector<Point> points)
{
return *find_max_angle(points);
}

Everyone is happy!
Jul 23 '05 #10
Jason Heyes wrote:
"Jeff Flinn" <NO****@nowhere.com> wrote in message
news:d2**********@bluegill.adi.com...
And you might want to replace your function with the following
which will properly handle the case of an empty vector:

typedef std::vector<Point> tPts;

tPts::iterator find_max_angle( tPts& aPts )
{
return std::max_element( aPts.begin()
, aPts.end()
, boost::bind
( std::less<double>()
, boost::bind( &Point::get_angle, _1 )
, boost::bind( &Point::get_angle, _2 )
)
);
}


Yes. I was going to ask for a briefer version of find_max_angle. You
are one step ahead of me. Since I would also like to use the original
interface, I will need this:

Point find_max_angle(std::vector<Point> points)
{
return *find_max_angle(points);
}

Everyone is happy!


I don't think the above will compile due to overload ambiguity. In both
cases, a more explicit naming of the functions would be advised.

Except when points is empty. The at best you'll get an access violation, at
worst some problem in a totally unrelated area of the code that you'll spend
days trying to track down. You'll need to:

tPts::iterator lItr = find_max_angle(points);

if( lItr != points.end() )
{
return *lItr;
}
else
{
throw "points is empty";
}

Also, do you realize that the std::vector points is being copied?

Jeff Flinn
Jul 23 '05 #11
Jason Heyes wrote:

[ ... ]
double Point::get_angle() const; // TODO: implement this!


If you care much about efficiency, you may NOT want to implement this
as stated. I'd just compute the slopes instead of the actual angles --
this is basically a single division (y/x) so it's quite fast. You're
discarding most of the values anyway, so computing the actual angle
instead of the slope doesn't really gain you much.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Jul 23 '05 #12
In message <11**********************@f14g2000cwb.googlegroups .com>,
Jerry Coffin <jc*****@taeus.com> writes
Jason Heyes wrote:

[ ... ]
double Point::get_angle() const; // TODO: implement this!


If you care much about efficiency, you may NOT want to implement this
as stated. I'd just compute the slopes instead of the actual angles --
this is basically a single division (y/x) so it's quite fast. You're
discarding most of the values anyway, so computing the actual angle
instead of the slope doesn't really gain you much.


But look out for the pathological cases. When x is 0, y/x is undefined,
but atan2(y, x) is fine. (Unless y is also 0 !)

--
Richard Herring
Jul 23 '05 #13
"Jerry Coffin" <jc*****@taeus.com> wrote in message
news:11**********************@f14g2000cwb.googlegr oups.com...
Jason Heyes wrote:

[ ... ]
double Point::get_angle() const; // TODO: implement this!


If you care much about efficiency, you may NOT want to implement this
as stated. I'd just compute the slopes instead of the actual angles --
this is basically a single division (y/x) so it's quite fast. You're
discarding most of the values anyway, so computing the actual angle
instead of the slope doesn't really gain you much.


The slope is not enough. You need the signs of x and y and you must handle
pathological cases (i.e., when x = 0). In the end you do no better than
atan2 efficiency-wise.
Jul 23 '05 #14
"Jeff Flinn" <NO****@nowhere.com> wrote in message
news:d2**********@bluegill.adi.com...
Jason Heyes wrote:
"Jeff Flinn" <NO****@nowhere.com> wrote in message
news:d2**********@bluegill.adi.com...
And you might want to replace your function with the following
which will properly handle the case of an empty vector:

typedef std::vector<Point> tPts;

tPts::iterator find_max_angle( tPts& aPts )
{
return std::max_element( aPts.begin()
, aPts.end()
, boost::bind
( std::less<double>()
, boost::bind( &Point::get_angle, _1 )
, boost::bind( &Point::get_angle, _2 )
)
);
}
Yes. I was going to ask for a briefer version of find_max_angle. You
are one step ahead of me. Since I would also like to use the original
interface, I will need this:

Point find_max_angle(std::vector<Point> points)
{
return *find_max_angle(points);
}

Everyone is happy!


I don't think the above will compile due to overload ambiguity. In both
cases, a more explicit naming of the functions would be advised.


Yes. I should have renamed the function.

Except when points is empty. The at best you'll get an access violation,
at worst some problem in a totally unrelated area of the code that you'll
spend days trying to track down. You'll need to:

tPts::iterator lItr = find_max_angle(points);

if( lItr != points.end() )
{
return *lItr;
}
else
{
throw "points is empty";
}

A precondition was stated so an if-statement is unnecessary.

Also, do you realize that the std::vector points is being copied?


Yes. This is not a concern unless points is large.
Jul 23 '05 #15
Jason Heyes wrote:

[ ... ]
The slope is not enough. You need the signs of x and y and you must
handle pathological cases (i.e., when x = 0). In the end you do no
better than atan2 efficiency-wise.


Unfortunately, doing a bit of testing shows I was even further wrong
than this: after a little testing, it looks like even if you ignore the
pathological cases, atan2 is actually _substantially_ faster than just
the floating point division on its own (at least with the
compilers/libraries I usually use).

To make a long story short, what I previously said was clearly wrong,
and badly so at that. I apologize for the misinformation.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Jul 23 '05 #16
"Jerry Coffin" <jc*****@taeus.com> wrote in message
news:11********************@g14g2000cwa.googlegrou ps.com...
Jason Heyes wrote:

[ ... ]
The slope is not enough. You need the signs of x and y and you must
handle pathological cases (i.e., when x = 0). In the end you do no
better than atan2 efficiency-wise.
Unfortunately, doing a bit of testing shows I was even further wrong
than this: after a little testing, it looks like even if you ignore the
pathological cases, atan2 is actually _substantially_ faster than just
the floating point division on its own (at least with the
compilers/libraries I usually use).


Interesting. I guess the atan2 routine works without floating point
division.

To make a long story short, what I previously said was clearly wrong,
and badly so at that. I apologize for the misinformation.


Not a problem. :)
Jul 23 '05 #17

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
by: administrata | last post by:
Hi! I'm programming maths programs. And I got some questions about mathematical signs. 1. Inputing suqare like a * a, It's too long when I do time-consuming things. Can it be simplified? 2....
3
by: gelong | last post by:
Hi there, I have a problem in writing a mathematical function using C++ programming. How to write an input that can insert whole equation? Example is the input are x² + 3y - 4z³ = 0. In maple, it...
36
by: Hoopster | last post by:
Hello, I know nothing about C++ but want to get started. Is there any good free C++ program that I can try to see if I like programming? I also need a good free compiler. I don't want to...
3
by: user | last post by:
Hi all, At the outset, I regret having to post this slightly OT post here. However, I strongly feel that people in this group would be the best to advise me on my predicament. I am working as...
0
by: Juan R. | last post by:
I have updated some basic requirements for a generic mathematical markup language for scientific requirements at the next link. ...
4
by: Xah Lee | last post by:
i've long time been interested in algorithmic mathematical art. That is, mathematical or algorithmic visual art works that are generated by computer such that the program's source code reflects the...
4
by: Talbot Katz | last post by:
Greetings Pythoners! I hope you'll indulge an ignorant outsider. I work at a financial software firm, and the tool I currently use for my research is R, a software environment for statistical...
13
by: jacek.strzelczyk | last post by:
Hello, I'm looking for a C library that provides the notation of n- dimensional mathematical functions. Or is there any other way to decode that kind of functions in C language? Thanks in...
2
by: Madmartigan | last post by:
Hi Operating system is WinXP using SharpDevelop version 1.1.0 and build 2124. I'm new to C# and have a problem trying to get a user to enter 3 mathematical operators of choice, then 2 numbers...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.