如何在两点之间画线段并找出交点数量？

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小于一个很小的值epsilon，那就说明它们相交了。

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)