I need to write an algorithm to calculate the distance between a line and a point. Have you done such as a algorithm?

You can go to this link if you dont understand what I mean:

http://www.allegro.cc/forums/thread/589720

thanks..

It looks like you're new here. If you want to get involved, click one of these buttons!

- 140.8K All Categories
- 103.6K Programming Languages
- 6.4K Assembler Developer
- 401 Assembly Code Share
- 239 Getting started in assembly
- 4.6K x86 Assembly
- 1.9K Basic
- 97 Qbasic
- 39.9K C and C++
- 5.6K Beginner C/C++
- 330 C/C++ on Linux/Unix
- 450 C/C++ Windows API
- 522 C++ Builder
- 253 C++ Game Development
- 3.3K C++ MFC
- 103 C++.NET
- 404 Visual C++
- 2.9K C#
- 7.9K Delphi and Kylix
- 334 Advanced Delphi
- 360 Delphi beginners
- 4 Haskell
- 9.7K Java
- 56 Enterprise JavaBeans
- 1.3K Java Beginners
- 304 Java Server Pages
- 4.1K Pascal
- 1.3K Perl
- 11 Perl 6
- 2K PHP
- 546 Python
- 37 Ruby
- 4.4K VB.NET
- 258 Advanced VB.Net
- 1.6K VBA
- 20.8K Visual Basic
- 767 Access databases and VB
- 831 Advance Visual Basic
- 1.2K Beginner VB
- 2.6K Game programming
- 315 Console programming
- 90 DirectX Game dev
- 1 Minecraft
- 112 Newbie Game Programmers
- 2 Oculus Rift
- 9K Applications
- 1.8K Computer Graphics
- 279 3D Graphics
- 129 DirectX
- 125 OpenGL
- 740 Computer Hardware
- 9 Cooling & Overclocking
- 3.4K Database & SQL
- 1.1K Access
- 91 ADO Programming
- 288 MySQL
- 358 Oracle
- 440 SQL-Server
- 535 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 25 DirectSound
- 257 XML Development
- 3.3K Classifieds
- 199 Co-operative Projects
- 198 For sale
- 190 FreeLance Software City
- 1.9K Jobs Available
- 603 Jobs Wanted
- 209 Wanted
- 2.9K Microsoft .NET
- 1.8K ASP.NET
- 1.1K .NET General
- 22 .NET WEB-Services
- 129 .NET WinForms
- 14 .NET XML
- 50 ADO.NET
- 142 C# & VB.NET School Support
- 3.4K Miscellaneous
- 8 Join the Team
- 354 Comments on this site
- 69 Computer Emulators
- 2.1K General programming
- 187 New programming languages
- 621 Off topic board
- 200 Mobile & Wireless
- 72 Android
- 126 Palm Pilot
- 338 Multimedia
- 154 Demo programming
- 184 MP3 programming
- 0 Bash scripts
- 27 Cloud Computing
- 1 Witsbits Go Cloud
- 53 FreeBSD
- 1.7K LINUX programming
- 1 Awk scripting
- 332 Linux Support
- 0 Sed scripting
- 370 MS-DOS
- 0 Shell scripting
- 321 Windows CE & Pocket PC
- 4.1K Windows programming
- 177 COM/DCOM
- 61 Networking And Security
- 17 Windows 2003 Server
- 6 Windows Vista
- 176 Windows XP
- 939 Software Development
- 416 Algorithms
- 68 Object Orientation
- 24 RUP & UML
- 91 Project Management
- 95 Quality & Testing
- 268 Security
- 63 Evil Scripting
- 81 Hacking
- 7.7K WEB-Development
- 1.8K Active Server Pages
- 61 AJAX
- 4 Bootstrap Themes
- 55 CGI Development
- 28 ColdFusion
- 224 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 131 Mobile Internet & Messaging
- 211 Wireless development
- 2.2K JavaScript
- 37 JQuery
- 304 WEB Servers
- 153 Apache
- 79 IIS
- 150 WEB-Services / SOAP

## Comments

Sure.

: You can go to this link if you dont understand what I mean:

: http://www.allegro.cc/forums/thread/589720

Why not use the code over there?

Or else: what is your problem in writing the code? What is your code now?

See ya,

bilderbikkel

:

: I need to write an algorithm to calculate the distance between a line and a point. Have you done such as a algorithm?

:

