446,132 Members | 1,948 Online
Need help? Post your question and get tips & solutions from a community of 446,132 IT Pros & Developers. It's quick & easy.

# Slightly mathematical programming problem.

 P: n/a 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 points) { Point max_point = points[0]; double max_angle = max_point.get_angle(); std::vector::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 Replies

 P: n/a 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

 P: n/a 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

 P: n/a "Raghu Uppalli" 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

 P: n/a 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

 P: n/a > 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

 P: n/a "Niels Dybdahl" 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

 P: n/a "Jason Heyes" wrote in message news:42***********************@news.optusnet.com.a u... "Niels Dybdahl" 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 tPts; tPts::iterator find_max_angle( tPts& aPts ) { return std::max_element( aPts.begin() , aPts.end() , boost::bind ( std::less() , 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

 P: n/a "Jeff Flinn" wrote in message news:d2**********@bluegill.adi.com... "Jason Heyes" wrote in message news:42***********************@news.optusnet.com.a u... "Niels Dybdahl" 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 tPts; tPts::iterator find_max_angle( tPts& aPts ) { return std::max_element( aPts.begin() , aPts.end() , boost::bind ( std::less() , 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

 P: n/a "Jeff Flinn" 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 tPts; tPts::iterator find_max_angle( tPts& aPts ) { return std::max_element( aPts.begin() , aPts.end() , boost::bind ( std::less() , 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 points) { return *find_max_angle(points); } Everyone is happy! Jul 23 '05 #10

 P: n/a Jason Heyes wrote: "Jeff Flinn" 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 tPts; tPts::iterator find_max_angle( tPts& aPts ) { return std::max_element( aPts.begin() , aPts.end() , boost::bind ( std::less() , 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 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

 P: n/a 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

 P: n/a In message <11**********************@f14g2000cwb.googlegroups .com>, Jerry Coffin writesJason Heyes wrote:[ ... ] double Point::get_angle() const; // TODO: implement this!If you care much about efficiency, you may NOT want to implement thisas 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'rediscarding most of the values anyway, so computing the actual angleinstead 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

 P: n/a "Jerry Coffin" 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

 P: n/a "Jeff Flinn" wrote in message news:d2**********@bluegill.adi.com... Jason Heyes wrote: "Jeff Flinn" 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 tPts; tPts::iterator find_max_angle( tPts& aPts ) { return std::max_element( aPts.begin() , aPts.end() , boost::bind ( std::less() , 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 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

 P: n/a 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

 P: n/a "Jerry Coffin" 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 discussion thread is closed

Replies have been disabled for this discussion.