469,945 Members | 1,794 Online

# regarding algorithim

Hi

I want to find an algorithim , which calculates shortest perpendicular
distance from a given point to a line.

Thanks

Mohan
Nov 14 '05 #1
14 1260
invincible wrote:
Hi

I want to find an algorithim , which calculates shortest perpendicular
distance from a given point to a line.

This is obviously *not* a problem related to the C programming language,
and so if *not* a question for comp.lang.c
<ot>
Just to get you started, the distance from (x0,y0) to the line ax+by+c=0
is fabs((a*x0+b*y0+c)/sqrt(a*a+b*b)). This is elementary math. If you
can't derive that for yourself, drop your programming course and take
the math you should have learned already.
</ot>
Nov 14 '05 #2
On Mon, 4 Apr 2005 12:20:15 +0530, "invincible"
<mo**********@in.bosch.com> wrote in comp.lang.c:
Hi

I want to find an algorithim , which calculates shortest perpendicular
distance from a given point to a line.

Thanks

Mohan

You're in luck.

Just find ANY perpendicular distance from a given point to a line. It
will be the shortest, since there is only one.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html
Nov 14 '05 #3
In article <3i********************************@4ax.com>,
Jack Klein <ja*******@spamcop.net> wrote:
Just find ANY perpendicular distance from a given point to a line. It
will be the shortest, since there is only one.

a) That depends on which geometry you are operating in;
b) Even within the geometry you were probably thinking of, there
are usually -two- answers... one of which is infinite,
c) The equation that was posted goes unstable as
a**2+b**2 approaches 0.
--
"This was a Golden Age, a time of high adventure, rich living and
hard dying... but nobody thought so." -- Alfred Bester, TSMD
Nov 14 '05 #4
thanks a lot for ur reply..........
"Martin Ambuhl" <ma*****@earthlink.net> wrote in message
invincible wrote:
Hi

I want to find an algorithim , which calculates shortest perpendicular
distance from a given point to a line.

This is obviously *not* a problem related to the C programming language,
and so if *not* a question for comp.lang.c
<ot>
Just to get you started, the distance from (x0,y0) to the line ax+by+c=0
is fabs((a*x0+b*y0+c)/sqrt(a*a+b*b)). This is elementary math. If you
can't derive that for yourself, drop your programming course and take
the math you should have learned already.
</ot>

Nov 14 '05 #5
On 5 Apr 2005 03:32:22 GMT, in comp.lang.c ,
ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote:
In article <3i********************************@4ax.com>,
Jack Klein <ja*******@spamcop.net> wrote:
Just find ANY perpendicular distance from a given point to a line. It
will be the shortest, since there is only one.

a) That depends on which geometry you are operating in;
b) Even within the geometry you were probably thinking of, there
are usually -two- answers... one of which is infinite,
c) The equation that was posted goes unstable as
a**2+b**2 approaches 0.

Er, if a^2+b^2 is zero, you don't have a line.

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
Nov 14 '05 #6
In article <q0********************************@4ax.com>,
Mark McIntyre <ma**********@spamcop.net> wrote:
On 5 Apr 2005 03:32:22 GMT, in comp.lang.c ,
ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote:
c) The equation that was posted goes unstable as
a**2+b**2 approaches 0. Er, if a^2+b^2 is zero, you don't have a line.

The equation that was posted used 'fabs', thus
indicating actual implimentation code rather than
indicating the mathematical formula for the solution.
Consider ax + by + c = 0 under the condition that
c = 0; then if a = -b, then the line is x = y
provided that a (and hence be) are not themselves 0.
Now, let |a| < sqrt(DBL_MIN) [if working with doubles]
or |a| < sqrt(FLT_MIN) [if working with float].
If one is working with float and one's FLT_MIN is
the common ~1.175E-38 then the posted equation would
bomb for |a| < ~1E-20 even though the formula's
answer should be the same as if a = 1, b = -1, c = 0.
Notice too that I said "goes unstable" as that term "approaches 0", not
as it -became- 0. When a and b are very small, the sum of their
squares approaches 0 quickly, so dividing anything by that sum is going
to lose precision and the division's represented answer is going to
"blow up" when small changes are made to a and b.

Just find ANY perpendicular distance from a given point to a line. It
will be the shortest, since there is only one.

would tend to imply that any old formula would do, but in actuality
one must be quote careful how one calculates the answer if one wishes
to be able to work with very small a and b.
A number of years ago, part of our interviews involved a question with
finding and implimenting the answer to a geometric problem. For the
most part, the responses were pretty pathetic: university CS grads [who
had had to take first year university calculas and algebra] were often
unable to complete the required short (10 line) program within one
hour, even though the problem involved no more than grade 10 level
geometry.

