C++ify tag

Discussion in 'C++' started by malcolm.mclean5@btinternet.com, Jun 6, 2014.

  1. Guest

    I've got a collection of lines, which intersect with each other. To avoid numerical problems and other nasty things, I want to store the intersectionsas intersections, rather than x,y coordinates.

    Now each line means something to higher-level code. It could be an index ina polygon, part of a space invader, whatever. So it needs a arbitrary tag to retrieve and query it.

    Now in C I'd write this something like the following.

    struct line
    {
    double x1, y1, x2, y2;
    void *tag;
    int taglen;
    int hash;
    struct line **intersections;
    int N_intersections;
    } LINE;

    Then you store the LINE objects in a hash table to retrieve them.

    The interface is then

    addline(x1, y1, x2, y2, tag, taglen);
    LINE *getintersections(tag, taglen);


    But the program contains C++, it would be nice to have a more C++ interfaceto it, so that the tags can contain embedded strings or whatever. Also maybe some sort of template so an int tag and a string tag which happens to be 4 bytes and the same bit pattern as the int doesn't evaluate to the same thing.
     
    , Jun 6, 2014
    #1
    1. Advertisements

  2. Jorgen Grahn Guest

    On Fri, 2014-06-06, wrote:

    (Please wrap your lines (no pun intended) to ~76 columns.)

    > I've got a collection of lines, which intersect with each other. To
    > avoid numerical problems and other nasty things, I want to store the
    > intersections as intersections, rather than x,y coordinates.


    (You're delaying the introduction of numerical errors -- a good
    thing I think.)

    Your lines is what some people call vectors in two-dimensional space.

    > Now each line means something to higher-level code. It could be an
    > index in a polygon, part of a space invader, whatever. So it needs a
    > arbitrary tag to retrieve and query it.


    > Now in C I'd write this something like the following.
    >
    > struct line
    > {
    > double x1, y1, x2, y2;
    > void *tag;
    > int taglen;
    > int hash;
    > struct line **intersections;
    > int N_intersections;
    > } LINE;


    Do you mean "intersection" and "INTERSECTION" instead of "line" and
    "LINE"?

    > Then you store the LINE objects in a hash table to retrieve them.
    >
    > The interface is then
    >
    > addline(x1, y1, x2, y2, tag, taglen);
    > LINE *getintersections(tag, taglen);


    > But the program contains C++, it would be nice to have a more C++
    > interface to it, so that the tags can contain embedded strings or
    > whatever. Also maybe some sort of template so an int tag and a string
    > tag which happens to be 4 bytes and the same bit pattern as the int
    > doesn't evaluate to the same thing.


    First thing I'd do would be to create a line class, but I'd call it
    Vector.

    Then an Intersection would simply be a std::pair<Vector>, plus some
    kind of guarantee that the vectors actually intersect. I don't
    understand your tag concept so I won't comment on it.

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
     
    Jorgen Grahn, Jun 6, 2014
    #2
    1. Advertisements

  3. Guest

    On Friday, June 6, 2014 11:27:17 AM UTC+1, Jorgen Grahn wrote:
    > On Fri, 2014-06-06, wrote:
    >
    > Then an Intersection would simply be a std::pair<Vector>, plus some
    > kind of guarantee that the vectors actually intersect. I don't
    > understand your tag concept so I won't comment on it.
    >

    A line is strictly a line segment, best defined by two points in 2D.
    (You can of course define in other ways).

    A line can intersect any number of others. But you also want to
    "tag" the lines with higher-level information. Otherwise, we can
    detect that line AB (the edge of our asteroid polygon) has intersected
    with line CD, but we don't have a clue what CD is, it could be
    another asteroid, a bullet,a space ship, even part of our own
    asteroid. So CD needs to be "tagged" with an arbitrary tag.
    We also need to retrieve CD via the tag from the intersection
    engine.

    if we've got N lines, we can't be doing N^2 intersection tests,
    so they need to all be submitted to the intersection engine
    at once, then the intersections calculated in one pass.
     
    , Jun 6, 2014
    #3
  4. red floyd Guest

    On 6/6/2014 3:03 AM, wrote:
    > I've got a collection of lines, which intersect with each other. To avoid numerical problems and other nasty things, I want to store the intersections as intersections, rather than x,y coordinates.
    >
    > Now each line means something to higher-level code. It could be an index in a polygon, part of a space invader, whatever. So it needs a arbitrary tag to retrieve and query it.
    >
    > Now in C I'd write this something like the following.
    >
    > struct line
    > {
    > double x1, y1, x2, y2;
    > void *tag;
    > int taglen;
    > int hash;
    > struct line **intersections;
    > int N_intersections;
    > } LINE;
    >
    > Then you store the LINE objects in a hash table to retrieve them.
    >
    > The interface is then
    >
    > addline(x1, y1, x2, y2, tag, taglen);
    > LINE *getintersections(tag, taglen);
    >
    >
    > But the program contains C++, it would be nice to have a more C++ interface to it, so that the tags can contain embedded strings or whatever. Also maybe some sort of template so an int tag and a string tag which happens to be 4 bytes and the same bit pattern as the int doesn't evaluate to the same thing.
    >


    why not make line a base class, remove the tag/taglen fields,
    and use inheritance and virtual methods to 'do the right thing'
    with the line.

    e.g.:

    struct line {
    ....
    virtual line* getintersections() = 0;
    };

    struct polygon_index : public line {
    ....
    line *getintersections(); // do polygon index stuff
    };

    struct space_invader: public line {
    ....
    line *getintersections(); // do space invader stuff
    };


    And avoid the LINE stuff, as a matter of style, ALLCAPS
    should pretty much only be used for #defines.
     
    red floyd, Jun 6, 2014
    #4
  5. Guest

    On Friday, June 6, 2014 5:46:23 PM UTC+1, red floyd wrote:
    > On 6/6/2014 3:03 AM, wrote:
    >
    > why not make line a base class, remove the tag/taglen fields,
    > and use inheritance and virtual methods to 'do the right thing'
    > with the line.
    >
    > e.g.:
    >
    > struct line {
    >
    > virtual line* getintersections() = 0;
    >
    > };
    >
    >
    > struct polygon_index : public line {
    >
    > ...
    >
    > line *getintersections(); // do polygon index stuff
    >
    > };
    >
    >
    >
    > struct space_invader: public line {
    >
    > ...
    >
    > line *getintersections(); // do space invader stuff
    >
    > };
    >
    >
    >

    Because we're talking about "has a" relationships. Space Invaders
    have lines associated with them. But the lines aren't "space invader
    lines" with special characteristics. They intersect with any other
    2D line according to Euclidean geometry.

    To avoid running N^2 intersection tests, you need to submit all
    the lines to the intersection engine, run it, then pull out what
    you've intersected with. I suppose lines could be a virtual base class,
    but they'd need "owner" pointers.
     
    , Jun 6, 2014
    #5
  6. Jorgen Grahn Guest

    On Fri, 2014-06-06, red floyd wrote:
    > On 6/6/2014 3:03 AM, wrote:
    >> I've got a collection of lines, which intersect with each other. To avoid numerical problems and other nasty things, I want to store the intersections as intersections, rather than x,y coordinates.
    >>
    >> Now each line means something to higher-level code. It could be an index in a polygon, part of a space invader, whatever. So it needs a arbitrary tag to retrieve and query it.
    >>
    >> Now in C I'd write this something like the following.
    >>
    >> struct line
    >> {
    >> double x1, y1, x2, y2;
    >> void *tag;
    >> int taglen;
    >> int hash;
    >> struct line **intersections;
    >> int N_intersections;
    >> } LINE;
    >>
    >> Then you store the LINE objects in a hash table to retrieve them.
    >>
    >> The interface is then
    >>
    >> addline(x1, y1, x2, y2, tag, taglen);
    >> LINE *getintersections(tag, taglen);
    >>
    >>
    >> But the program contains C++, it would be nice to have a more C++ interface to it, so that the tags can contain embedded strings or whatever. Also maybe some sort of template so an int tag and a string tag which happens to be 4 bytes and the same bit pattern as the int doesn't evaluate to the same thing.
    >>

    >
    > why not make line a base class, remove the tag/taglen fields,
    > and use inheritance and virtual methods to 'do the right thing'
    > with the line.


    Why? He doesn't seem to have any use for the untagged line.

    Disclaimer: I'm biased against inheritance and runtime polymorphism,
    especially when the runtime polymorphism isn't used at runtime.

    ....
    > And avoid the LINE stuff, as a matter of style, ALLCAPS
    > should pretty much only be used for #defines.


    Yes, it looks bad even as C. Just use 'struct line' and say no to
    typedefs.

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
     
    Jorgen Grahn, Jun 6, 2014
    #6
  7. Öö Tiib Guest

    On Friday, 6 June 2014 13:03:26 UTC+3, wrote:
    > I've got a collection of lines, which intersect with each other. To avoid numerical problems and
    > other nasty things, I want to store the intersections as intersections, rather than x,y coordinates.


    Correct me if I'm wrong but it feels that you are talking about "line segments" not "lines".
    It matters since for lines on plane intersection is almost always the case and for line
    segments it is typically rare.

    > Now each line means something to higher-level code. It could be an index in a polygon, part of
    > a space invader, whatever. So it needs a arbitrary tag to retrieve and query it.


    Isn't that what the line "means" composition as rule? Relation between composite and
    component is one of strongest relations. "Tags" are usually used for rather soft and loose
    relations.

    "Line is part of space invader" feels almost like that joke:
    http://www.youtube.com/watch?v=BKorP55Aqvg :)

    > Now in C I'd write this something like the following.
    >
    > struct line


    What you wrote further down smells like 'typedef' is missing here?

    > {
    > double x1, y1, x2, y2;


    The doubles here may cause artifacts when intersection close to endpoint of one or
    both of the line segments is sometimes undetected because of floating point arithmetic.

    > void *tag;
    > int taglen;


    "Not sure" about it like I commented above.

    > int hash;


    In C++ the hash is (for whatever reason) of type 'size_t' as tradition.
    Cached hash here is likely wasteful "optimization".

    > struct line **intersections;
    > int N_intersections;


    I'm not sure how often the "lines" of yours are added and removed
    but if often then those two lines fragment your memory in no time.

    > } LINE;


    I don't like screaming caps anywhere. YMMW.

    > Then you store the LINE objects in a hash table to retrieve them.
    >
    > The interface is then
    >
    > addline(x1, y1, x2, y2, tag, taglen);
    > LINE *getintersections(tag, taglen);


    This is the interface of hash table?

    > But the program contains C++, it would be nice to have a more C++ interface to it, so that
    > the tags can contain embedded strings or whatever. Also maybe some sort of template so
    > an int tag and a string tag which happens to be 4 bytes and the same bit pattern as the int
    > doesn't evaluate to the same thing.


    May be think more about the types of entities and relations between the entities and how
    strong those relations are and how those are implemented and where stored. About hierarchy
    of composition and about your "line a intersects with line b" relation. It feels that particular
    implementation of Bentley-Ottmann algorithm or something like that is dictating design for
    you.
     
    Öö Tiib, Jun 9, 2014
    #7
    1. Advertisements

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.
Similar Threads
  1. jstack
    Replies:
    1
    Views:
    828
    Tor Iver Wilhelmsen
    Jul 4, 2003
  2. kishan bisht

    struts tag inside a tag

    kishan bisht, Jul 8, 2003, in forum: Java
    Replies:
    1
    Views:
    1,768
    Wendy S
    Jul 9, 2003
  3. shahbaz
    Replies:
    0
    Views:
    1,145
    shahbaz
    Oct 27, 2003
  4. RC
    Replies:
    2
    Views:
    696
    Malte
    May 10, 2005
  5. shruds
    Replies:
    1
    Views:
    1,333
    John C. Bollinger
    Jan 27, 2006
  6. posterguy

    p tag vs br tag

    posterguy, Apr 13, 2004, in forum: HTML
    Replies:
    24
    Views:
    8,972
    Poison
    Apr 14, 2004
  7. RC
    Replies:
    2
    Views:
    869
  8. Gregory Nans
    Replies:
    0
    Views:
    485
    Gregory Nans
    Aug 30, 2003
Loading...