Verctor/List what is best for my design?

[Sims]

Hi,

I know this is slightly OT but before i can get to the programming part i
want to make sure that i have the structure covered.

I have a 2D map and items in my list/vector will be lines on the map, with a
start and finish point within the map, so an item would have a start pos
S(x,y) and an end pos E(x,y).

so my structure would be something like

struct _POS{
int x;
int y;
};

struct _ITEMLOC{
_POS pos_start;
_POS pos_end;
};

So in effect it would be a straight line going from one point to another.

If i have a vector with hundreds of items i want to retrieve all the items
that fall within a certain square.

something like Search( top, left, bottom, right). And that would return all
the items whose line are within that square, (either partially or totally).

Does anybody know how i could achieve that?

Many thanks in advance.
Sims

[Peter Koch Larsen]

"Sims" <si*********@hotmail.com> skrev i en meddelelse
news:bu************@ID-162430.news.uni-berlin.de...

Hi,

I know this is slightly OT but before i can get to the programming part i
want to make sure that i have the structure covered.

I have a 2D map and items in my list/vector will be lines on the map, with a start and finish point within the map, so an item would have a start pos
S(x,y) and an end pos E(x,y).

so my structure would be something like

struct _POS{
This is a nonportable name. Use a better name.
int x;
int y;
};

struct _ITEMLOC{
And so is this. The reason: all identifiers containing two consecutive
underscores or beginning with one underscore and an uppercase letter are
reserved for the implementation (the compiler).
_POS pos_start;
_POS pos_end;
};

So in effect it would be a straight line going from one point to another.

If i have a vector with hundreds of items i want to retrieve all the items
that fall within a certain square.

something like Search( top, left, bottom, right). And that would return all the items whose line are within that square, (either partially or totally).
Does anybody know how i could achieve that?

Many thanks in advance.
Sims

There really is no big difference between a list and a vector here, but the
vector would be faster in this case. You just have to look at the entiere
solution to determine what operations are needed. But if you stick to
std::containers and iterators, it should not be a problem to replace the
container and try both alternatives.

Kind regards
Peter

[Chris Theis]

"Peter Koch Larsen" <pk*@mailme.dk> wrote in message
news:40*********************@dread14.news.tele.dk. ..
[SNIP]

There really is no big difference between a list and a vector here, but

the vector would be faster in this case.

IMHO this depends very much on what the user does more often - insert/delete
or search for elements. However, you're of course right that both containers
are easily exchangeable. Thus this discussion might not really lead to
something unless it is tested for the actual case.

[SNIP]

Chris

[Chris Theis]

"Sims" <si*********@hotmail.com> wrote in message
news:bu************@ID-162430.news.uni-berlin.de...

Hi,
[SNI] something like Search( top, left, bottom, right). And that would return all the items whose line are within that square, (either partially or totally).

In your case you might also consider the use of a set<> container, which
usually is implemented in terms of a balanced binary tree. Supplying an
appropriate sorting criterion might reduce your search times in comparison
to a vector or a list.

Regards
Chris

[Sims]

In your case you might also consider the use of a set<> container, which
usually is implemented in terms of a balanced binary tree. Supplying an
appropriate sorting criterion might reduce your search times in comparison
to a vector or a list.

Regards
Chris

Thanks for the replies,
The elements are created once, there is no delete or insert afterward.

How would i do a search for a two dimensional array?

I know how to do a search in a list that is sorted, (in alphabetical order
for example), but how would search for items that are start/end points given
a square?

Also i will have in the region of 200 000 items does that make a dif when it
comes to list/vector?

Sims

[Chris Theis]

"Sims" <si*********@hotmail.com> wrote in message
news:bu************@ID-162430.news.uni-berlin.de...

In your case you might also consider the use of a set<> container, which
usually is implemented in terms of a balanced binary tree. Supplying an
appropriate sorting criterion might reduce your search times in comparison to a vector or a list.

Regards
Chris

Thanks for the replies,
The elements are created once, there is no delete or insert afterward.

How would i do a search for a two dimensional array?

Why would you want to use a 2D array? I'd propose for example a collection
of collections (e.g. vector of vectors) for this.

I know how to do a search in a list that is sorted, (in alphabetical order
for example), but how would search for items that are start/end points given a square?
The search algorithms of the standard library accept a user defined unary
predicate function that can be used to supply your search criterium.
Furthermore you could pre-sort your collection based on the starting
coordinates for example.

