nearest line

[walnoot]

Let's say you dynamically draw 50 lines on the stage.

I'd like to know how to check which of these lines is the nearest to a certain point (e.g. the mousepointer). And ofcourse I'd like to know the fastest way.

I'm starting to understand it, but I need a little help to really get it.

What I understand is that the point on a linesegment closest to a certain point is the intersectionpoint of the perpendicular line between the "certain point" and the line.

But I can't think of an easy way to calculate this.

Anyone?

Thanks in advance!

[andreaskrenmair]

Hi,

you have to calculate the minimal distance from this point to your line. I will explain it for one line.

Let´s assume you have two points on your line: (px1,py1) and (px2, py2) and your point (x, y).

The first thing we have to do is to calculate the vector of the line:

vx = px1 - px2 and vy = py1 - py2

So we have the vecor of the line. Now we take the normal of the vector:

nvx = -vy
nvy = nvx

So we have the vector that is normal to out line. With our point (x,y) we form another line and cross it with the actual line (the one where we want to know its distance to the point).

The other line looks this way:

(x,y) + t * (nvx,nvy)

That is a form called parameter form. A line is represented with a point and a vector in the parameter form. The paremeter t is not specified and can be any value.

After we have crossed the two lines we get an intersection point (ix, iy). Then we have to calculate the vector from our point (x,y) to the intersection point (ix, iy):

dx = x - ix
dy = y - iy

Finally we calculate the length of the vector Math.sqrt(dx*dx+dy*dy) and we have the shortest distance from our point (x,y) to our line.

Just do this for the other lines and compare the distance to current shortest distance.

If anything is unclear, just ask.

[strille]

Finally we calculate the length of the vector Math.sqrt(dx*dx+dy*dy) and we have the shortest distance from our point (x,y) to our line.

Also, remember that if you just want to know which line is closest to the point you can skip the square root. And if you need to know the distance to the closest line you can calculate the square root when you know which is closest. Will speed it up quite a bit.

[walnoot]

Hi! thanks for replying.

I fully understand the theory as you explain,
but could you explain how to solve an equation with parameter form?
Will the equation look like this ? ->

(x,y) + t * (nvx,nvy) = (px1,pxy1) + t * (vx,vy)

I don't have a clue where to start solving this.

Really appreciate your help.

Thanks strille, allthough I was aware of that.

[andreaskrenmair]

Hi,

actually every line has a different parameter. So the equation looks like this:

(x,y) + t * (nvx,nvy) = (px1,pxy1) + u * (vx,vy).

So you would split it up into x and y:

x + t * nvx = px1 + u * vx
y + t * nvy = py1 + u * vy

Then solve the two equations - get t and u and use one of them to calculate the intersection point:

use the result of t and apply it in (x,y) + t * (nvx,nvy) :

ix = x + (value of t) * nvx
...

So we have to solve an equation with two variable in flash. So I have to admit I have no clue how to do this in flash, but there is a workaround:

Instead of using the parameter form we can use the implicit form:

y = k * x + d

So we have our points on the line (px1,py1) and (px2, py2)

k = y/x

So lets calculate k:

k = (py1 -py2)/(px1 - px2)

Then use one of the wo points and use their x and y values to calculate d:

d = py1 - k * px1

Now we have the first equation of our line. So lets calculate the normal: We have to use the inverse of our current k:

k_normal = - ((px1 - px2)/(py1 -py2))

Then use your point (x,y) to complete the implicit form of our normal:

d_normal = y - k_normal * x

So now we can calculate the intersection point:

ix = (d_normal-d)/(k-k_normal);
iy = k * ix + d

That´s it ( I have not tested it in Flash, but it should work). If someone has a good solution for the parameter form please let us know.

[walnoot]

I see, I think I can work things out with this.
I'm very grateful to your extended replies,
and actually feel bad I can't draw out the thank-word any longer than 4 lines.
Thanks again.