creation of a set of segments, please help

Discussion in 'C++' started by aaragon, Nov 13, 2008.

  1. aaragon

    aaragon Guest

    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::eek: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
    aaragon, Nov 13, 2008
    #1
    1. Advertising

  2. aaragon

    SG Guest

    On 14 Nov., 00:08, aaragon <> wrote:
    > bool Segment::eek: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
    SG, Nov 13, 2008
    #2
    1. Advertising

  3. aaragon

    aaragon Guest

    On Nov 13, 5:24 pm, SG <> wrote:
    > On 14 Nov., 00:08, aaragon <> wrote:
    >
    > > bool Segment::eek: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


    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
    aaragon, Nov 13, 2008
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. PC
    Replies:
    2
    Views:
    3,916
    Marc Guardiani
    Nov 12, 2003
  2. Jeff Nokes

    Cache::Cache Stale Segments

    Jeff Nokes, Sep 30, 2003, in forum: Perl
    Replies:
    0
    Views:
    549
    Jeff Nokes
    Sep 30, 2003
  3. Emre Guldogan

    '<#% ... #>' code segments in aspx (C#.net)

    Emre Guldogan, Dec 14, 2004, in forum: ASP .Net
    Replies:
    4
    Views:
    759
    bruce barker
    Dec 14, 2004
  4. keithb
    Replies:
    0
    Views:
    385
    keithb
    Apr 22, 2006
  5. KK
    Replies:
    2
    Views:
    498
    Big Brian
    Oct 14, 2003
Loading...

Share This Page