Also i will have in the region of 200 000 items does that make a dif when it comes to list/vector?
That's difficult to say. In general vectors are fast when inserting or
deleting at the end of the collections, whereas lists are better if
inserting/deletion is required anywhere. On the other hand vectors provide
random access which is not supplied by the list class. Furthermore (in
comparison to sets for example) vectors are considered to be "slow" for
searching and lists are considered "very slow" with respect to this
requirement. As not many insertion/deletion statements will be needed but
searching is required quite often I'd suggest thinking about using a set<>.

Sims

Chris

[Jerry Coffin]

In article <bu************@ID-162430.news.uni-berlin.de>,
si*********@hotmail.com says...

Hi,

I know this is slightly OT but before i can get to the programming part i
want to make sure that i have the structure covered.

I have a 2D map and items in my list/vector will be lines on the map, with a
start and finish point within the map, so an item would have a start pos
S(x,y) and an end pos E(x,y).
[ ... ]
So in effect it would be a straight line going from one point to another.

If i have a vector with hundreds of items i want to retrieve all the items
that fall within a certain square.

IMO, the representation you've chosen is probably less than optimal for
the job at hand, at least assuming you're doing searches relatively
frequently.

For frequent searches, I'd instead represent the points in polar
coordinates, and convert the corners of the rectangle to polar
coordinates as well.

What this will do is let you define an area roughly similar to a slice
of a donut (with a size and position defined by your square), and _very_
quickly eliminate the vast majority of lines that don't fall within that
area. Once you've done that, you can check the remaining lines to see
whether they really intersect your square, or just happen to be close to
it. This test is substantially more expensive, so eliminating it most
of the time will probably be a real win.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Jerry Coffin]

In article <bu************@ID-162430.news.uni-berlin.de>,
si*********@hotmail.com says...

[ ... ]

Thanks for the replies,
The elements are created once, there is no delete or insert afterward.

In that case, you almost certainly want to use a vector rather than a
set or map -- the latter offer logarithmic time on insertions and
deletions, but in exchange for this, they normally lose some searching
speed (at least on most processors).

The reason is simple: they're normally implemented as trees, with each
node individually allocated, so they have poor locality of reference. A
vector is always contiguous, so it generally has substantially better
locality of reference, making it much more cache-friendly.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Karl Heinz Buchegger]

Jerry Coffin wrote:

In article <bu************@ID-162430.news.uni-berlin.de>,
si*********@hotmail.com says...

Hi,

I know this is slightly OT but before i can get to the programming part i
want to make sure that i have the structure covered.

I have a 2D map and items in my list/vector will be lines on the map, with a
start and finish point within the map, so an item would have a start pos
S(x,y) and an end pos E(x,y).

[ ... ]

So in effect it would be a straight line going from one point to another.

If i have a vector with hundreds of items i want to retrieve all the items
that fall within a certain square.

IMO, the representation you've chosen is probably less than optimal for
the job at hand, at least assuming you're doing searches relatively
frequently.

For frequent searches, I'd instead represent the points in polar
coordinates, and convert the corners of the rectangle to polar
coordinates as well.

What this will do is let you define an area roughly similar to a slice
of a donut (with a size and position defined by your square), and _very_
quickly eliminate the vast majority of lines that don't fall within that
area.

Never heard of that idea.
But ... to speed up the testing (using cartesian coordinates), simple techniques
have been developed in the 60's. The OP should consult any literature on
computer graphics and look up the section which talkes about window clipping
using 'end point codes' (Cohen-Sutherland clipping).

Or google:

http://www.google.com
"window clipping end point code"

--
Karl Heinz Buchegger
kb******@gascad.at

[Karl Heinz Buchegger]

Jerry Coffin wrote:

In article <bu************@ID-162430.news.uni-berlin.de>,
si*********@hotmail.com says...

[ ... ]

Thanks for the replies,
The elements are created once, there is no delete or insert afterward.

In that case, you almost certainly want to use a vector rather than a
set or map -- the latter offer logarithmic time on insertions and
deletions, but in exchange for this, they normally lose some searching
speed (at least on most processors).

But still sorting the squares eg. on the left x-coordinate can speed
up the process.
The reason is simple: Walking linearly through the vector and testing
the primitiv against it, once you found a square, which has a left
x-coordinate greater then the maximum x coordinate of the primitive
(lies entirely to the right of the primtive) you know that all other
squares will also be completely right of the primtive and thus the
test can be terminated early.

But as always: profile, if it makes a difference. Especially with
computer graphics it's not always obvious where the time is spent.

--
Karl Heinz Buchegger
kb******@gascad.at