: You can go to this link if you dont understand what I mean:

: http://www.allegro.cc/forums/thread/589720

:

: thanks..

:

Smallest distance between a line and a point is the line drawn from the point perpendicular to the line.

Say for the line you have the equation y = ax + b, in two dimensions.

Now for a little bit of Lineair Algebra. If you shift the line so that at x = 0, y = 0, the line is given by the vector (1, a). Meaning for each 1 step to the right, take 'a' steps up.

For the point, p, we have p = (p1, p2) as it's coordinates.

Now we shifted our line to go through the origin so we should do the same with p. We shifted the line down by b, so p becomes p = (p1, p2 - b)

Now there are two ways of doing this... one is elegant, but makes no sense at all if you're not familar with it.

The other is continuing in the geometry way.

Let's start with the elegant one:

If we have a line, and we consider the point as a vector, reaching out from the origin to this point, we can seperate this new vector into two components: one parallel to the line and one perpendicular to it.

The parallel component is called a projection of the vector onto a line (or onto another vector if you will). The vector that describes the line I will call l. |p| denotes the length of the vector |p|

[code]

proj p = ( |p| Cos t ) (l / |l|)

[/code]

t is the angle between p and l. If you just look at the first part |p| Cos t then you recognise that you are using goniometrics to calculate the side of a triangle. The second part l / |l|, is basically to give the projection a direction. The first part is just a number, the length of that side, but that side also has a direction, which is the same as the direction of l. So multiplying it by l reduced to length 1, which is l / |l| will add the proper direction without changing the length.

The definition of the dot product is u . v = |u| |v| Cos t

So proj p becomes:

[code]

proj p = (( p . l ) / |l|) (l / |l|) = ( p . l ) (l / l.l)

[/code]

l.l = |l|^2, (Cos t = 1, t = 0 because l and l are the same line)

So applying this to our problem we have:

[code]

proj p = ( p . l ) (l / l.l)

p =

l = <1, a>

proj p = (p1 + ap2 - ab) / (1 + a^2) <1, a>

[/code]

We split up the vector into a parallel and orthogonal component. We are actually interested in the orthogonal component because that is the length. This is given by p - proj p

[code]

length = p - proj p

= - (p1 + ap2 - ab) / (1 + a^2) <1, a>

= <(ab - ap2) / (1 + a^2),

(p2(1 - a^2) - b + b*a^2 + ap1) / (1 + a^2) >

distance = |length|

= Sqrt[ (ap2 - ab) / (1 + a^2))^2 +

((p2(1 - a^2) - b + b*a^2 + ap1) / (1 + a^2))^2 ]

[/code]

Ok so it aint pretty But it's a very systematic way of handling and that's where it gets it's elegance.

The way of Geometry:

You're looking for a line that is perpendicular to the line given. Now when you picture it in your head, you'll see that a line perpendicular would be to take 'a' steps up, and 1 step to the left. Meaning it is given by the vector (a, -1) or (-a, 1) (for our purposes here, both are good).

A more mathematical way of looking at this, is using the dot product, which becomes 0 if and only if the vectors are perpendicular to eachother. (1, a) . (p, q) = 1*p + a*q = 0

Thus p = -aq and so the vector becomes (-aq, q) or (-a, 1) for q = 1.

So we have -ay = x for our line -> y = -x / a

Now we have to place it correctly: shift it up or down till it goes through p.

[code]

p2 = -p1 / a + z

z is our shift

z = p2 + p1 / a

[/code]

Now find where it intersects with our original line.

[code]

-x / a + p2 + p1 / a = ax + b

x = (p1/a + p2 + b) / (a + 1/a)

y = (p1 + ap2 + ab) / (a + 1/a) + b

Length^2 = ((p1 + ap2 + ab) / (a + 1/a) + b - p2)^2 +

((p1/a + p2 + b) / (a + 1/a) - p1)^2

[/code]

Take the square root and you're all done.

Now I really do not know if I made mistakes or not.. ofcourse I like to think I didn't, but...

Anyway, I assumed this kind of explanation is what you wanted since the link you specified contained all the sourcecode.

Best Regards,

Richard

: :

: : I need to write an algorithm to calculate the distance between a line and a point. Have you done such as a algorithm?

: :

: : You can go to this link if you dont understand what I mean:

: : http://www.allegro.cc/forums/thread/589720

