Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #3167 > unrolled thread

Calculating coordinate intersections?

Back to article view | Back to comp.programming

Contents

  Calculating coordinate intersections? DaveC <invalid@invalid.net> - 2013-03-19 15:17 -0700
    Re: Calculating coordinate intersections? Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2013-03-19 18:26 -0700
      Re: Calculating coordinate intersections? DaveC <invalid@invalid.net> - 2013-03-19 21:53 -0700
        Re: Calculating coordinate intersections? Robert Wessel <robertwessel2@yahoo.com> - 2013-03-20 02:05 -0500
          Re: Calculating coordinate intersections? DaveC <invalid@invalid.net> - 2013-03-20 13:19 -0700
            Re: Calculating coordinate intersections? "BartC" <bc@freeuk.com> - 2013-03-20 21:42 +0000
            Re: Calculating coordinate intersections? Robert Wessel <robertwessel2@yahoo.com> - 2013-03-20 23:48 -0500
    Re: Calculating coordinate intersections? rouben@shady.(none) (Rouben Rostamian) - 2013-03-20 05:27 +0000
      Re: Calculating coordinate intersections? DaveC <invalid@invalid.net> - 2013-03-19 23:39 -0700
        Re: Calculating coordinate intersections? Geoff <geoff@invalid.invalid> - 2013-03-20 00:33 -0700
    Re: Calculating coordinate intersections? James Dow Allen <jdallen2000@yahoo.com> - 2013-03-20 23:41 -0700
      Re: Calculating coordinate intersections? Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2013-03-21 13:18 -0700
        Re: Calculating coordinate intersections? DaveC <invalid@invalid.net> - 2013-03-21 23:02 -0700
          Re: Calculating coordinate intersections? Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2013-03-21 23:28 -0700
      Re: Calculating coordinate intersections? Rui Maciel <rui.maciel@gmail.com> - 2013-03-21 21:40 +0000
        Re: Calculating coordinate intersections? DaveC <invalid@invalid.net> - 2013-03-21 23:03 -0700
          Re: Calculating coordinate intersections? Rui Maciel <rui.maciel@gmail.com> - 2013-03-22 08:36 +0000
            Re: Calculating coordinate intersections? bob <bob@coolfone.comze.com> - 2013-03-22 07:16 -0700
          Re: Calculating coordinate intersections? Geoff <geoff@invalid.invalid> - 2013-03-22 01:49 -0700
    Re: Calculating coordinate intersections? Rui Maciel <rui.maciel@gmail.com> - 2013-03-21 21:26 +0000
      Re: Calculating coordinate intersections? notme <notme@notme.org> - 2013-03-22 00:31 -0700
    Re: Calculating coordinate intersections? "Chris M. Thomasson" <no@spam.invalid> - 2013-03-22 13:08 -0700

Page 1 of 2  [1] 2  Next page →

#3167 — Calculating coordinate intersections?

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.

[toc] | [next] | [standalone]

#3168

On 3/19/13 3:17 PM, DaveC 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?
>
> Ideas?
>
> Thanks.
>

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?

[toc] | [prev] | [next] | [standalone]

#3171

> 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).

[toc] | [prev] | [next] | [standalone]

#3174

On Tue, 19 Mar 2013 21:53:56 -0700, DaveC <invalid@invalid.net> wrote:

>> 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).


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?

[toc] | [prev] | [next] | [standalone]

#3176

> 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

[toc] | [prev] | [next] | [standalone]

#3177

"DaveC" <invalid@invalid.net> wrote in message 
news:0001HW.CD6F67DD007E08C2B04999BF@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 

[toc] | [prev] | [next] | [standalone]

#3178

On Wed, 20 Mar 2013 13:19:25 -0700, DaveC <invalid@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).

[toc] | [prev] | [next] | [standalone]

#3172

In article <0001HW.CD6E31F4003565A0B04999BF@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

[toc] | [prev] | [next] | [standalone]

#3173

> 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?

[toc] | [prev] | [next] | [standalone]

#3175

On Tue, 19 Mar 2013 23:39:05 -0700, DaveC <invalid@invalid.net> wrote:

>> 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?

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.

[toc] | [prev] | [next] | [standalone]

#3179

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

[toc] | [prev] | [next] | [standalone]

#3180

On 3/20/13 11:41 PM, James Dow Allen wrote:
> 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.)

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.

[toc] | [prev] | [next] | [standalone]

#3183