We did have one candidate who had no problem finding the solution and
programming it up in a short time, easily seeing it for the fairly
trivial math programming question that it was. The candidate happened
to overlook that the formula degenerated to 0/0 in one case. That
wasn't a big deal at all considering the ease in which they'd gotten
through everything. On the other hand, the candidate ruined everything
by insisting on arguing when we pointed out the simple overlook,
insisted that because calculas showed that the formula limit approached
1 from both sides, that the answer *was* 1 and that therefore they
deemed their program to be correct. Overlooking the small problem that
their program was going to crash on that input, not give particular

If the candidate had said "Duh, of course. I overlooked that but I'll
be more careful in future," then the candidate might well have gotten
the job... but instead the candidate showed that the candidate's ego
ability or willingness to work with the reality of computer
implimentation limitations. And our work is in the reality of
numeric instabilities and bad signal to noise ratios, not in fields
where there is a Right Answer...
--
Would you buy a used bit from this man??
Nov 14 '05 #7
Walter Roberson wrote:
The equation that was posted used 'fabs', thus
indicating actual implimentation code rather than
indicating the mathematical formula for the solution.
Bullshit. What I posted was<ot>
Just to get you started, the distance from (x0,y0) to the line
ax+by+c=0 is fabs((a*x0+b*y0+c)/sqrt(a*a+b*b)). This is elementary
math. If you can't derive that for yourself, drop your programming
course and take the math you should have learned already.
</ot>

I have posted "actual implementation [spelt thus] code" many times here.
It is always posted in the form of complete, compilable code. It also
is not part of a sentence begining "Just to get you started." I know
that you have been trolling^W posting here for a short time, but there
is no excuse for your poor imitation of Carnack.

Nov 14 '05 #8
Walter Roberson wrote:
The equation that was posted used 'fabs', thus
indicating actual implimentation code rather than
indicating the mathematical formula for the solution. Bullshit. What I posted was Just to get you started, the distance from (x0,y0) to the line
ax+by+c=0 is fabs((a*x0+b*y0+c)/sqrt(a*a+b*b)). This is elementary
math.

"elementary math" does not include any function commonly known
as fabs(). fabs() is C code, a specific absolute value function that
takes a double as its argument and returns a double. And that
leads to implimentation instability as a*a+b*b approaches the
implimentation's 0.

the formula you actually posted.

My comment on the formula was not a put-down of it: it's
a fine formula within a fairly reasonable domain.
My comment on the formula was entirely within the context
of Jack's statement that "ANY" distance calculation would do,
in which I took the formula *as posted* and pointed out that
it was unsuitable for some contexts.

I know
that you have been trolling^W posting here for a short time, but there
is no excuse for your poor imitation of Carnack.

I don't recall that I have ever trolled in clc . I have posted
my opinions and defended those opinions, but they -are- my opinions,
not troll statements.
--
Oh, to be a Blobel!
Nov 14 '05 #9
On 5 Apr 2005 23:00:03 GMT, in comp.lang.c ,
ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote:
In article <q0********************************@4ax.com>,
Mark McIntyre <ma**********@spamcop.net> wrote:
On 5 Apr 2005 03:32:22 GMT, in comp.lang.c ,
ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote:
c) The equation that was posted goes unstable as
a**2+b**2 approaches 0.
Er, if a^2+b^2 is zero, you don't have a line.

The equation that was posted used 'fabs', thus
indicating actual implimentation code

Actually it was a mathematical formula. I assume that in real code
you'd check for a and b both being zero. And I discount imaginary
values of either... :-)
Consider ax + by + c = 0
we can consider what we like. There's no (real) combination of a and b
that create a line, yet whose summed squares are zero.

If you want to continue this, take it over to sci.maths maybe?
Just find ANY perpendicular distance from a given point to a line. It
will be the shortest, since there is only one.

Its not. Axiomatically, if you find any perpendicular between your
point and your line, its is the shortest distance. Jack said nothing
A number of years ago, part of our interviews involved a question with
finding and implimenting the answer to a geometric problem.
Interesting, but the answers posted were not implementations, they
were hints.
through everything. On the other hand, the candidate ruined everything
by insisting on arguing when we pointed out the simple overlook,

Something thats all too common in CLC too...

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
Nov 14 '05 #10
On 6 Apr 2005 02:29:39 GMT, in comp.lang.c ,
ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote:
"elementary math" does not include any function commonly known
as fabs().
Thats a silly bit of pedantry, and you know it. You're doing precisely
what you blamed your interview candidate for - you overlooked
something, got called on it, and are now busy trying to fight back out
I don't recall that I have ever trolled in clc .
I have posted
my opinions and defended those opinions, but they -are- my opinions,
not troll statements.

