Skip to content
Advertisement

Nuimberof intersection in a graph

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)

enter image description here

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

User contributions licensed under: CC BY-SA
10 People found this is helpful
Advertisement