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]

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

Jerry Coffin wrote:

In article <bu************ @ID-162430.news.uni-berlin.de>,
si*********@hot mail.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.a delphia.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******@gasca d.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.programmin g or perhaps comp.database.t heory (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.programmin g or perhaps comp.database.t heory (my
subconsiousness says Hilbert-curves could be interesting here).

comp.graphics.a lgorithms

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