Quadrilateral given by four lines

Question

my question is simple: I have four lines (given by $Ax + By + C = 0$ equation) $l[0]$, $l[1]$, $l[2]$, $l[3]$. There are maximum of $6$ intersection points. How to find four points out of these that form convex quadrilaterals?

Answer 1

You're not guaranteed a convex quadrilateral, in general. If you want a systematic way to find the four intersection, given that your four lines do form a convex quadrilateral, you can sort intersections by their position relative to the others.

Pick 2 random lines, and focus on their intersection point. Along each line, there should be 2 other intersections; keep these in mind. For a line intersection to be the vertex of a convex quadrilateral, it must be the middle point on one of the two lines which form the intersection. Numerically, this can be found by examining the signs of the displacement vectors between the central intersection point and the other colinear points.

You just have to repeat until you find the 4 vertices.

EDIT: In general, there will be 1 vertex which is not a middle-point. This point has the extra property that it is not co-linear with the other 3 middle-point-vertices. Use this criterion to find the fourth vertex.