does anyone have any ideas or even some code on how to find a location of a point, which is a certain amount of units away from two line segments? here's a little picture to clear up any confuzion. note that the two line segments don't have to touch each other, and the minumal distance between two points lying on the two segments will always be less that double the "certain distance". that means such a point is possible. and in case if the two line segments are lying on the same line, it should report that (since there are two possible points in that case) as n/a. thank you very much in advance! --- shurcool my project [edited by - shurcool on June 24, 2002 2:57:23 PM]

you can solve using the following

the vectorial form of a line is p + tv (p - point, v - vector, t - scalar variable)
the distance between point A to line(P + tv) is |v x AP| / |v|.

given lines a (ap +t*av), b (bp +t*bv) and distance c, you can find your point P solving the following equation:

quote:
|av x apP|/|av| = |bv x bpP|/|bv| = c

*passes out*

i'm sorry, but i don't know vector math that well, and i don't know what |v x AP| / |v| means (what are |'s for?). could you please write more c++ code, because i don't know what mathematical symbols mean (i'm only in grade 10), such as .Cross or .Dot, etc.

thank you very much!

---
shurcool
my project

[edited by - shurcool on June 24, 2002 4:15:38 PM]

I don't have much free time so I'll give it to you straight and to the point... no explanations today sorry...

Assume you have two lines given by the equations

y = m1x + c1y = m2x + c2   

and a point (with unknown coordinates) a distance 'r' from both lines (r is taken as the distance along the normal from the unknown point to each line, as in shurcool's diagram, 'certain distance').

Compute:

theta1 = atan(m1)theta2 = atan(m2)   

Then the x coordinate of the point you want is given by

       x = (c2-c1)/(m1-m2) + r(1/|cos(theta2)| - 1/|cos(theta1)|)/(m1-m2)   

where |cos(theta)| means the Absolute value: sqrt(cos(theta)*cos(theta))

and the y coordinate is given by

y = m1x + c1 + r/(|cos(theta1)|)   

Good luck,

Timkin

[edited by - Timkin on June 24, 2002 12:23:29 AM]

quote:Original post by Tjoppen
Isn't this stuff pretty basic...
The two lines can be considered two planes in 2D, meaning you just compute the dotproduct point - line1 and point - line2.
But you'd have to calc the normal and distance of the two planes too, but that isn't an especially hard task.

Yes... and when you've done that... and you simplify the maths... you get an easier method... which I posted the answer for above.

Here's the explanation now that I have more time...

Since the point is a constant distance from each line then you can consider two new lines - each parallel to the given lines - that intersect at the unknown point. If r is the distance away from the given line that the point lies, then you need to move the line a distance of r/|cos(theta)| units up or down (add for up, subtract for down), where theta is the angle between the given line and the x axis (tan(theta) = gradient).

So move both lines that distance and simply solve for the point of intersection... which is what I did... and gives the answer I gave... and it's using maths that a 10th grader will understand, since that is the restriction that shurcool placed on the problem.

Simple, isn't it!

Cheers,

Timkin

[edited by - Timkin on June 25, 2002 4:25:01 AM]

quote:Original post by Timkin
and it''s using maths that a 10th grader will understand, since that is the restriction that shurcool placed on the problem.

no no no! i said i''m grade 10, which is why i don''t know what |''s mean (something about matrices, right?), but that doesn''t mean that a more advanced solution is bad. as long as i know how to do it using c++ vector function, i''m ok for now. in a year or so when i''ll learn vector math, i will be able to go back and more thoroughly underdstand the principles behind it, but for now the fastest and more optimized solution is what i''m looking for. Timkin, you solution is exactly what i had in mind, but i didn''t think it was too optimized, because u''d need to find length of two lines, move them by ''certain distance'' up or down (also have to calculate what direction to move), and find their intersection point. what i was hoping for is that there would be a way to accomplish that using the fancy vector math functions (exactly what Tjoppen outlined), such as dot or cross product, etc. that are easy to implement in c++. thank you all for your solutions too, they are greately appreciated. i will show you the results (it''s for a collision handling demo i posted here not so long ago) as soon as they''re ready, so you''ll know you didn''t waste your time and effort for nothing. thanks again,
shurcool

---
shurcool
my project

quote:Original post by shurcool
no no no! i said i'm grade 10, which is why i don't know what |'s mean (something about matrices, right?)

No, I gave the definition above: |a| = sqrt(a*a)

quote:Original post by shurcool
Timkin, you solution is exactly what i had in mind, but i didn't think it was too optimized

It's more optimal than you'd think!

quote:Original post by shurcool
, because u'd need to find length of two lines, move them by 'certain distance' up or down (also have to calculate what direction to move), and find their intersection point.

No! You don't need to do any of that. That's all done in working out the answer that I gave above. You just apply the answer to whatever pair of lines and single point you have!!! All the rest of the computations are uncessary.

quote:Original post by shurcool
what i was hoping for is that there would be a way to accomplish that using the fancy vector math functions

A word of advice to anyone reading this... don't use fancy maths when something simpler is available!


To spell it out for you shurcool...


You wanted to know the coordinates of the point that was a certain distance away from two separate lines. Here's the answer:


You have two lines in your picture.

The first line has equation: y = m1x + c1

and the second line has equation: y = m2x + c2


If your lines are not in that form (but are just two points), you can trivially transform whatever representation you have into the equations above. For example, if a line is given by two points (x1,y1) and (x2,y2), then it has an equation for that line of

y = m*x + c

where m = (y2-y1)/(x2-x1)
and c = y2 - m*x2

So, you should be able to work out the two equations for your lines.


You need some other information: the angle each line makes with the x axis. That's trivial if you know the gradient of the line, m.

So:

theta1 = tan-1(m1) = atan(m1)
theta2 = tan-1(m2) = atan(m2)


Now, you also have a point at an unknown coordinate (xp,yp). It lies a distance r away from your two lines. I assume that you know r, since it's something you choose!

So, you know r, m1, m2, c1, c2, theta1 and theta2.

Just plug them into this formula!

xp = (c2-c1)/(m1-m2) + (r/(m1-m2))*(1/|cos(theta2)| - 1/|cos(theta1)|)yp = m1xp + c1 + r/(|cos(theta1)|)   

Now, just to make sure everything works well, you make r positive if the point is above the two lines and negative if its below the two lines.

And that's all there is to it! No fancy maths needed. Just fast, quick substitution!

Next time, please make sure you read and understand someones response before dismissing it.

Timkin
[EDITED to make equations more readable]

[edited by - Timkin on June 25, 2002 9:29:53 PM]

ok, two quick things i want to say.

first of all, if |x| = sqrt(x * x), then... what's the point? it's like saying `y` = y + 1 - 1. or is there something i'm missing? (does it have something to do with it being possible to represent the number in 1/z format, because i know that it isn't for pi, for example... i think)
[edit] ah... absolute value... abs(). :) gotcha. [/edit]

