Circle embedded in line-- fastest vector to unembed

I don't know if this is very different from what you have, but it feels more natural to me:

Vector ray_direction = p2 - p1;
Vector normal(-ray_direction.y, ray_direction.x);
Vector from_p1_to_pt = pt - p1;
Vector move_direction = normal * dot_product(normal, from_p1_to_pt);
normalize(move_direction);

Sadly, that's pretty close to what I have. I was hoping there was some method of figuring it out without that "normalize." I'm using this to potentially, at worst case, unembed a whole lot of things, so I want it to be as efficient as possible, and without sqrt.

If you want the resulting vector to have length 1, there is no way of avoiding the normalization. Here's a proof:

Vector cheap_normalize(Vector v) {
  Vector pt = v;
  double radius = Infinity;
  Vector p1(-v.y, v.x);
  Vector p2 = -p1;
  
  return unembed(pt, radius, p1, p2)
}

You could try some tricks to normalize faster: http://en.wikipedia.org/wiki/Fast_inverse_square_root

Sadly, that's pretty close to what I have. I was hoping there was some method of figuring it out without that "normalize." I'm using this to potentially, at worst case, unembed a whole lot of things, so I want it to be as efficient as possible, and without sqrt.

This sounds like a terrible case of pre-optimizations. A sqrt is probably not going to be your worst bottleneck in your code. If you are experiancing slow downs, use real profileres to find where you are slowing down, you are far more likely to run into issues with cache misses/coherency then you are to worry about a little sqrt.

Edit: apparantly johnny is not into this advice, and deceided i was worth down voting over it, carry on doing w/e u want then.

?? Every cycle's sacred... every cycle's good... every cycle's wanted, in my neighborhood... ?

However, I don't need it PERFECTLY normalized... I just need it pretty close to one. I wonder what tricks I can do by multiplying my vectors by huge numbers, so they approach infinity, and then divide them by eachother. That might work for my resolution.

I don't know if this is very different from what you have, but it feels more natural to me:

Vector ray_direction = p2 - p1;
Vector normal(-ray_direction.y, ray_direction.x);
Vector from_p1_to_pt = pt - p1;
Vector move_direction = normal * dot_product(normal, from_p1_to_pt);
normalize(move_direction);

Does this work? I'm trying to figure out why you would multiply a vector by a dot product, and then immediately normalize it. I don't see how that would change its direction.

Does this work? I'm trying to figure out why you would multiply a vector by a dot product, and then immediately normalize it. I don't see how that would change its direction.

I am only interested in the sign of the dot product. Does that make things more clear?

Square root maps to hardware and its fast. There are tricks to calculate inverse of square root but those might ends up to be slower these days.

http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/

There are tricks to calculate inverse of square root but those might ends up to be slower these days.

I was interested in the time difference between the two, and that way is surprisingly much much faster: http://ideone.com/6iUX2P

however, once i ran it on my own pc, the two are basically the same with no optimizations(sqrt is actually faster):

Resolution: 10000000
Time Taken for 1/sqrt(i): 0.0360257 seconds. Total Sum: 1997.9
Time Taken for InvSqrt(i): 0.0370257 seconds. Total Sum: 1996.03

but with optimizations, once again the fast InvSqrt beats 1/sqrt with a pretty high degree of improvement:

Resolution: 10000000
Time Taken for 1/sqrt(i): 0.0070153 seconds. Total Sum: 1997.9
Time Taken for InvSqrt(i): 0.0020014 seconds. Total Sum: 1996.03

however, we are talking about a fraction of a second, over a million iterations to see such differences, and at the cost of a minor bit of accuracy. i still think overall 1/sqrt is much simplier than this other method.

edit: actually, i also realize their's apparantly a minor diffrence in the results between ideone, and my pc, even though they are running the exact same code(although maybe the sqrt implementation might be diffrent, that InvSqrt is the same, yet here is a diffrence between the two?)

however, we are talking about a fraction of a second, over a million iterations to see such differences, and at the cost of a minor bit of accuracy. i still think overall 1/sqrt is much simplier than this other method.

Yeah, that's not enough to matter for my purposes. It's more that I was wondering if there was some completely alternate way of doing it that I might be missing out on-- you know, like all those nice tricks you can do with dot and cross products.

For my specific purposes-- direction toward/away from infinite line from a particular point, I hoped their might be some common equation that I was ignorant of, rather than "find closest point, normalize vector." That WORKS, but again, sometimes there's cute tricks, and that's what I was hoping for.

You said require a unit vector. Intuitively, I don't see how you'd get one without normalization.

Now, if you wanted to push out your circle with a strength that depended on how "embedded" it was in the line, then you might be able to figure out some trick that avoided normalization.

Hi all,

This is for 2D...

Say I have a circle at Point pt, with radius r ...

And I have a line that goes from Point p1 to Point p2.

Assuming the circle is embedded in the line, I want to know-- as fast as possible, without normalizes, etc, if that's even possible-- what direction to push my circle in to unembed it most efficiently.

I currently have a pretty simple method where I do this:

1. Find closest point on line to center of circle

2. Take vector of that to center of circle and normalize it

3. Move circle in that direction.

Is there a faster, math wizardy way?

Thanks!

No, definitely not.

Speed will come from the context of the collision detection code (i.e. your memory usage, or the algorithm calling the collision detection), and not so much from the actual collision detection function.

So optimizing the function beyond removing unnecessary if-statements and normalization won't really accomplish anything.

As for the inverse sqrt, some machines have their own sqrt intrinsics (like fsqrt or _mm_sqrt_ps), and so doing software inv square roots may just slow you down.

Edit: Math derivation for this kind of problem: http://www.randygaul.net/2014/07/23/distance-point-to-line-segment/

I am only interested in the sign of the dot product. Does that make things more clear?

Yes, thanks.

I'm still curious if it is correct to always move in the direction of the normal of the line segment. For example, if p1 == p2, there's still a best direction. But I was missing something with the sign, so I could also be missing something else.

Edit: oh, maybe I'm missing that it is just a "line" instead of a segment. From the description, I'm not sure. It uses the word line but describes it as a line that goes from one point to another, which I pictured as a segment.

Edit: oh, maybe I'm missing that it is just a "line" instead of a segment. From the description, I'm not sure. It uses the word line but describes it as a line that goes from one point to another, which I pictured as a segment.

1. A straight line segment can be drawn joining any two points.
2. Any straight line segment can be extended indefinitely in a straight line.
[...]