0
$\begingroup$

I'm looking for a simple way of calculating the area between two straight lines in a -1 to +1 square surface, the shaded fields in the plot below:

Area between lines

My first thought was to calculate the difference of the integrals of the two lines. But I had to split it into two parts (left and right of the intersection) since I wanted the total area, not the upper area minus the lower area. When finished, I realized that the integrals included a triangular area below y = -1. I'm only interested in the area bounded by -1 <= x <= +1 and -1 <= y <= +1.

My second thought was to calculate the area of the two triangles using the intersection point and the points where the lines exit the bounded area. But there are several cases to handle here, for each triangle:

  1. Both lines exit the area to the left or right.
  2. Both lines exit the area to the top or bottom.
  3. One line exits to the right or left and the other one to the top or bottom.
  4. The lines do not intersect.

I guess there is probably a much simpler solution that I haven't thought of.

$\endgroup$
4
  • $\begingroup$ Can one of the lines be vertical? How do you know it's the orange area and not the white one you're looking for? $\endgroup$ Commented Sep 16, 2013 at 13:22
  • $\begingroup$ How are the lines given? $\endgroup$ Commented Sep 16, 2013 at 14:45
  • $\begingroup$ The lines are given as y = ax + b, so they can't be vertical. Regarding orange or white area, it's the smaller area of the two that I'm interested in. $\endgroup$
    – Anlo
    Commented Sep 16, 2013 at 16:56
  • $\begingroup$ Actually, I just realized that it might not be the smallest area I'm looking for. If the lines are given as y=ax+b and y=cx+d, all points (x,y) within the area should satify ax+b <= y <= cx+d OR cx+d <= y <= ax+b. $\endgroup$
    – Anlo
    Commented Sep 17, 2013 at 10:28

1 Answer 1

0
$\begingroup$

Ok, so I bit the bullet and implemented a geometry-based area calculation:

  1. Define the two lines as: $$ y = ax + b\\ y = cx + d $$
  2. Find the four $(x,y)$ points where the two lines exit the $[-1,+1] \times [-1,+1]$ bounded area.
  3. For each corner of the area $(x_c,y_c) = (-1,-1), (-1,+1), (+1,-1), (+1,+1)$, check if it is located between the lines or not: $$ (ax_c+b \le y_c \le cx_c+d) \lor (cx_c+d \le y_c \le ax_c+b) $$
  4. Add the four exit points and all corners found between the lines to a list.
  5. Sort the list so the points are placed counter-clockwise around the perimeter of the bounded area.
  6. Calculate the intersection point of the two lines: $$ ax_i + b = cx_i + d\\ x_i = \frac{d - b}{a - c}\\ y_i = ax_i + b $$
  7. If $(x_i,y_i)$ is located in the bounded area, $$ (-1 \le x_i \le +1) \land (-1 \le y_i \le +1) $$ for each consecutive pair of points (wrapping around to compare the last point with the first), check if their midpoint: $$ (x_m,y_m) = (\frac{x_n+x_{n+1}}{2},\frac{y_n+y_{n+1}}{2}) $$ is located between the lines the same way as in step 3. If the midpoint is not between the lines, insert the intersection point between the two points checked.
  8. Use the list of points as vertices for a non-intersecting, possibly concave, polygon and calculate its area using: $$ A = \frac{1}{2} \sum_{n = 0}^{N-1}(x_n y_{n+1} - x_{n+1} y_n) $$

I've run the algorithm on random data and it seem to handle all cases correctly.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .