Three points are chosen at random inside a square. Each point is chosen by choosing a random x-coordinate and a random y-coordinate.

A triangle is drawn with the three random points as the vertices. What is the probability that the center of the square is inside the triangle?

DEFDBL A-Z

FOR i = 1 TO 1000000
   x1 = RND(1): y1 = RND(1)
   x2 = RND(1): y2 = RND(1)
   x3 = RND(1): y3 = RND(1)
 
   m = (y2 - y1) / (x2 - x1)
   a = y1 - m * x1
   test1 = y3 - (m * x3 + a)
   test2 = .5 - (m * .5 + a)
  
   m = (y3 - y1) / (x3 - x1)
   a = y1 - m * x1
   test3 = y2 - (m * x2 + a)
   test4 = .5 - (m * .5 + a)
 
   m = (y3 - y2) / (x3 - x2)
   a = y2 - m * x2
   test5 = y1 - (m * x1 + a)
   test6 = .5 - (m * .5 + a)
 
   IF test1 * test2 > 0 AND test3 * test4 > 0 AND test5 * test6 > 0 THEN
     hit = hit + 1
   END IF
   ct = ct + 1
   PRINT hit, ct, hit / ct
NEXT

results in 249,640 hits in 1,000,000 tries, indicating a probability of 1/4 is likely.

The basis of the program is that in order for the center of the square to be within the triangle, it must be on the same side of any one of the lines of the triangle as the vertex of the triangle that is excluded from that side.  If this is true for all three side/vertex sets, the center is within the triangle.

Posted by Charlie on 2008-03-17 13:21:49