[Peter Koch Larsen]

"Karl Heinz Buchegger" <kb******@gascad.at> skrev i en meddelelse
news:40***************@gascad.at...

Jerry Coffin wrote:

In article <bu************@ID-162430.news.uni-berlin.de>,
si*********@hotmail.com says...

[ ... ]

Thanks for the replies,
The elements are created once, there is no delete or insert afterward.

In that case, you almost certainly want to use a vector rather than a
set or map -- the latter offer logarithmic time on insertions and
deletions, but in exchange for this, they normally lose some searching
speed (at least on most processors).

But still sorting the squares eg. on the left x-coordinate can speed
up the process.
The reason is simple: Walking linearly through the vector and testing
the primitiv against it, once you found a square, which has a left
x-coordinate greater then the maximum x coordinate of the primitive
(lies entirely to the right of the primtive) you know that all other
squares will also be completely right of the primtive and thus the
test can be terminated early.

But as always: profile, if it makes a difference. Especially with
computer graphics it's not always obvious where the time is spent.

--
Karl Heinz Buchegger
kb******@gascad.at

The actual problem - as I understood it - was to draw all lines found in
some square. In that case, sorting would be almost useless so far as i can
see.

Kind regards
Peter

[Karl Heinz Buchegger]

Peter Koch Larsen wrote:

The actual problem - as I understood it - was to draw all lines found in
some square. In that case, sorting would be almost useless so far as i can
see.

Aehm. Somehow I turned this around to read: some lines against
lots of squares :-)

Anyway:
Sort the lines by their minumum x coordinate. You can stop
testing the lines as soon as you find one which has a minumum
x coordinate which is bigger then the maximum x coordinate of
the square.
--
Karl Heinz Buchegger
kb******@gascad.at

[Chris Theis]

"Jerry Coffin" <jc*****@taeus.com> wrote in message
news:MP************************@news.clspco.adelph ia.net...
[SNIP]

For frequent searches, I'd instead represent the points in polar
coordinates, and convert the corners of the rectangle to polar
coordinates as well.

If I understand you correctly you try to eliminate the vast majority of
candidates by testing whether they fall into that "slice". In case they do
you perform the actual test whether the point is within the square. In
principle this means that you perform a projection onto the angular
coordinate to perform the coarse test. However, I don't really understand
the advantage resulting from the conversion to polar coordinates, as such
projection tests (based on cartesian coordinates) are a common technique in
collision detection. The number of minum comparisons is 1 and the maximum
number of comparisons is 2. IMHO it's just the same with the polar
coordinates, but probably I'm missing something. I'd really appreciate if
you could point out whether I'm overlooking some crucial point.

Regards
Chris

[Peter Koch Larsen]

"Karl Heinz Buchegger" <kb******@gascad.at> skrev i en meddelelse
news:40***************@gascad.at...

Peter Koch Larsen wrote:

The actual problem - as I understood it - was to draw all lines found in
some square. In that case, sorting would be almost useless so far as i can see.

Aehm. Somehow I turned this around to read: some lines against
lots of squares :-)

Anyway:
Sort the lines by their minumum x coordinate. You can stop
testing the lines as soon as you find one which has a minumum
x coordinate which is bigger then the maximum x coordinate of
the square.
--
Karl Heinz Buchegger
kb******@gascad.at

Yes. This will help the filtering somewhat, but if it pays of is another
question. My gut feeling is that sorting and searching will not help much
unless it is quite accurate and that a simple sorting on max x-coordinate
will be close to useless. There are no doubt better ways to do it but then
we should be in comp.programming or perhaps comp.database.theory (my
subconsiousness says Hilbert-curves could be interesting here).

Kind regards
Peter

[Karl Heinz Buchegger]

Peter Koch Larsen wrote:

Yes. This will help the filtering somewhat, but if it pays of is another
question. My gut feeling is that sorting and searching will not help much
unless it is quite accurate and that a simple sorting on max x-coordinate
will be close to useless.
That depends on how often the whole process is done, how often the
lines are updated etc. It can make a difference but often it is just
the case that the sort process takes longer then testing a few thousend
lines against a box (which is quite simple to do, especially if the lines
can be reoriented to always point eg. to the right and up).
That's why I said in a previous post: Try it and see if it makes a
difference.
There are no doubt better ways to do it but then
we should be in comp.programming or perhaps comp.database.theory (my
subconsiousness says Hilbert-curves could be interesting here).

comp.graphics.algorithms

--
Karl Heinz Buchegger
kb******@gascad.at