Calculating coordinate intersections?

[DaveC]

A point is at X1,Y1. Second point is at X2,Y2.

If point 1 shoots at point 2 (takes a vector in that general direction), how
can I know that point 2 was hit?

Ideas?

Thanks.

[Daniel Pitts]

Are we talking points, or tiny circles, or something else? For points,
it would have to go in the *exact* direction.

If we're talking tiny spheres, then they need only get close enough.
meaning the distance to the line (defined by point 1 and your vector) to
point 2 is <= the sum of the radii of the two circles.

I don't remember the math off the top of me head, but it is pretty
straight forward vector math. I think it involves the dot product of
the direction unit vector and the vector between the two points.

If point1 travels only so far in the given direction, then you'd need to
do a second check (after the first) to make sure that it goes far enough
in that direction to intersect.

This is where algebra comes in. Fun stuff, no?

[DaveC]

> I don't remember the math off the top of me head, but it is pretty
> straight forward vector math. I think it involves the dot product of
> the direction unit vector and the vector between the two points.

The *exact* math is what I'm looking for.

Let's presume stationary dots (for X1,Y2 & X2,Y2).

[none Rouben Rostamian]

In article <0001HW.CD6E31F4...@news.eternal-september.org>,

DaveC <newsgroups> wrote:
>A point is at X1,Y1. Second point is at X2,Y2.
>
>If point 1 shoots at point 2 (takes a vector in that general direction), how
>can I know that point 2 was hit?

Suppose you are shooting in the direction of vector V = <V1, V2>.
Let A = <X2 - X1, Y2 - Y1>.

You will hit the target if:
(a) V is parallel to A;
and
(b) V has positive components along A.

The first condition is equivalent to A1*V2 = A2*V1.

The second condition is equivalent to A1*V1 + A2*V2 > 0.

--
Rouben Rostamian

[DaveC]

> Suppose you are shooting in the direction of vector V = <V1, V2>.
> Let A = <X2 - X1, Y2 - Y1>.
>
> You will hit the target if:
> (a) V is parallel to A;
> and
> (b) V has positive components along A.
>
> The first condition is equivalent to A1*V2 = A2*V1.
>
> The second condition is equivalent to A1*V1 + A2*V2 > 0.

V in in degrees?

[Robert Wessel]

Sounds like homework.

But here's a hint: What's the equation of the line traced by the shot
from point one? And then what special cases are there?

[Geoff]

No.

A vector has a magnitude and a direction but the units depend on the
coordinate system in use. In this case the direction is A as described
by the distances from P1 to P2 in the X and Y Cartesian coordinates.
You'll have to do the trigonometry to get an angle for A and the units
you get will depend on the programming language or algorithms you
choose. This is called a coordinate transformation. If you want
degrees or radians you will have to transform from Cartesian to polar
coordinates. See "Pythagoras" for more information.

[DaveC]

> Sounds like homework.
>
> But here's a hint: What's the equation of the line traced by the shot
> from point one? And then what special cases are there?

Your "homework" ear needs tuning: I'll be 60 this year. (c;

A friend (in his 50's) is writing a space (ie, "Aliens attack", et. al.) game
and needs to figure out this kind of math.

I don't know much math (just acting as the messenger...).

The line traced by the shot: isn't that just from point X1,Y1 at an angle of,
for example, 45 degrees? Don't know what equation that would be...

Dave

[BartC]

"DaveC" <inv...@invalid.net> wrote in message
news:0001HW.CD6F67DD...@news.eternal-september.org...

> The line traced by the shot: isn't that just from point X1,Y1 at an angle
> of,
> for example, 45 degrees? Don't know what equation that would be...

A line from P at x1y1 towards Q at x2y2 *will* pass through Q eventually
(assuming Q is still in the same place if and when the projectile arrives).

You're probably asking whether any arbitrary vector through P, will pass
through Q. Here you need to google for things such as "equation of straight
line", "nearest point to a line" and so on. The latter will give you the
shortest distance between Q and the line through P; if 0, or close to zero,
then the line passes through or near Q. Perhaps another way is to work out
the angle of the line from P, and the line PQ, and see if they are
coincident (use atan() here, but watch out when the x1=x2).

However to work on a whole game, your friend needs to learn some basic
vector maths.

--
Bartc

[Robert Wessel]

On Wed, 20 Mar 2013 13:19:25 -0700, DaveC <inv...@invalid.net> wrote:

>> Sounds like homework.
>>
>> But here's a hint: What's the equation of the line traced by the shot
>> from point one? And then what special cases are there?
>
>Your "homework" ear needs tuning: I'll be 60 this year. (c;

Doesn't mean you're not in school with a homework assignment. ;-)

