I’d think it would be easiest to first break it up into three general cases:
- the line doesn’t intersect the square: Your answer is either 0 or 1.
- the line intersects two opposite sides, say the left and right sides at X1 and X2. Your answer is either (X1+X2)/2, or 1 minus that. Similar if it intersects the top and bottom at Y1 and Y2.
- the line intersects two adjacent sides, at X1 and Y1. You have a triangle, whose area is easy to calculate, then decide if that’s you answer or 1 minus your answer.
The area above will always be the area of 1 triangle or the sum of 2 triangles.
So a way to approach with a small number of conditions could be:
1 - If line is on top of one edge of square then handle that condition
2 - Otherwise, calc intersect of all 4 sides resulting in 2 points
3 - If 2 adjacent sides are intersected which includes the top line of the square - calc area of that single triangle
4 - Otherwise you need to sum the area of 2 triangles, they are:
4.1 - Triangle #1, 3 points are:
4.1.1 - intersect point #1
4.1.2 - end point of that line that is “inside” region (e.g. top end if it’s the left side that is intersected)
4.1.3 - adjacent line end point that is “inside” region
4.2 - Triangle #2, 3 points are:
4.2.1 - intersect point #1
4.2.2 - intersect point #2
4.2.3 - point #4.1.3 (calculated in previous section)
Yep, this is simplest, simpler than my 2 triangles.
Since you speak about “above” the line, I will assume the line is not vertical.
Thus, we may as well specify the line by two points (-1, p) and (1, q) on it. [I am using the convention that “above” corresponds to having a larger second coordinate]. Without loss of generality, we may assume p <= q (if p > q, just swap them). Let us also, for convenience, define the function g(y) = (p + q - 2y)/(p - q), which assigns to vertical coordinates the corresponding horizontal coordinate on the line.
Having done so:
If p > 1, the answer is 0, as the entire square is below the line.
If q < -1, the answer is 4, as the entire square is above the line.
Otherwise, the answer will be the sum of up to three terms:
A) The first term is the simplest: 2 - p - q. This would be completely correct if the line never crossed the bottom or top of the square.
B) If p < -1, we add a term of (p + 1) * (1 + g(-1))/2. This compensates for crossing the bottom of the square.
C) If q > 1, we add a term of (q - 1) * (1 - g(1))/2. This compensates for crossing the top of the square.
Personally, I would tessellate everything to triangles and only deal with those. Intersecting a line with a triangle is easier than with a square, though you might end up with two triangles out of it. At the end, just add up the areas of the resulting triangles.
For your second problem, you can do the intersection twice, but flipping the direction of the lines, and then adding the results.
There may be slightly simpler methods for specific problems, but this method will work no matter how many lines you have or how they intersect. And it’s easier to prove to yourself that the method works.
Ah, in my last post I had not realized the problem had been expanded to include two lines…
It might be easier to start talking in terms of half-planes. A half-plane is a line where we deem one side of it to be inside and the other outside (there are some complications with how we deal with points exactly on the line, but I think for current purposes this can be ignored).
The first problem then is the area of an intersection between a half-plane and a square. We might call this (S & H). The second problem is the intersection of S with two half-planes, and also the complements of the half-planes. We might call this (S & ((H[sub]1[/sub] & H[sub]2[/sub]) + (H’[sub]1[/sub] & H’[sub]2[/sub]))).
As I said, though, dealing with triangles only makes this much easier. So instead we might write:
(T[sub]1[/sub] & H[sub]1[/sub] & H[sub]2[/sub]) +
(T[sub]1[/sub] & H’[sub]1[/sub] & H’[sub]2[/sub]) +
(T[sub]2[/sub] & H[sub]1[/sub] & H[sub]2[/sub]) +
(T[sub]2[/sub] & H’[sub]1[/sub] & H’[sub]2[/sub])
Intersecting a triangle with a half-plane is easy because there’s really only one case to worry about. You first figure out which of the three vertices lie on which side of the half-plane. If they’re all in or all out, you’re done. Otherwise, you have one vertex on one side and two on the other side. Sort your vertices so that the singleton is first and remember whether that’s the inside or outside. Do the intersection with the two edges that radiate from there, and then construct a single new triangle (if the singleton was inside) or two new tris (if it was outside) from the two new points.