creation of a set of segments, please help

[aaragon]

Hello everybody,

I have an interesting problem for which I still don't have a solution.
Imagine that you're working with points in two-dimesional space, so
the point class should be (simplifying):

class Point {

double x_,y_;

public:

Point(double x, double y) : x_(x), y_(y) {}
// other constructors and member functions
};

Now, imagine that you're also working with segments in 2D. A segment
consists of its endpoints:

class Segment {

Point source_, target_;
public:
Segment(const Point& s, const Point& t) : source_(s), target_(t)
{}
// other constructors and member functions
};


Now, I want to enforce that if I have points P1, P2, the segment P1-P2
is the same as the segment P2-P1. That is, the orientation of the
segment doesn't matter so as long as the endpoints are the same, the
segments are equal. This could be enforced by operator== in the
Segment class:

bool Segment:perator==(const Segment& s)
{ return ((source_ == s.source_ && target_ == s.target_) || (target_
== s.source_ && source_ == s.target_)); }


Now, I would like to create a set of segments. Of course, the segment
does not have to have duplicates. However, sets are defined by using
operator< which is not defined here.

So the question is, how do I create a std::set of segments? Any ideas?
I could just write operator< so that it compares the smaller point
from both segments, but I thought that someone could have a better
solution.

Thank you all,

aa

 

[SG]

bool Segment:perator==(const Segment& s)
{ return ((source_ == s.source_ && target_ == s.target_) || (target_
== s.source_ && source_ == s.target_)); }

You have to be very careful with comparing doubles -- especially in
case of many geometric algorithms. They work fine on paper but when it
comes to the implementation rounding errors can be a pain in the a**.

Now, I would like to create a set of segments. Of course, the segment
does not have to have duplicates. However, sets are defined by using
operator< which is not defined here.

Right. Anyhow, using points and segments (with doubles as members) as
keys in a set / map might do you harm. In theory you can still work
out a total order. For example: compare Points lexically and store
segments with source<target and compare segments also lexically.

So the question is, how do I create a std::set of segments? Any ideas?

Try to avoid it whenever possible.

Cheers!
SG

 

[aaragon]

You have to be very careful with comparing doubles -- especially in
case of many geometric algorithms. They work fine on paper but when it
comes to the implementation rounding errors can be a pain in the a**.


Right. Anyhow, using points and segments (with doubles as members) as
keys in a set / map might do you harm. In theory you can still work
out a total order. For example: compare Points lexically and store
segments with source<target and compare segments also lexically.


Try to avoid it whenever possible.

Cheers!
SG

Thanks for replying to my post. This is what I came up with since atan
() returns the angle between -pi/2 and pi/2:

struct SegmentSorter {
bool operator()(const segment_type& s1, const segment_type& s2) const
{
// compute angle of first segment
double phi1 = atan((s1.t_.y() - s1.s_.y())/(s1.t_.x() - s1.s_.x()));
// compute angle of second segment
double phi2 = atan((s2.t_.y() - s2.s_.y())/(s2.t_.x() - s2.s_.x()));
return phi1 < phi2;
}
};


typedef std::set<segment_type, SegmentSorter> segment_set;

What do you think?

aa