Creating non self intersecting Quadrilaterals from 4 points

Question

Given 4 points (lP1, lP2, lP3, lP4) ordered from highest y value to lowest, and when y values equal each other, it is sorted from lowest x to highest x, based in a regular mathematical Quadrant I (not inverted as it typically would be for Computer Science). Based off of this, what is the best way to determine from which points lines should be drawn to create a non self-intersecting Quadrilateral?

Answer 1

One approach is as follows: pick any three points and imagine connecting them to form a triangle. See if the fourth point is inside the triangle. If it is, you can connect it to any pair of points you want, deleting the side between them, and you have a non self-intersecting quadrilateral. If it is outside, you want to pick two points to connect it to such that the fourth point is not inside the triangle formed. There will be one or two choices.

Some examples are given below. In each case, the heavy lines are the original triangle, the dot is the remaining point, and the light lines give the new ones. You delete the dark line connecting the other ends of the light lines. In the third example, you have to take the middle light line, then can take either of the other two you like.