Finding the boundary of a triangle given the area

Question

This post is math related but my concerns include the correct algorithm I can use in a program. I have been advised to post here as well as on stackoverflow, so maybe I can get some math related insight to this.

I am trying to find the points p1, p2 as an imaginary line (yellow) moves in the direction of the red arrow. The points p1, p2, p3, p4 will bound a user-input area A. What I want is the "first" occurrence of the given area as the yellow line sweeps from right to left.

The points p3, p4, A and angle are known.

I have initially tried something like (psudeocode):

from right to left of the triangle:
    Move p1 to the left on the x-axis by epsilon
    Calculate p2 and the area bounded by (p1,p2,p3,p4)
    if(area < error): return the result
    else: continue

However, this solution may not converge as the epsilon value may be "jumped" over. (for example, if i am trying to find the number 4 by incrementing the number 0 by 0.3 each time, it will never hit 4).

As such, I have tried a binary search method, but failed as I realised that the area bounded is not monotonically increasing (for example, the area bounded by the green line and the left most end of the triangle is also possible solution returned by binary searchig).

My question is is there an algorithm to solve this type of problem? And that it is guaranteed to converge?

Answer 1

Let;'s call the angle $\alpha$. Then your code for computing various geometric values in the picture should look something like this (assuming you have a way to subtract two points to get a vector in your language):

v = p4 - p3;
h = Length(v); // length of right edge
pL = p3 - (sin(angle) * h, 0); // coordinate of left vertex of triangle
A = sin(angle) * h * h / 2; // area of dark blue triangle. 
// for any t between 0 and 1.
hy = p3 + t(p4 - p3);     // length of yellow edge
p1 = p3 + t * (pL - p3);
A1 = A * (1-t)^2; // area of p2 p3 pL
slice = A - A1; // area of quad p2 p3 p1 p4

But the mathematical point is that the area of that left quad, when you've gone $t$ of the way from $p_3$ to the unlabelled left vertex, which I'm now going to call $Q$, is just $$ (1-t)^2 U $$ where $U$ is the area of the large triangle, which is $$ \sin(\alpha) * h^2 / 2 $$ where $h$ is the length of the edge $p_3 p_4$.

If you want this area to be $A$, you write \begin{align} (1-t)^2 U &= A \\ (1-t)^2 &= \frac{A}{U}\\ (1-t) &= \sqrt{\frac{A}{U}}\\ t &= 1 - \sqrt{\frac{A}{U}}\\ t &= 1 - \frac{\sqrt{A}}{\sqrt{U}}\\ t &= 1 - \frac{\sqrt{A}}{\sqrt{\sin(\alpha) h^2 / 2}}\\ t &= 1 - \frac{\sqrt{A}}{h\sqrt{\sin(\alpha)/2}}\\ \end{align}

Having computed $t$, you know that $$ p_1 = p_3 + t(p_L - p_3) $$ where $p_L$ is the point whose $y$ coordinate is the same as that of $p_3$, and whose $x$ coordinate is the $x$-coordinate of $p_3$, MINUS $h \sin(\alpha)$.

Answer 2

First of all, you can do a kind of "binary search" using the distance from $p_3$ to $p_1$ in order to solve this problem. It's called the "bisection method". There are many places you can learn about this method (here, for example); it may be useful to you in the future to know about this.

But in this case, there is a direct solution. Let $p_0$ be the third vertex of the blue triangle. Compute the area of this triangle; let $B$ be the area.

The segment from $p_1$ to $p_2$ will cut the blue triangle (area equal to $B$) into two pieces, a quadrilateral on the right and a triangle on the left, You want the area of the quadrilateral to be $A$, so the area of the remaining triangle (bounded by $p_0$, $p_1$, and $p_2$) must be $B - A$.

The triangles $p_0p_1p_2$ and $p_0p_3p_4$ (the triangle to the left and the large blue triangle) are similar triangles (same angles at each vertex), so the ratio of their areas is the square of the ratio of the lengths of corresponding sides. That is, if $x$ is the distance from $p_0$ to $p_1$ and $r$ is the distance from $p_0$ to $p_3$, then $$ \frac{B - A}{A} = \frac{x^2}{r^2}. $$

With a little algebra, we find that $$ x = r \times \sqrt{\frac{B - A}{A}}. $$

So you can compute $x$. Then you can find the distance from $p_3$ to $p_1$, which is $r - x$.