Re: C++ify tag
On Friday, 6 June 2014 13:03:26 UTC+3, malcolm...@btinternet.com 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.