Find if 4 lines form a Quadrilateral in 2D space

Question

• How can I know if 4 lines form a Quadrilateral in 2D space?
• And how would I obtain the corners? (in clockwise order starting with the top left corner)

Note that lines are formed by 2 points in my case, however the length is not limited to those points but goes on infinitly.

All points are in a fixed 2D space, say (0, 0, 100, 100). The Quadrilateral is either in that space too, or I do not care about it. Also lines are hardly ever parralel since the data comes from an actual image.

The blue lines here is the data, and the green points are the corners I want to obtain. Note that my input data is not always this nice, but mostly consists of lines which do not form any quadrangle in the fixed space.

What I tried

• Find all intersection points within that space.
• Create a convex hull

But this seems inefficient to me and is sometimes inaccurate. I was hoping that there is a somewhat better approach.

Answer 1

Call the lines $L_1,L_2,L_3,L_4$, and let $P_{ij}$ be the intersection of lines $L_i$ and $L_j$. Then the quadrilateral is determined uniquely by which of the lines $L_2,L_3,L_4$ is opposite $L_1$. So there are only three possibilities:

• $L_2$ is opposite $L_1$: $P_{13}P_{32}P_{24}P_{41}$
• $L_3$ is opposite $L_1$: $P_{12}P_{23}P_{34}P_{41}$
• $L_4$ is opposite $L_1$: $P_{12}P_{24}P_{43}P_{31}$

If none of the lines are parallel, and no three lines meet at a single point, then exactly one of these will be a convex quadrilateral.

Do you know how to determine whether a quadrilateral $ABCD$ is convex?