> 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?

[toc] | [prev] | [next] | [standalone]

#3185

On 3/21/13 11:02 PM, DaveC wrote:
>> 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?
>
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.

[toc] | [prev] | [next] | [standalone]

#3182

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

[toc] | [prev] | [next] | [standalone]

#3184

> 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.

Can you please suggest how best to do this?

[toc] | [prev] | [next] | [standalone]

#3187

DaveC wrote:

> Can you please suggest how best to do this?

I've suggested bounding the target with a circle/sphere, represent the shot 
as a line and then check if the shot hit the target by evaluating the 
intersection between the line and the bounding circle/sphere.

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


Hope this helps,
Rui Maciel

[toc] | [prev] | [next] | [standalone]

#3189

On Friday, March 22, 2013 3:36:22 AM UTC-5, Rui Maciel wrote:
> DaveC wrote:
> 
> 
> 
> > Can you please suggest how best to do this?
> 
> 
> 
> I've suggested bounding the target with a circle/sphere, represent the shot 
> 
> as a line and then check if the shot hit the target by evaluating the 
> 
> intersection between the line and the bounding circle/sphere.
> 
> 
> 
> http://en.wikipedia.org/wiki/Line%E2%80%93sphere_intersection
> 
> 
> 
> 
> 
> Hope this helps,
> 
> Rui Maciel

Yes.  In layman's terms, calculate the distance from the center of the sphere to the line.

If it's less than r, there's an intersection.

If it's greater than r, there's no intersection.

If it's r, they're tangent.

[toc] | [prev] | [next] | [standalone]

#3188

On Thu, 21 Mar 2013 23:03:17 -0700, DaveC <invalid@invalid.net> wrote:

>> 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.
>
>Can you please suggest how best to do this?

Here is some 3 dimensional vector handling in C using floating point
vectors. This isn't complete but it illustrates the techniques. This
is how it's done in 3D in the FPS game, Quake 2. You can delete the
third component of the vectors for your 2D game

typedef float vec_t;
typedef vec_t vec3_t[3];

/* compare elements of two vectors, return 1 if they match */

int VectorCompare (vec3_t v1, vec3_t v2)
{
	if (v1[0] != v2[0] || v1[1] != v2[1] || v1[2] != v2[2])
			return 0;
			
	return 1;
}

/* compute the length of a vector and normalize the elements to it */
vec_t VectorNormalize (vec3_t v)
{
	float	length, ilength;

	length = v[0]*v[0] + v[1]*v[1] + v[2]*v[2];
	length = sqrt (length);

	if (length)
	{
		ilength = 1/length;
		v[0] *= ilength;
		v[1] *= ilength;
		v[2] *= ilength;
	}
		
	return length;

}

/* return the dot product v1 . v2 */
/* note the dot product of two vectors is a scalar */
vec_t _DotProduct (vec3_t v1, vec3_t v2)
{
	return v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2];
}

void _VectorSubtract (vec3_t veca, vec3_t vecb, vec3_t out)
{
	out[0] = veca[0] - vecb[0];
	out[1] = veca[1] - vecb[1];
	out[2] = veca[2] - vecb[2];
}

void _VectorAdd (vec3_t veca, vec3_t vecb, vec3_t out)
{
	out[0] = veca[0] + vecb[0];
	out[1] = veca[1] + vecb[1];
	out[2] = veca[2] + vecb[2];
}

void _VectorCopy (vec3_t in, vec3_t out)
{
	out[0] = in[0];
	out[1] = in[1];
	out[2] = in[2];
}

/* v1 x v2, return product in cross, the cross */
/* product of two vectors is a vector normal to the v1,v2 plane */
void CrossProduct (vec3_t v1, vec3_t v2, vec3_t cross)
{
	cross[0] = v1[1]*v2[2] - v1[2]*v2[1];
	cross[1] = v1[2]*v2[0] - v1[0]*v2[2];
	cross[2] = v1[0]*v2[1] - v1[1]*v2[0];
}

void VectorInverse (vec3_t v)
{
	v[0] = -v[0];
	v[1] = -v[1];
	v[2] = -v[2];
}

void VectorScale (vec3_t in, vec_t scale, vec3_t out)
{
	out[0] = in[0] * scale;
	out[1] = in[1] * scale;
	out[2] = in[2] * scale;
}

[toc] | [prev] | [next] | [standalone]

#3181

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

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.programming

csiph-web