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

chromosomes, overlapping chromosomes and nuclei

In an attempt to find features to distinguish chromosomes from overlapping chromosomes or from nuclei or small image segmentation artifacts ("dusts"), the area and the convex-hull area of isolated particles were computed after segmentation of a metaphasic chromosome image.

Image segmentation and convex-hull area computation were performed with scripts written previously. The features were saved in csv files.

miniKar produced an other csv file where the particle category (label) was saved.

This is an opportunity to handle the data with the pandas library and to see from this limited data set if the two features may be good candidates to classify at least particles in one of the three categories (single, overlapping, nuclei). A features file and the labels file were loaded, merged in one data frame. The features were filtered according to the label (the particle category) and then were displayed in a scatter plot:

green:single chromosomes; red overlapping chromosomes; blue:nuclei

The normalized area is the 1000*area of a particle divided by the image size (1024x1536). From this scatter plot, it's clear that at least an other feature will be necessary to separate the single chromosomes from the overlapping chromosomes. This may be due to the chromosomes bending.

A surprising thing, the ratio should be such: area/convexhull <1 and it is not true for all the particles.

import KarIO
import os,csv
import pylab
import pandas
#make a configurator object
config=KarIO.ClassifConf()
#build the the name feature file
##list all the feature files
##répertoire courant : os.listdir(os.getcwd())
featurespath=os.path.join(os.getcwd(),"Results","features")
labelpath=os.path.join(os.getcwd(),"Results","labels")
#print featurespath
##open features csv files
featuresFilesList=os.listdir(featurespath)
labelsFilesList=os.listdir(labelpath)
##
#let's find a pair of feature file/label file
#open with pandas
#two files match if they come from the same metaphase

featfile=config.user+'-'+config.slide+'-'+config.metaphases_list[2]+'-'+config.counterstain+'.csv'
labelfile='shapeCateg-'+featfile

fea=pandas.read_csv(os.path.join(featurespath,featfile),header=None,names=['particle','ratio','area'])
lab=pandas.read_csv(os.path.join(labelpath,labelfile),header=None,names=['particle','type'])
#merge columns:features and label
data=fea.join(lab)
single=data[data['type']=='single']
touching=data[data['type']=='touching']
nuclei=data[data['type']=='nuclei']
dusts=data[data['type']=='dusts']

##ploting with pylab
#different colors according to the category

fig=pylab.figure()
ax = fig.add_subplot(111)
ax.scatter(single['ratio'],single['area'],c='green',marker='o')
ax.scatter(touching['ratio'],touching['area'],c='red',marker='o')
ax.scatter(nuclei['ratio'],nuclei['area'],c='blue',marker='o')
pylab.show()