regarding algorithim

[invincible]

Hi

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

Thanks

Mohan

[Martin Ambuhl]

Re: regarding algorithim

invincible wrote:[color=blue]
> Hi
>
> I want to find an algorithim , which calculates shortest perpendicular
> distance from a given point to a line.[/color]

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>

[Jack Klein]

Re: regarding algorithim

On Mon, 4 Apr 2005 12:20:15 +0530, "invincible "
<mohan.bhakri@i n.bosch.com> wrote in comp.lang.c:
[color=blue]
> Hi
>
> I want to find an algorithim , which calculates shortest perpendicular
> distance from a given point to a line.
>
> Thanks
>
> Mohan[/color]

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.l earn.c-c++

http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html

[Walter Roberson]

Re: regarding algorithim

In article <3it351hl6n7vh0 8bu8ck6a9qqib2r 25u4c@4ax.com>,
Jack Klein <jackklein@spam cop.net> wrote:[color=blue]
>Just find ANY perpendicular distance from a given point to a line. It
>will be the shortest, since there is only one.[/color]

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

[invincible]

Re: regarding algorithim

thanks a lot for ur reply..........


"Martin Ambuhl" <mambuhl@earthl ink.net> wrote in message
news:jO64e.29$s p3.2@newsread3. news.atl.earthl ink.net...[color=blue]
> invincible wrote:[color=green]
> > Hi
> >
> > I want to find an algorithim , which calculates shortest perpendicular
> > distance from a given point to a line.[/color]
>
> 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>[/color]

[Mark McIntyre]

Re: regarding algorithim

On 5 Apr 2005 03:32:22 GMT, in comp.lang.c ,
roberson@ibd.nr c-cnrc.gc.ca (Walter Roberson) wrote:
[color=blue]
>In article <3it351hl6n7vh0 8bu8ck6a9qqib2r 25u4c@4ax.com>,
>Jack Klein <jackklein@spam cop.net> wrote:[color=green]
>>Just find ANY perpendicular distance from a given point to a line. It
>>will be the shortest, since there is only one.[/color]
>
>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.[/color]

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>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt >

[Walter Roberson]

Re: regarding algorithim

In article <q00651hdt0u5qd g1qmtdksg5sf0b6 sdh0m@4ax.com>,
Mark McIntyre <markmcintyre@s pamcop.net> wrote:[color=blue]
>On 5 Apr 2005 03:32:22 GMT, in comp.lang.c ,
>roberson@ibd.n rc-cnrc.gc.ca (Walter Roberson) wrote:[/color]
[color=blue][color=green]
>>c) The equation that was posted goes unstable as
>>a**2+b**2 approaches 0.[/color][/color]
[color=blue]
>Er, if a^2+b^2 is zero, you don't have a line.[/color]

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.

Jack had posted that,
[color=blue][color=green][color=darkred]
>>>Just find ANY perpendicular distance from a given point to a line. It
>>>will be the shortest, since there is only one.[/color][/color][/color]

and I am pointing out that Jack's answer is misleading: Jack's answer
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
numeric answer...

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
about theoretical answers was going to noticably impact the candidate's
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??

[Martin Ambuhl]

Re: regarding algorithim

Walter Roberson wrote:
[color=blue]
> The equation that was posted used 'fabs', thus
> indicating actual implimentation code rather than
> indicating the mathematical formula for the solution.[/color]

Bullshit. What I posted was[color=blue]
><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>[/color]

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.

[Walter Roberson]

Re: regarding algorithim

In article <HMF4e.4333$44. 4199@newsread1. news.atl.earthl ink.net>,
Martin Ambuhl <mambuhl@earthl ink.net> wrote:[color=blue]
>Walter Roberson wrote:[/color]
[color=blue][color=green]
>> The equation that was posted used 'fabs', thus
>> indicating actual implimentation code rather than
>> indicating the mathematical formula for the solution.[/color][/color]
[color=blue]
>Bullshit. What I posted was[/color]
[color=blue][color=green]
>> 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.[/color][/color]

"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.

I did not write about your *intended* formula, I wrote about
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.

[color=blue]
>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.[/color]

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!

[Mark McIntyre]

Re: regarding algorithim

