Re: GP: Flipping a point across a line: The answer

[Kevin Shea <kev@d-cubed.co.uk>]

Hi all,

I'm brand-new to this list and so far I've seen a lot of excellent
information on where to start, sources of info etc. Thanks for
everything
so far.

Anyway, sorry to bring this one back up after it seems to have been left
to lie for a while but I've just read this and think there are a few
things worth pointing out about the answers given so far.

Eudoxus3 wrote:
> 
> ...
> 
> // declare variables to use, integers are Ok.
> declare A, B, C, D, E, Y, M, ZZ, P
> ...
> // so, from here we want to get `D`, which will also have x and y values...
> // this bit calculates where a line from C to A,B at a right angle will
> // intersect...
> Y = (B.y - A.y) / (B.x - A.x)

The basic algorithm everyone has used is correct, but there are a few
problems with it - (above) what if B.x == A.x? Especially if you're
using
integer display-coords? I saw another mail involving tan(), cos() etc 
which has a related problem - arctan(what?) == 90 degrees?

A more reliable approach for doing this type of operation (this sort of
stuff is what I do for a living) is to use a parameterised definition
of a line instead of the implicit 'y = mx + c' form. You can avoid a lot
of infinite and undefined results that way.

Start off defining your line as L(t) = A + tD where A is a point on the
line and D = B - A. Your line is then parameterised by t from 0 (A) to
1 (B). Alternatively (I prefer this one), make D a unit vector and
remember
B's parameter which is also the length of the line-segment.

Next, orthogonally project C onto the line to get the point I. It's
worth
noting that this projection & reflection are through the *unbounded*
line
through A & B. The (vector) equation for the projection is:

I = A + [(C - A).D'] D' // '.' is the scalar/dot product here

where D' is the *unit* direction of the line

finally,

Cm = C + 2(I-C).

This method also works in 3d as well without change.

The only thing you have to watch is when defining the unit direction D'.
If you're calculating it on the fly from the two endpoints A & B by
dividing (B-A) by its length, watch for a divide-by-zero when B and A
are
the same point. A simple resolution check is needed along the lines of:

DL = length_of(D)
if DL < "resolution"
	// There *is* no line in this case, only a point
	D'.x = 0
	D'.y = 0
	...
else
	D'.x = D.x/DL
	D'.y = D.y/DL
	...
endif

Note that are no more divides, sqrt() or trig functions after this -
everything is relatively fast additions & multiplications from here on
in.

The 2d pseudo code for the reflection would then look vaguely like
(there
are a lot of intermediate variables here that can be eliminated):

CA.x = C.x - A.x
CA.y = C.y - A.y

// Project C onto the line to get I (calculate D' as above)
PD = CA.x * D'.x + CA.y * D'.y // the 'distance' along the line from A
I.x = A.x + PD * D'.x
I.y = A.y + PD * D'.y

// Then get Cm
IC.x = I.x - C.x
IC.y = I.y - C.y

Cm.x = C.x + 2*IC.x
Cm.y = C.y + 2*IC.y

Hope all this helps!

Kev

-----------------------------------------------------------------------
Kevin Shea						D-Cubed Ltd.
Software Engineer					Cambridge
Tel:	+44 1223 722632					CB6 2XD
Email:	kev@d-cubed.co.uk				United Kingdom

The opinions expressed here are my own and in no way represent the
opinions of my employer etc etc
-----------------------------------------------------------------------
=================================================================
To SUBSCRIBE or UNSUBSCRIBE please visit
http://gameprogrammer.com/mailinglist.html