Indistinguishable from the distance of usenet, especially when done ad
nauseam and in inflammatory fashion.

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
Nov 14 '05 #11
In article <c4********************************@4ax.com>,
Mark McIntyre <ma**********@spamcop.net> wrote:
On 6 Apr 2005 02:29:39 GMT, in comp.lang.c ,
ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote:
"elementary math" does not include any function commonly known
as fabs(). You're doing precisely
what you blamed your interview candidate for - you overlooked
something, got called on it, and are now busy trying to fight back out
On the contrary, I noticed the existance of the fabs() in the
original formula immediately, and thus immediately recognized the code
as being implimentation rather than mathematical. I noticed something
that others missed.

I make no claim that the use of fabs() in the formula was deliberate:
I just point out that it was there, and will be read by some as the
C fabs() function... which is fine for some domain values but not
for others.
Thats a silly bit of pedantry, and you know it.
It is -not- "a silly bit of pendantry". I majored in math and
I've worked in math-heavy research environments since then.
There is no fabs() in mathematics, -except- when one is
explicitly dealing with limited precision.

fabs() vs abs() is a semantic difference. It may have been an
unintended semantic difference, but it was there.

I don't recall that I have ever trolled in clc .
I have posted
my opinions and defended those opinions, but they -are- my opinions,
not troll statements.

Indistinguishable from the distance of usenet, especially when done ad
nauseam and in inflammatory fashion.

Nearly everything is indistinguishable from the distance of usenet ;-(

--
Would you buy a used bit from this man??
Nov 14 '05 #12
Walter Roberson wrote:
On the contrary, I noticed the existance of the fabs() in the
original formula immediately, and thus immediately recognized the code
as being implimentation rather than mathematical. I noticed something
that others missed.
You *still* can't spell "implementation."
There is no polite term for your claim that you "recognized the code as
being implimentation [sic] rather than mathematical." There is nothing
that flags my post as either "code" or "implimentation." It makes sense
that when one posts to comp.lang.c one uses the syntax available in C.
For example, I am always disturbed by people who type in c.l.c
'(a^2+b^2)' or '(a**2+b**2)' where I have '(a*a+b*b)'. Those other
forms have meanings to C programmers which are _not_ the same as
'(a*a+b*b)'.

If I had prepared my original text for publication in an elementary math
textbook (repeated for convenience)
Just to get you started, the distance from (x0,y0) to the line
ax+by+c=0 is fabs((a*x0+b*y0+c)/sqrt(a*a+b*b)). This is elementary
math. If you can't derive that for yourself, drop your programming
course and take the math you should have learned already.

I would have written

..EQ
delim %%
..EN
..br
Just to get you started, the distance from
%(x sub 0 , y sub 0 )%
to the line
%ax ~+~ by ~+~ c ~=~ 0%
is
%{~|~ ax sub 0 ~+~ by sub 0 ~+~c ~|~} over sqrt {a sup 2 ~+~ b sup 2}%.
..br
This is elementary
math. If you can't derive that for yourself, drop your programming
course and take the math you should have learned already.
..bp
..EQ
delim off
..EN

Would that have been useful?

Your assertions are utter bullshit, and you are a troll.
*PLONK*
Nov 14 '05 #13
On 6 Apr 2005 16:01:59 GMT, in comp.lang.c ,
ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote:
In article <c4********************************@4ax.com>,
Mark McIntyre <ma**********@spamcop.net> wrote:
You're doing precisely what you blamed your interview candidate for -
On the contrary, I noticed the existance of the fabs() in the
original formula immediately, and thus immediately recognized the code
as being implimentation rather than mathematical. I noticed something
that others missed.

mistake in hollering about the summed squares, and are now trying o
wriggle off the hook by claiming that Martin's quote, which he
specifically flagged as being just an algo, was a code sample.
Thats a silly bit of pedantry, and you know it.

It is -not- "a silly bit of pendantry".

*shrug*
I majored in math and
I've worked in math-heavy research environments since then.
Then you know that this was nothing more than a short-hand way of
expressing what might otherwise have been hard.
There is no fabs() in mathematics,

there's also no f in sense (in your argument)

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
Nov 14 '05 #14
Martin Ambuhl wrote:
Walter Roberson wrote:
On the contrary, I noticed the existance of the fabs() in the
original formula immediately, and thus immediately recognized
the code as being implimentation rather than mathematical. I
noticed something that others missed.

.... snip ...
Your assertions are utter bullshit, and you are a troll.
*PLONK*

On the other hand he IS educable, as shown by the earlier
controversy over quote marks. He will spend a long time living
that sequence down. He does show signs of infallibility,
manifested as extreme porcine headedness. We all do it, to some
extent or other.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the