CODEWITHSUNDEEP
python
George
George

Reputation: 1175

How do you make line segments between two points and find out how many points intersect the line?

I have code that generates all the possible lines between points:

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()

enter image description here

but I want how many points each line intersects. (points are blue)

Upvotes: 0

Views: 1149

Answers (2)

wberry
wberry

Reputation: 19337

Maybe something like this (untested):

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)

Upvotes: 1

totowtwo
totowtwo

Reputation: 2147

Use this distance metric. http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html It has a nice vector expression towards the end. Permute all point-line combinations, if d is less than epsilon, you have an intersection.

Upvotes: 0

Related Questions