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

Question

I am working on a project in Matlab and you need to find the area between two lines inside the square [-1,+1]x[-1,+1] intersecting at the point (xIntersection,yIntersection) . Thus, the idea is to subtract two lines and integrate between [-1, xIntersection] and [xIntersection, +1], summarize the results and, if they are negative, change your sign.

For more information on how to find the intersection of two lines, check out this link.

I use Matlab's integral() function, here is a code snippet:

 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 

Please note that I defined g(x) and f(x) earlier in the code, but did not report this in the snippet.

The problem is that I soon realized that lines can intersect either inside or outside the square, in addition, they can intersect the square on either side of it, and the number of possible combinations grows very quickly.

Ie:

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

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

Any ideas?

Answer 1

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

If you want to calculate the area of ​​an area bounded by a smaller angle of two lines and the borders of a square, then you can forget about the intersection and forget about all the different cases.

You can just use the fact that

• square S is 4

• 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 a large angle, sometimes a small angle)

• the value min(A, SA) is the correct answer (always a small angle).

Answer 2

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

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

Convert 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 to get a convex quadrangle. Calculate its area .
• Else:
  • Find the intersection point p and find the intersection angle α between l_2 and h_2 . and then check:
    • If α at [90°,180°] or α at [270°,360°] , replace l and h .
    • If α > 180° , set l_2 = −l_2
  • Set l_1 := h_1 := p . Do once for positive t and negative t (back and forth along l_2 and h_2 from p ):
    • Find the intersections of s_l and s_h from l and h with B
    • If on the same boundary B : calculate the region of the triangle s_l , s_h , p
    • If on adjacent borders B : find the angle c of B between the borders of the hit and once again collect the four points s_l , s_h , p and c , so you get a convex quadrangle and calculate its area.
    • If on opposite borders find the corresponding side B (you can do this by looking at the direction s_l-p ). Using the two corner points c_1 and c_2 , you now have 5 points that form a polygon. Sort them so that the polygon is convex and computes its area .

These are still quite a few cases, but I do not think so. This can be simplified by also using the polygon formula for a triangle and a quadrangle.

How to sort points to get a convex polygon / quadrangle: select any of them as p_1 , and then sort the remaining points according to the angle up to p_1 .

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

edit: Image to help explain comment:

Answer 3

Hi 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 discussion and completeness.

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

Here is a little fragment and two images to show different accuracy of the empirical result obtained with a 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 probably 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