どのようにして2つの点の間に線分を作成し、その線と交差する点の数を調べますか？

Question

私はポイント間のすべての可能なラインを生成するコードがあります。

import matplotlib.pyplot as plt 
import matplotlib.lines as lines 
import itertools 

fig=plt.figure() 
ax=fig.add_subplot(111) 
all_data = [[1,10],[2,10],[3,10],[4,10],[5,10],[3,1],[3,2],[3,3],[3,4],[3,5]] 
x, y = zip(*all_data) 
plt.scatter(x,y) 
for pair in itertools.combinations(all_data,2): 
    line=lines.Line2D(*zip(*pair)) 
    line.set_color('brown') 
    ax.add_line(line) 

plt.show() 

を私はそれぞれの行が交差するどのように多くのポイントします。 （ポイントは青）

Answer 1

この距離メトリックを使用します。 http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html 最後に向かって素敵なベクトル式があります。 dがεより小さければ、交点を持つすべての点線の組み合わせを置換します。

Answer 2

はたぶん（未テスト）このような何か：

def crossf(p1, p2): 
    u"returns a boolean function for testing line (p1, p2)" 
    if p1[0] == p2[0]: 
    y = [p1[1], p2[1]] 
    y.sort() 
    # if p3 falls within the y range it is on the line 
    return lambda p3: (p3[1] >= y[0]) and (p3[1] <= y[1]) 
    else: 
    slope = p2[1] - p1[1], p2[0] - p1[0] 
    # y/x ratio of point (p3 - p1) must equal slope 
    return lambda p3: (p3[0] - p1[0]) * slope[1] == (p3[1] - p1[1]) * slope[0] 

crosstests = dict([(pair, crossf(*pair) for pair in itertools.combinations(all_data,2)]) 

for pair in crosstests: 
    for point in all_data: 
    print 'point %s does %sfall on line %s' % (point, 
     '' if crosstests[pair](point) else 'not ', pair)