>A friend (in his 50's) is writing a space (ie, "Aliens attack", et. al.) game
>and needs to figure out this kind of math.
>
>I don't know much math (just acting as the messenger...).
>
>The line traced by the shot: isn't that just from point X1,Y1 at an angle of,
>for example, 45 degrees? Don't know what equation that would be...

There are several ways to skin that cat, but a conceptually simple
approach is as follows:

The general equation of a line is:

y=m*x+b (1)

If your projectile is traveling at angle alpha, m is tan(alpha). You
can then subsitute in x1 and y1 and solve for b:

y1=m*x1+b
-or-
b = y1-x1*tan(alpha)

Then you can see if the second point is on the line, by just solving
(1) for x2, and seeing if that value is y2.

That leaves a few loose ends (you'd find a match if the second point
were on the wrong side of the first point, but still on the line), and
the arithmetic falls apart for vertical lines (best to just rotate the
world 90 degrees for lines more than 45 degrees off the X axis).

The bigger problem is that you don't really want exact intersection.
IOW, you count as a hit if you pass within some distance, epsilon, of
the second point.

You can handle that by assuming a line going through the second point,
at a 90 degree angle to the first line. Then you have equations for
two lines, and you can determine where the lines intersect. IOW, you
end up with the following system of equations:

y = m1*x + b1
y = m2*x + b2

Which you can trivially solve to find the point of intersection. That
intersection will be the point of closest approach. You can then
trivially compute the distance between the intersection and the point
with the usual distance formula:

d = sqrt((x2-xi)**2 + (y2-yi)**2)

and the check if (d < epsilon).

Normally you'd compute the square of the distance (avoids the need for
the messy square root calculation), and compare to (epsilon**2)
instead.

This still leaves you the issues of relative positions (the
intersection could, again, be "behind" the first point), and the
arithmetical problems of near vertical lines, both of which you'd need
to handle (usually done with some creative rotations and
translations).

[James Dow Allen]

Some of the answers make this over-complicated.

Calculate the angle to the target.
Calculate the angle the gun is fired.
Subtract to get the angular error.

A fanning-out ray gun will hit if the angular error
is less than some threshold.
For a normal projectile gun, first multiply the
angular error by distance to target.
(And thus changing degrees to meters.)

James

[Daniel Pitts]

Conceptually that is simpler, but it is far more difficult to calculate
angles than to use vector dot products to come up with the same "meters"
value.

[Rui Maciel]

DaveC wrote:

> Ideas?

The general idea is to bound the target with a volume and then test the
collision between a line and that bounding volume.

A particularly simple approach is to adopt a circle/sphere as a bounding
volume, and then evaluate any possible collision by evaluating the
intersection between a shot/line and the bounding volume/sphere.

http://en.wikipedia.org/wiki/Line%E2%80%93sphere_intersection


Hope this helps,
Rui Maciel

[Rui Maciel]

James Dow Allen wrote:

> Some of the answers make this over-complicated.

“Make things as simple as possible, but not simpler.”

> Calculate the angle to the target.
> Calculate the angle the gun is fired.
> Subtract to get the angular error.

Your suggestion is simpler, but has the downside of failing to actually
work. Think about it for a moment, particularly the relation between the
radius, the angle, and the tangent function.


Rui Maciel

[DaveC]

> Conceptually that is simpler, but it is far more difficult to calculate
> angles than to use vector dot products to come up with the same "meters"
> value.

Can you please show how this is done?

[Daniel Pitts]

I gave you more than enough keywords for google. It's been too long
since I've done this myself, and I have to look it up every time anyway.
Google for "vector dot product", or "distance from point to a line"
and you'll likely find your answers and then some.

[Chris M. Thomasson]

"DaveC" wrote in message
news:0001HW.CD6E31F4...@news.eternal-september.org...

The following code might help you out a bit simply because it finds the
intersection point(s) between circles:

https://groups.google.com/group/sci.fractals/browse_frm/thread/8850150ce7584f3

;^)