I am doing a project in sagemath, where I have a list like this [(0, 2), (1, 3), (2, 1), (3, 0)]. Which creates a graph below and using that graph it calculates the number of intersecting point as 5(marked in purple color)
How do I count this value without graphing it? or with graphing?
Advertisement
Answer
I find this quite interesting question. Could you approach problem like this: think your graph points as layers. Let’s name them zero to three according to your left side starting dots.
Then loop layers starting from top and check all layers below it. Every line starting below will cross your line if its ending point is higher layer than your lines ending point.
Code would be something like this.
lines = [(0,3),(1,2),(2,0),(3,1)] #translated your cordinates. cross = 0 lines.sort() # we want order lines so upper starting point is first for i in range(len(lines)): #using index here, easier this time. my_start = lines[i][0] my_end = lines[i][1] for line_below in lines[i:]: # loop through lines below if line_below[0] == my_start: continue # We don't count crossing if we have the same starting point. if line_below[1] < my_end: cross += 1 #if end point is higher than my end poi, we'll corss
And I’d visualize your starting / ending points like this, not random order on right side:
0 0 1 1 2 2 3 3
But actually this approach would work no mater how many starting points or ending points you have in your graph. The code doesn’t count crossing if the lines meet on starting point or ending point or if two lines are identical (same starting and ending point).