Skip to content

Instantly share code, notes, and snippets.

@agocs
Created January 5, 2015 22:02
Show Gist options
  • Save agocs/dd50aebf6d0ba664a3b5 to your computer and use it in GitHub Desktop.
Save agocs/dd50aebf6d0ba664a3b5 to your computer and use it in GitHub Desktop.
What is the probability that two random lines drawn inside a square will intersect?
import random
#Orientation and doIntersect mostly copied wholesale from here:
# http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
# with some modifications because I can safely ignore their special cases.
def orientation(p, q, r):
val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
if val == 0:
return val #colinear
retval = 1 if (val > 0) else 2
return retval
def doIntersect(p1, p2, q1, q2):
o1 = orientation(p1, q1, p2)
o2 = orientation(p1, q1, q2)
o3 = orientation(p2, q2, p1)
o4 = orientation(p2, q2, q1)
if (o1 != o2 and o3 != o4):
return True
return False
def makeRandPoint():
#Let's say our random square goes from 0,0 to 10,10
#Figure out which wall the point is on
wall = random.randint(0,3)
if wall == 0:
return (0,random.random() * 10)
if wall == 1:
return (random.random() * 10,0)
if wall == 2:
return (10,random.random() * 10)
if wall == 3:
return (random.random() * 10,10)
def main():
intersections = 0
for i in range(1000000) :
p1 = makeRandPoint()
p2 = makeRandPoint()
q1 = makeRandPoint()
q2 = makeRandPoint()
if doIntersect(p1, p2, q1, q2):
intersections = intersections + 1
print (str(intersections) + " intersections of 1,000,000 found.")
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment