This script generates N random points in a plane, then it builds all the combinations of two (three or four) points in N points. The function nclosestpoints, returns the n closest pair of points . The function nsmallesttriangles returns the n smallest triangles according to their area. The function trianglesbellow returns all triangles with an a…

Combination_Area_sort.py

# -*- coding: utf-8 -*-
"""
Created on Fri Dec 14 22:02:31 2012

@author: Jean-Patrick


"""
import random
import itertools as it
from collections import defaultdict
import numpy as np
from scipy.misc import comb

def dist(p1,p2):
    x1=p1[0]
    x2=p2[0]
    y1=p1[1]
    y2=p2[1]
    return (x2-x1)**2+(y2-y1)**2
    
def triArea(A,B,C):
    '''given three points A=(x,y), B, C 
        compute the triangle ABC area
    '''
    xA=A[0]
    yA=A[1]
    xB=B[0]
    yB=B[1]
    xC=C[0]
    yC=C[1]
    return 0.5*abs((xB-xA)*(yC-yA)-(xC-xA)*(yB-yA))
    

def nclosestpoints(c2pointslist,n):
    dic = {}
#    print "get ",n," smallest closest points"
#    print 'there is ', len(c2pointslist), ' 2tupples'
    for i in c2pointslist:
        point1 = i[0]
        point2 = i[1]
        dis = dist(point1,point2)
        dic[dis] = i
        #print dis,i
    allkeys = dic.keys()
    #print allkeys
    ar = np.asarray([allkeys])
    ar = np.sort(ar)
#    print 'all keys:'
    #print ar, ar.shape
    nsmallestkeys = ar[0][:n].tolist()#Uggly!!!
#    print nsmallestkeys
    newdic = defaultdict(list)
    for k in nsmallestkeys:
        newdic[k].append(dic[k])
#    print 'nbre clées' ,len(newdic.keys()),' ==', n
    return newdic
    
    
def nsmallesttriangles(c3pointslist,n):
    dic = {}
    for triplet in c3pointslist:
        point1 = triplet[0]
        point2 = triplet[1]
        point3 = triplet[2]
        
        area = triArea(point1,point2,point3)
        dic[area] = triplet
    #print dic
    allkeys = dic.keys()
    #print allkeys
    ar = np.asarray([allkeys])
    ar = np.sort(ar)
    #print ar.shape
    nsmallestkeys = ar[0][:n].tolist()#Uggly!!!
#    print nsmallestkeys
    newdic = {}
    for k in nsmallestkeys:
        #BUG 7/1/2013
        newdic[k]=dic[k]
#    print 'nbre clées' ,len(newdic.keys()),' ==', n
    return newdic
    
def trianglesbellow(c3pointslist,thresh):
    dic = {}
    for triplet in c3pointslist:
        point1 = triplet[0]
        point2 = triplet[1]
        point3 = triplet[2]
        
        area = triArea(point1,point2,point3)
        dic[area] = triplet
    #print dic
    allkeys = dic.keys()
    ar = np.asarray([allkeys])
    ar = ar[ar<thresh]
    #print ar
    nsmallestkeys = ar.tolist()
    newdic = {}
    for k in nsmallestkeys:
        newdic[k]=dic[k]
#    print 'nbre clées' ,len(newdic.keys()),' ==', n
    return newdic
    
def nsmallestquadrilateral(pointslist,n):
    pass

Nb_points = 10
pl=map(lambda p:(random.randint(0,20),random.randint(0,20)),range(1,Nb_points))
c2=[i for i in it.combinations(pl,2)]
c3=[i for i in it.combinations(pl,3)]
c4=[i for i in it.combinations(pl,4)]

print 'doublets'
print nclosestpoints(c2,7)
print 'triangles'
print nsmallesttriangles(c3,7)
print trianglesbellow(c3,5)