: :

: : thanks..

: :

:

: Smallest distance between a line and a point is the line drawn from the point perpendicular to the line.

: Say for the line you have the equation y = ax + b, in two dimensions.

:

: Now for a little bit of Lineair Algebra. If you shift the line so that at x = 0, y = 0, the line is given by the vector (1, a). Meaning for each 1 step to the right, take 'a' steps up.

:

: For the point, p, we have p = (p1, p2) as it's coordinates.

: Now we shifted our line to go through the origin so we should do the same with p. We shifted the line down by b, so p becomes p = (p1, p2 - b)

:

: Now there are two ways of doing this... one is elegant, but makes no sense at all if you're not familar with it.

: The other is continuing in the geometry way.

:

: Let's start with the elegant one:

: If we have a line, and we consider the point as a vector, reaching out from the origin to this point, we can seperate this new vector into two components: one parallel to the line and one perpendicular to it.

: The parallel component is called a projection of the vector onto a line (or onto another vector if you will). The vector that describes the line I will call l. |p| denotes the length of the vector |p|

: [code]

: proj p = ( |p| Cos t ) (l / |l|)

: [/code]

: t is the angle between p and l. If you just look at the first part |p| Cos t then you recognise that you are using goniometrics to calculate the side of a triangle. The second part l / |l|, is basically to give the projection a direction. The first part is just a number, the length of that side, but that side also has a direction, which is the same as the direction of l. So multiplying it by l reduced to length 1, which is l / |l| will add the proper direction without changing the length.

: The definition of the dot product is u . v = |u| |v| Cos t

: So proj p becomes:

: [code]

: proj p = (( p . l ) / |l|) (l / |l|) = ( p . l ) (l / l.l)

: [/code]

: l.l = |l|^2, (Cos t = 1, t = 0 because l and l are the same line)

:

: So applying this to our problem we have:

: [code]

: proj p = ( p . l ) (l / l.l)

: p =

: l = <1, a>

:

: proj p = (p1 + ap2 - ab) / (1 + a^2) <1, a>

: [/code]

:

: We split up the vector into a parallel and orthogonal component. We are actually interested in the orthogonal component because that is the length. This is given by p - proj p

:

: [code]

: length = p - proj p

: = - (p1 + ap2 - ab) / (1 + a^2) <1, a>

: = <(ab - ap2) / (1 + a^2),

: (p2(1 - a^2) - b + b*a^2 + ap1) / (1 + a^2) >

:

: distance = |length|

: = Sqrt[ (ap2 - ab) / (1 + a^2))^2 +

: ((p2(1 - a^2) - b + b*a^2 + ap1) / (1 + a^2))^2 ]

: [/code]

:

: Ok so it aint pretty But it's a very systematic way of handling and that's where it gets it's elegance.

:

: The way of Geometry:

:

: You're looking for a line that is perpendicular to the line given. Now when you picture it in your head, you'll see that a line perpendicular would be to take 'a' steps up, and 1 step to the left. Meaning it is given by the vector (a, -1) or (-a, 1) (for our purposes here, both are good).

: A more mathematical way of looking at this, is using the dot product, which becomes 0 if and only if the vectors are perpendicular to eachother. (1, a) . (p, q) = 1*p + a*q = 0

: Thus p = -aq and so the vector becomes (-aq, q) or (-a, 1) for q = 1.

:

: So we have -ay = x for our line -> y = -x / a

: Now we have to place it correctly: shift it up or down till it goes through p.

: [code]

: p2 = -p1 / a + z

: z is our shift

: z = p2 + p1 / a

: [/code]

:

: Now find where it intersects with our original line.

: [code]

: -x / a + p2 + p1 / a = ax + b

: x = (p1/a + p2 + b) / (a + 1/a)

: y = (p1 + ap2 + ab) / (a + 1/a) + b

:

: Length^2 = ((p1 + ap2 + ab) / (a + 1/a) + b - p2)^2 +

: ((p1/a + p2 + b) / (a + 1/a) - p1)^2

: [/code]

: Take the square root and you're all done.

:

: Now I really do not know if I made mistakes or not.. ofcourse I like to think I didn't, but...

: Anyway, I assumed this kind of explanation is what you wanted since the link you specified contained all the sourcecode.

:

: Best Regards,

: Richard

:

:

Thanks. I just wanted another opinion just to make sure