and gradient for a vertical line would be infinity. how would i represent it in float format? would a really high number do (max number that can fit in float), or is there a better way around it?

thanks a lot for your thorough responce, i guess it i just replied really fast before i real all responces thoroughly. :-\ sorry...

oh, one more quick question...

Quote:Now, just to make sure everything works well, you make r positive if the point is above the two lines and negative if its below the two lines.

but i don't know if it will be above or below, there's always only one possibility, unless the two line segments line on same line (2d plane). so i guess i would have to figure it out, right?

[Edited by - shurcool on August 21, 2006 10:22:02 AM]

quote:Original post by shurcool
and gradient for a vertical line would be infinity. how would i represent it in float format? would a really high number do (max number that can fit in float), or is there a better way around it?

Okay, if you''re likely to be working with vertical lines, then you need to take care. Obviously, for a vertical line defined by two points, the x values are the same... so you have an easy test for this situation.

I take it that your lines ARE defined by two points???

Let''s asume that one line is vertical. Call it line 1. It''s equation is given by x = c1.

The other line has equation y = m2x + c2

So, the point you are looking for has coordinates

xp = c1 + r
yp = m2xp + c2 + r/|cos(theta2)|

If perchance both lines are vertical (or both are parallel) then you cannot solve the problem as there are an infinite number of points that lie an equal distance from both lines... i.e., the line half way between the two lines.

quote:Original post by shurcool

Now, just to make sure everything works well, you make r positive if the point is above the two lines and negative if its below the two lines.

but i don''t know if it will be above or below, there''s always only one possibility, unless the two line segments line on same line (2d plane). so i guess i would have to figure it out, right?

Actually, there are 4 possibilities, but you only want the one that depends on how the line is clipped. I''ll need to give this some more thought tomorrow… it''s 10pm and I really should be leaving the office to get home!

Cheers,

Timkin