C++ify tag

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

  1. 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.
    malcolm.mclean5, Jun 6, 2014
    1. Advertisements

  2. malcolm.mclean5

    Jorgen Grahn Guest

    On Fri, 2014-06-06, wrote:

    (Please wrap your lines (no pun intended) to ~76 columns.)
    (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.
    Do you mean "intersection" and "INTERSECTION" instead of "line" and
    First thing I'd do would be to create a line class, but I'd call it

    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 Grahn, Jun 6, 2014
    1. Advertisements

  3. 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

    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.
    malcolm.mclean5, Jun 6, 2014
  4. malcolm.mclean5

    red floyd Guest

    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.


    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
  5. 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.
    malcolm.mclean5, Jun 6, 2014
  6. malcolm.mclean5

    Jorgen Grahn Guest

    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.

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

    Jorgen Grahn, Jun 6, 2014
  7. malcolm.mclean5

    Öö Tiib Guest

    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.
    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

    "Line is part of space invader" feels almost like that joke:
    What you wrote further down smells like 'typedef' is missing here?
    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.
    "Not sure" about it like I commented above.
    In C++ the hash is (for whatever reason) of type 'size_t' as tradition.
    Cached hash here is likely wasteful "optimization".
    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.
    I don't like screaming caps anywhere. YMMW.
    This is the interface of hash table?
    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
    Öö Tiib, Jun 9, 2014
    1. Advertisements

Ask a Question

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.