Selecting a maximal area quadrilateral from four random points

To calculate the area of a quadrilateral with the points coordinates, the points are supposed to be taken clockwise or counter clock wise.When the shoelace formula is applied on each of  4!=24 tuple of four points, different values can be obtained:

For example, the area of the square (on top left) with the points taken clock wise, is equal to 4. The 24 ways to calculate the area yield only two values 0 or 4. The quadrilateral of area equal to 0 is plotted on top right (red), this quadrilateral is self intersecting. The trapeze area (down left) is equal to 3, the 24 ways to calculate the area yied three values :0, 1, 3 and the maximal value of the area corresponds to a non intersecting quadrilateral (blue, down right).

Quadrilaterals were build from randomly chosen points, their area was calculated by taking the original points order:

Some of them are self intersecting (first, top left) or degenerated (the 10th). By searching the order of the points giving the maximal area, non self-intersecting quadrilaterals can be found:

If both initial and final quadrilaterals are overlayed:

Compare from the previous post, the function to calculate the area was modified http://people.virginia.edu/~ll2bf/docs/various/polyarea.html).

Play with the code on cloud.sagemath or download code.

Update (2014-04):

A quadrilateral of maximal area is found using brute force (by looking for the permutations of four points). Since cyclic or circular permutations of four points yield quadrilaterals with the same area, the search of maximal area should be performed not on a set of permutations of points but on a set of unique cyclic permutations of four points (a "necklace") possibly with Sawada's algorithm