this is for a program I am working on.
my program isn’t really about geometry (it is sort of a monte carlo simulation) and I need to know the probability of a random 2 dimensional point landing above a line which intersects a square.
The square is from x = -1 to +1 and from y = -1 to +1. The line could be anywhere, it might not even intersect the square at all.
I have come up with solutions for specific cases (such as when the line intersects the square at the top and bottom edges) and I can continue on in this way but it feels so inelegant. Is there a simple solution that works for the general case?
i guess another way to put this question is: let f(x) be the line that goes through the square. Then let g(x) be a line parallel to f(x) but shifted up by 1. I want to integrate g(x) from x = -1 to 1, but restricting g(x) to the range 0 to 2.
I assume you’re restricting the random point to lie within or on the square, yes?
If the line intersects a square, it will form a right triangle or a right trapezoid. It is the area of that figure (or its complement) you want. Evaluate the line’s x at y=1 and y=-1 and vice versa; determine which are in bounds (-1,1) and proceed by cases.
This is straightforward but somewhat tedious. I know no shortcut except … Monte Carlo simulation!
Do you actually want to do the MC simulation or do you just want the answer based upon the areas above and below the line?
Yes
i need the answer analytically, based on the areas above and below the line.
I was hoping it wouldn’t come to this. I can think of 7 distinct cases to look for. Oh well…
Yep, from what you describe septimus is correct
Nine cases, I’m afraid, since in the vertical and non-interesecting cases, you’ll still need an above/below test.
Assuming one definition of “above/below” and that the line is y = Ax + B, AFAICT the nine cases correspond exactly to the nine values (0,1,2,…,8) of this C expression:
(A+B > 1 ? 2 : A+B < -1 ? 0 : 1) + ( -A+B > 1 ? 6 : -A+B < -1 ? 0 : 3)
Yes, I believe you are correct. I will ensure that these cases are not evaluated.
looks interesting, I will try to come to terms with that (I don’t know C, just VB.)
It turns out my problem is more complicated than I thought. What I now have is 2 functions, both straight lines crossing a square. I need to know the area above f1 but below f2 plus the area above f2 but below f1.
Does this mean I have to code for 49 individual cases? :eek:
I’ve decided life is too short and am going to approximate the answer by splitting the x axis into very many smaller chunks and finding the sum of (the absolute difference between f1 and f2 at x)*dx.
I may be missing something here, but it seems that the area above the line can in general be seen as consisting of a rectangle plus a triangle. Calculating the area of each of these - and then their sum - should not be difficult.
Note that in certain cases, the area of either of these - or both (in the case of a line that does not intersect the square) - could be zero. Which should not cause problems.
I’m with **Xema **- a little geometry is all that’s needed here after you determine the intercepts. Granted the geometry will be different depending upon which sides of the square are intercepted but for each case it should be trivial.
this is what i did when it I thought it was just 1 line (only 7 cases to consider). However with 2 lines it seems to me that there are 49 cases to consider. Each case on it’s own is trivial but 49 of them is a pain to sludge through.
Calculating the area of a particular situation is simple, making a program that handles all situations is more complex. There are probably ways to simplify this though, using the symmetries of some of the situations.
Let’s say you have the points of intersection, [x1, y1] and [x2, y2]. In both pairs, either x or y has to be -1 or 1.
Start by checking that the line intersects at all. If it isn’t the calculation is trivial.
Order the two points so that x1 is the smaller of the two x’s.
Next let’s start with the case that x1 is -1. The area above the line then is one of these three:
A, the triangle [-1, y1], [x2, 1], [-1, 1]
B, the trapezoid (or square) [-1, y1], [1, y2], [1, 1], [-1, 1]
C, the pentagon [-1, y1], [x2, -1], [1, -1], [1, 1], [-1, 1]
The areas of these are:
A = (1 - y1)(1+x2)/2
B = 2*(1-y1 + 1-y2)/2 = (2 - y1 - y2)
C = 4 - (1-y1)(1+x2)/2
If x1 isn’t -1, check if x2 is 1, if it is, the flip the sign on both x1 and x2, change the order and run them through the already area function.
If x1 isn’t -1 and x2 isn’t 1, then check if y1 > y2. If it is, we have [x1, 1], [x2, -1], change that to [-1, x1] and [1, x2] and run it through the area function. If it isn’t, we have [x1, -1], [x2, 1], change that to [-1, -x1] and [1, -x2] and run it through the area function.
I think. 
Yeah, I admit I missed that part.
Good Luck!
The first question to be answered is in what form is the line specified? Two points? Slope intercept? Once that is known, it may be possible to have a single solution.
naita is certainly on the right track
I’m thinking you need to determine a few things
a) if neither if the lines intersect the box…
a1) both above or both below - your answer is zero
a2) one above and one below - it’s the area of the box
b) if only one line intersects the box all you need is the area either above or below that line depending upon if the other line is above or below the box
c) both lines intersect the box…
c1) if the lines do not intersect within the box you need the area between them which is the area below the upper line minus the area below the lower line
c2) if the lines intersect within the box naita pretty much worked out for you
Does that sound like I’m on the right track naita and Saffer?
And I’m with both of the posters on this. It’s a simple case of geometric calculation. Unless the line is a curve, there’s no need to get into integration etc.
Top rectangle - top triangle = top area. Same for bottom area, or just total area minus top area. I am not sure why this is getting so much complexing.