Pasch's Axiom states that, if a line $l$ intersects $\triangle ABC$ on the side $\overline{AB}$ between its endpoints, but does not contain $A$, $B$, or $C$, then $l$ intersects precisely one of $\overline{AC}$ or $\overline{BC}$ between its endpoints. Pasch's Axiom is Hilbert's Axiom II.4.
Using Pasch's axiom, it is possible to define half-planes. Namely, each line $l$ separates the plane into two convex sets, called half-planes, such that $A$ and $B$ are in the same half-plane if and only if $\overline{AB}$ does not intersect $l$, and in opposite half-planes if and only if $\overline{AB}$ does intersect $l$.
The interior of the angle $\angle BAC$ is defined as the intersection of two half-planes: the half-plane of $\overleftrightarrow{AB}$ containing $C$, and the half-plane of $\overleftrightarrow{AC}$ containing $B$. As the intersection of two convex sets, the interior of the angle is itself convex.
The interior of the triangle may then be defined as the intersection of the interiors of its three angles.
Now consider $\triangle ABC$ and a point $D$ between $B$ and $C$. Note that the segment $\overline{CD}$ does not intersect the line $\overleftrightarrow{AB}$, because the line $\overleftrightarrow{CD}$ intersects $\overleftrightarrow{AB}$ at $B$, hence cannot intersect $\overleftrightarrow{AB}$ at a point between $C$ and $D$. Similarly, the segment $\overline{BD}$ does not intersect the line $\overleftrightarrow{AC}$. It follows that $D$ is in the interior of $\angle BAC$.
$\hspace{3 cm}$
Let $E$ be any point between $A$ and $D$. $E$ is on $\overrightarrow{AD}$, so $E$ is in the interior of $\angle BAC$. If it were not, then, since $D$ is in the interior, the segment $\overline{DE}$ would have to intersect either $\overleftrightarrow{AB}$ or $\overleftrightarrow{AC}$, but the line $\overleftrightarrow{DE}$ intersects each line at $A$, hence cannot intersect either at a point between $D$ and $E$.
Now consider $\angle ABC$. $\overline{DE}$ does not intersect $\overleftrightarrow{AB}$, as just explained, so $E$ is in half-plane of $\overleftrightarrow{AB}$ containing $D$. It follows that $E$ and $C$ are in the same half-plane of $\overleftrightarrow{AB}$ as well. On the other hand, the segment $\overline{AE}$ does not intersect $\overleftrightarrow{BC}$, because the line $\overleftrightarrow{AE}$ intersects $\overleftrightarrow{BC}$ at $D$, hence cannot intersect $\overleftrightarrow{BC}$ at any point between $A$ and $E$. It follows that $E$ is in the half-plane of $\overleftrightarrow{BC}$ containing $A$. So $E$ is in the interior of $\angle ABC$.
Similarly, $E$ is in the interior of $\angle CAB$.
Because $E$ is in the interior of each of the three angles, it must be in the interior of $\triangle ABC$.
Best Answer
A search for largest rectangle in a polygon shows that this problem has been studied in the plane.
Here is a solution that would find the rectangle in your illustration (it's a computer science student project, well done and well documented).
I suspect the three dimensional problem is a fair bit harder.
(This link only answer posted at the OP's request.)