Friday, 16 November 2007

Code: The Distance from Point to Line Segment

上周提到的“点到线段的距离”问题,我的Python Code是这样的:

import math

def p2s( a, b, p ):
dX = b[0] - a[0]
dY = b[1] - a[1]
segmentLen = math.sqrt( dX * dX + dY * dY )
halfLen = segmentLen / 2

pX = p[0] - a[0]
pY = p[1] - a[1]
if segmentLen < 1E-6:
return math.sqrt( pX * pX + pY * pY )

newX = abs( ( pX * dX + pY * dY ) / segmentLen - halfLen )
newY = abs( - pX * dY + pY * dX ) / segmentLen

if newX > halfLen:
newX = newX - halfLen
return math.sqrt( newX * newX + newY * newY )
else:
return newY

a = ( 1, 1 )
b = ( 4, 5 )
p = ( 0, 5 )

print p2s( a, b, p )

Friday, 9 November 2007

Quiz: The Distance from Point to Line Segment

昨天和James,深入地讨论了一个简单的平面几何问题,计算点到线段的距离。

如图所示,知道线段AB和点P1、P2的坐标,计算距离L1、L2的长度。要求,优化算法,使得计算的Time Cost最少

我用Python在Windows下,测试了不同数值操作相应的time cost。基本的比例关系是这样的:

        加法   :  2.0
减法 : 2.0
乘法 : 2.2
除法 : 2.4
开根 : 6.0
绝对值 : 3.0
判断是 : 2.5
判断否 : 2.6

有兴趣的,一起考虑考虑这个简单问题,如何做到更好。请将idea或code,回复在下面。基本的程序样式,如下:

import math

def p2s( a, b, p ):
[...]

a = ( 1, 1 )
b = ( 4, 5 )
p = ( 0, 5 )

print p2s( a, b, p )

一周以后,我会把我的Python Code贴出来。