On 5 Apr 2005 23:00:03 GMT, in comp.lang.c ,
roberson@ibd.nr c-cnrc.gc.ca (Walter Roberson) wrote:
[color=blue]
>In article <q00651hdt0u5qd g1qmtdksg5sf0b6 sdh0m@4ax.com>,
>Mark McIntyre <markmcintyre@s pamcop.net> wrote:[color=green]
>>On 5 Apr 2005 03:32:22 GMT, in comp.lang.c ,
>>roberson@ibd. nrc-cnrc.gc.ca (Walter Roberson) wrote:[/color]
>[color=green][color=darkred]
>>>c) The equation that was posted goes unstable as
>>>a**2+b**2 approaches 0.[/color][/color]
>[color=green]
>>Er, if a^2+b^2 is zero, you don't have a line.[/color]
>
>The equation that was posted used 'fabs', thus
>indicating actual implimentation code[/color]

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... :-)
[color=blue]
>Consider ax + by + c = 0[/color]

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?
[color=blue]
>Jack had posted that,
>[color=green][color=darkred]
>>>>Just find ANY perpendicular distance from a given point to a line. It
>>>>will be the shortest, since there is only one.[/color][/color]
>
>and I am pointing out that Jack's answer is misleading:[/color]

Its not. Axiomatically, if you find any perpendicular between your
point and your line, its is the shortest distance. Jack said nothing
about how to do so.
[color=blue]
>A number of years ago, part of our interviews involved a question with
>finding and implimenting the answer to a geometric problem.[/color]

Interesting, but the answers posted were not implementations , they
were hints.
[color=blue]
>through everything. On the other hand, the candidate ruined everything
>by insisting on arguing when we pointed out the simple overlook,[/color]

Something thats all too common in CLC too...

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt >

----== 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 =----

[Mark McIntyre]

Re: regarding algorithim

On 6 Apr 2005 02:29:39 GMT, in comp.lang.c ,
roberson@ibd.nr c-cnrc.gc.ca (Walter Roberson) wrote:
[color=blue]
>"elementary math" does not include any function commonly known
>as fabs().[/color]

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
of your corner.
[color=blue]
>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.[/color]

Indistinguishab le 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>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt >

----== 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 =----

[Walter Roberson]

Re: regarding algorithim

In article <c4m751lsbqr0lm sgeurg0g1a22oo3 4jk6t@4ax.com>,
Mark McIntyre <markmcintyre@s pamcop.net> wrote:[color=blue]
>On 6 Apr 2005 02:29:39 GMT, in comp.lang.c ,
>roberson@ibd.n rc-cnrc.gc.ca (Walter Roberson) wrote:[/color]
[color=blue][color=green]
>>"elementary math" does not include any function commonly known
>>as fabs().[/color][/color]
[color=blue]
> 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
>of your corner.[/color]

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.
[color=blue]
>Thats a silly bit of pedantry, and you know it.[/color]

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.

[color=blue][color=green]
>>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.[/color][/color]
[color=blue]
>Indistinguisha ble from the distance of usenet, especially when done ad
>nauseam and in inflammatory fashion.[/color]

Nearly everything is indistinguishab le from the distance of usenet ;-(

--
Would you buy a used bit from this man??

[Martin Ambuhl]

Re: regarding algorithim

Walter Roberson wrote:
[color=blue]
> 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.[/color]

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)
[color=blue]
> 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.[/color]

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*

[Mark McIntyre]

Re: regarding algorithim

On 6 Apr 2005 16:01:59 GMT, in comp.lang.c ,
roberson@ibd.nr c-cnrc.gc.ca (Walter Roberson) wrote:
[color=blue]
>In article <c4m751lsbqr0lm sgeurg0g1a22oo3 4jk6t@4ax.com>,
>Mark McIntyre <markmcintyre@s pamcop.net> wrote:
>[color=green]
>> You're doing precisely what you blamed your interview candidate for -[/color]
>
>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.[/color]

We could argue about this all day. My opinion is that you made a
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.
[color=blue][color=green]
>>Thats a silly bit of pedantry, and you know it.[/color]
>
>It is -not- "a silly bit of pendantry".[/color]

*shrug*
[color=blue]
>I majored in math and
>I've worked in math-heavy research environments since then.[/color]

Then you know that this was nothing more than a short-hand way of
expressing what might otherwise have been hard.
[color=blue]
>There is no fabs() in mathematics,[/color]

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

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt >

----== 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 =----

[CBFalconer]

Re: regarding algorithim

Martin Ambuhl wrote:[color=blue]
> Walter Roberson wrote:
>[color=green]
>> 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.[/color]
>[/color]
.... snip ...[color=blue]
>
> Your assertions are utter bullshit, and you are a troll.
> *PLONK*[/color]

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.c om, 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
"Reply" at the bottom of the article headers." - Keith Thompson