## Thursday, January 31, 2013

### 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).