Area between two lines inside the square [-1,+1] x [-1,+1]

Question

I'm working on a project in Matlab and need to find the area between two lines inside of the square [-1,+1]x[-1,+1] intersecting in a point (xIntersection,yIntersection). So the idea is to subtract the two lines and integrate between [-1, xIntersection] and [xIntersection, +1], sum the results and if it's negative, change its sign.

For details on how I find the intersection of the two lines check this link.

I'm using Matlab's function integral(), here a snippet of my code:

xIntersection = ((x_1 * y_2 - y_1 * x_2) * (x_3 - x_4) - (x_1 - x_2) * (x_3 * y_4 - y_3 * x_4) ) / ((x_1 - x_2) * (y_3 - y_4) - (y_1 - y_2) * (x_3 - x_4));

d = @(x) g(x) - f(x);
result = integral(d, -1, xIntersection) - int( d, xIntersection, 1)
if(result < 0),
    result = result * -1;
end

Note that I defined previously in the code g(x) and f(x) but haven't reported it in the snippet.

The problem is that I soon realized that the lines could intersect either inside or outside of the square, furthermore they could intersect the square on any of its sides and the number of possible combinations grows up very quickly.

I.e.:

These are just 4 cases, but considering that f(+1), f(-1), g(+1), g(-1) could be inside the interval [-1,+1], above it or under it and that the intersection could be inside or outside of the square the total number is 3*3*3*3*2 = 162.

Obviously in each case the explicit function to integrate in order to get the area between the two lines is different, but I can't possibly think of writing a switch case for each one.

Any ideas?

Answer 1

I think my answer to your previous question still applies, for the most part.

If you want to compute the area of the region bounded by the smaller angle of the two lines and the boundaries of the square, then you can forget about the intersection, and forget about all the different cases.

You can just use the fact that

• the area of the square S is equal to 4

• the value of this integral

  A = quadgk(@(x) ...
      abs( max(min(line1(x),+1),-1) - max(min(line2(x),+1),-1) ), -1, +1);
  

  gives you the area between the lines (sometimes the large angle, sometimes the small angle)

• the value of of min(A, S-A) is the correct answer (always the small angle).

Answer 2

Assuming “between the lines” means “inside the smaller angle formed by the lines”:

With the lines l and h, S := [-1,+1]x[-1,+1] and B as the border of S.

Transform l to the form l_1 + t*l_2 with l_1 and l_2 beeing vectors. Do the same for h.

• If the intersection is not inside S, find the 4 intersections of l and h with B. Sort them so you get a convex quadrilateral. Calculate its area.
• Else:
  • Find the intersection point p and find the intersection angle α between l_2 and h_2. and then check:
    • If α in [90°,180°] or α in [270°,360°], swap l and h.
    • If α > 180°, set l_2 = −l_2
  • Set l_1 := h_1 := p. Do once for positive t and negative t (forwards and backwards along l_2 and h_2 from p):
    • Find intersections s_l and s_h of l and h with B.
    • If on same border of B: compute area of triangle s_l, s_h, p
    • If on adjacent borders of B: find the corner c of B in between the hit borders and once again sort the four points s_l, s_h, p and c so you get an convex quadrilateral and calculate it’s area.
    • If on opposite borders, find the matching side of B (you can do this by looking at the direction of s_l-p). Using its two corner points c_1 and c_2, you now have 5 points that form a polygon. Sort them so the polygon is convex and calculate its area.

This is still quite a few cases, but I don’t think there’s a way around that. You can simplify this somewhat by also using the polygon formula for the triangle and the quadrilateral.

How to sort the points so you get a convex polygon/quadrilateral: select any one of them as p_1 and then sort the rest of the points according to angle to p_1.

If you define an intersection function and a polygon_area that takes a list of points, sorts them and returns the area, this algorithm should be rather simple to implement.

edit: Image to help explain the comment:

Answer 3

Hey guys thanks for your answers, I also thought of an empirical method to find the area between the lines and wanted to share it for the sake of discussion and completeness.

If you take a large number of random points within the square [-1,+1]x[-1,+1] you can measure the area as the fraction of the points which fall in the area between the two lines.

Here's a little snippet and two images to show the different accuracy of empirical result obtained with different number of points.

minX = -1;
maxX = +1;

errors = 0;
size = 10000;

for j=1:size,

    %random point in [-1,+1]
    T(j,:) = minX + (maxX - minX).*rand(2,1); 

    %equation of the two lines is used to compute the y-value
    y1 = ( ( B(2) - A(2) ) / ( B(1) - A(1) ) ) * (T(j,1) - A(1)) + A(2);
    y2 = (- W(1) / W(2)) * T(j,1) -tresh / W(2);

    if(T(j,2) < y1),
        %point is under line one
        Y1 = -1;
    else
        %point is above line one
        Y1 = +1;
    end

    if(T(j,2) < y2),
        %point is under line two 
        Y2 = -1;
    else
        %point is above line two
        Y2 = +1;
    end

    if(Y1 * Y2 < 0),

        errors = errors + 1;
        scatter(T(j,1),T(j,2),'fill','r')
    else
        scatter(T(j,1),T(j,2),'fill','g')
    end

end

area = (errors / size) / 4;

And here are two images, it sure takes longer than the solution posted by @Rody but as you can see you can make it accurate.

• Number of points = 2000

Number of points = 10000