C++ify tag

[malcolm.mclean5]

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.

 

[Jorgen Grahn]

On Fri, 2014-06-06, (e-mail address removed) 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:air<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

 

[malcolm.mclean5]

On Fri, 2014-06-06, (e-mail address removed) wrote:

Then an Intersection would simply be a std:air<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.

 

[red floyd]

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.

 

[malcolm.mclean5]

On 6/6/2014 3:03 AM, (e-mail address removed) 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.

 

[Jorgen Grahn]

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

 

[Öö Tiib]

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:

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.