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

A convex quadrilateral is drawn with the the four random points as the vertices.

Determine the probability that the center of the square is inside this quadrilateral.

I tried two methods:  one randomized; and one using every combination of integer coordinates in a (of necessity) small grid.
To determine if the four points could form a convex quadrilateral, I made a function isconvex() which takes a list of 8 coordinates (four points) as input and checks if any point is inside the triangle formed by the other 3 points.  If so, then the quadrilateral is not convex.

Another function isinside() checks to see if the origin is inside any of the 4 triangles which can be formed from the 4 points, and the origin is the center of the square.  If true for any of the 4 triangles, then it should also be true for the quadrilateral, whether convex or not.  

I'm sure there are better algorithms for determining convexity and inside-ness, but this is the one I came up with.  I found the Graham scan on Wikipedia but did not implement it.

For the random case, I used coordinates from (-1000,-1000) to (1000,1000) and ran 10000000
repetitions.

Randomized Results:
74.5% of the time, the quadrilateral was convex
Convex:
Inside 3464671
Outside 3987770
Total 7452441
Probability that the center of the square is inside:  0.465

Not Convex:
Inside 1117576
Outside 1117576
Total 2547559
Probability that the center of the square is inside:  0.439

-----
For the "non random" method, 8 nested loops took quite a computational toll, so the largest grid size I ran was (-4,-4) to (4,4) with integer coefficients.  I denied the possiblity that any point could be (0,0).

"Non Random" Results:
78.8% of the time, the quadrilateral was convex
Convex:
Inside 14054938
Outside 18239308
Total 32294246
Probability that the center of the square is inside:  0.435

Not Convex:
Inside 3805743
Outside 4860111
Total 8665854
Probability that the center of the square is inside:  0.439

I'll put the code in another post.

Posted by Larry on 2023-01-12 10:44:18