Prev: Infinite Series Help
Next: The closure of the union equals the union of the closures
From: Brandon on 9 Jul 2010 17:07
I have a three dimensional environment partitioned into a regular grid
of cubes. There's a line segment in the space as well and I'd like to
know which of the cubes the line segment intersects. Is there an
efficient algorithm for this?
From: OwlHoot on 9 Jul 2010 20:33
On Jul 9, 10:07 pm, Brandon <brandon.joseph.mo...(a)gmail.com> wrote:
>
> I have a three dimensional environment partitioned into a regular grid
> of cubes.  There's a line segment in the space as well and I'd like to
> know which of the cubes the line segment intersects.  Is there an
> efficient algorithm for this?

Assume your line is in the form:

x = a1.t + b1, y = a2.t + b2, z = a3.t + b3

and the grid is the set of points { - c.x, -d.y, -e.z } for fixed
c, d, e with x, y, and z equal .. -2, -1, 0, 1, 2, .. independently
then intersections occur where:

c 0 0 a1 x b1

0 d 0 a2 y b2
( ) ( ) = ( )
0 0 e a3 z b3

- d.e.a1 - e.c.a2 - c.d.a3 c.d.e t K

where K is another parameter, and the final row is a "dummy"
extra condition chosen so that the determinant on the left is:

(d.e.a1)^2 + (e.c.a2)^2 + (c.d.a3)^2 + (c.d.e)^2

(You'll need to check the signs, as that's the kind of thing
I often get wrong, especially when I've had a few drinks!)

This gives a solution of the form:

x, y, z, t = A1.K + B1, A2.K + B2, A3.K + b3, A4.K + B4

and then you need to choose K so that x, y, z are integers, or
as near to integers as necessary for your requirements.

If you're content with approximate solutions, for example if
any of c, d, e are irrational, then this becomes an exercise
in Diophantine approximation.

See: http://en.wikipedia.org/wiki/Diophantine_approximation


Cheers

John Ramsden
From: James Waldby on 9 Jul 2010 22:16
On Fri, 09 Jul 2010 14:07:08 -0700, Brandon wrote:

> I have a three dimensional environment partitioned into a regular grid
> of cubes. There's a line segment in the space as well and I'd like to
> know which of the cubes the line segment intersects. Is there an
> efficient algorithm for this?

There is an efficient algorithm to list such elements; see
<http://en.wikipedia.org/wiki/Bresenham's_line_algorithm>.

On the other hand, if you want what you actually asked for,
the answer is No. There is no algorithm for causing people
to know things, much less one that's efficient.

--
jiw
From: Rob Johnson on 10 Jul 2010 02:36
In article <i18l5d$idj$1(a)news.eternal-september.org>,
James Waldby <no(a)no.no> wrote:
>On Fri, 09 Jul 2010 14:07:08 -0700, Brandon wrote:
>
>> I have a three dimensional environment partitioned into a regular grid
>> of cubes. There's a line segment in the space as well and I'd like to
>> know which of the cubes the line segment intersects. Is there an
>> efficient algorithm for this?
>
>There is an efficient algorithm to list such elements; see
><http://en.wikipedia.org/wiki/Bresenham's_line_algorithm>.
>
>On the other hand, if you want what you actually asked for,
>the answer is No. There is no algorithm for causing people
>to know things, much less one that's efficient.

The Bresenham algorithm draws nice looking lines, but it does not
fill in all the pixels that the line intersects. Filling in all
pixels that a line intersects looks blotchier than the lines that
the Bresenham algorithm draws.

To set all pixels a line touches, an algorithm needs to track each
time the line crosses a pixel boundary on any axis.

Rob Johnson <rob(a)trash.whim.org>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
 | 
Pages: 1
Prev: Infinite Series Help
Next: The closure of the union equals the union of the closures