delaunay triangulation

514 days ago by jrp

import matplotlib def plot_dt(x,y): n = len(x) tri = matplotlib.tri.Triangulation(x,y) edges = set(tuple(e) for e in tri.edges) points = zip(x,y) p = list_plot(points,xmin=0,xmax=1,ymin=0,ymax=1,aspect_ratio=1,color="black") for i in xrange(n): for j in xrange(i+1,n): if (i,j) in edges or (j,i) in edges: p += line2d([points[i],points[j]]) return p def lengths(tri): out = [] for e in tri.edges: ax = tri.x[e[0]] ay = tri.y[e[0]] bx = tri.x[e[1]] by = tri.y[e[1]] out.append( ( (ax - bx)**2 + (ay - by)**2 ) ** 0.5 ) return out def areas(tri): out = [] for t in tri.triangles: ax = tri.x[t[0]] ay = tri.y[t[0]] bx = tri.x[t[1]] by = tri.y[t[1]] cx = tri.x[t[2]] cy = tri.y[t[2]] x1 = bx - ax y1 = by - ay x2 = cx - ax y2 = cy - ay out.append( 0.5 * abs(x1*y2 - x2*y1) ) return out def cdf(vals): vals.sort() n = len(vals) points = [(vals[i],float(i)/n) for i in xrange(n)] return list_plot(points) def avg(vals): n = len(vals) return sum(vals)/float(n) def uniform_points(n): return [uniform(0,1) for i in range(n)], [uniform(0,1) for i in range(n)] def chars(n): ar = [] le = [] for loop in range(100): tri = matplotlib.tri.Triangulation(*uniform_points(n)) ar.append(avg(areas(tri))) le.append(avg(lengths(tri))) return avg(ar), avg(le) 
       
ar = [] le = [] for n in [10 + i*5 for i in range(10)]: print n c = chars(n) print c ar.append((n,c[0])) le.append((n,c[1])) 
        
10
(0.036225757262767069, 0.36336206953716965)
15
(0.027017986349366568, 0.31193095120573028)
20
(0.021196830356723359, 0.27457970444526131)
25
(0.016857644256843617, 0.24249911696763493)
30
(0.014336647096549528, 0.2232636996535588)
35
(0.012847383741687892, 0.20949835082177462)
40
(0.011140967310853041, 0.19838277092875928)
45
(0.010190941084524667, 0.18768796308770622)
50
(0.0090237424608916508, 0.17631928163355076)
55
(0.0082974784472252781, 0.16971869504986611)
10
(0.036225757262767069, 0.36336206953716965)
15
(0.027017986349366568, 0.31193095120573028)
20
(0.021196830356723359, 0.27457970444526131)
25
(0.016857644256843617, 0.24249911696763493)
30
(0.014336647096549528, 0.2232636996535588)
35
(0.012847383741687892, 0.20949835082177462)
40
(0.011140967310853041, 0.19838277092875928)
45
(0.010190941084524667, 0.18768796308770622)
50
(0.0090237424608916508, 0.17631928163355076)
55
(0.0082974784472252781, 0.16971869504986611)
for n in [11 + i*5 for i in range(10)]: print n c = chars(n) print c ar.append((n,c[0])) le.append((n,c[1])) 
        
11
(0.033041549951091251, 0.34949357733297787)
16
(0.025423237769746643, 0.2972459612255548)
21
(0.019474201324534958, 0.26145561158583791)
26
(0.016514663337246528, 0.24252759478856803)
31
(0.013947928664272562, 0.21975365595049193)
36
(0.012325332077059556, 0.20794857137964534)
41
(0.010909616975106135, 0.19361301286830224)
46
(0.0096939218305166757, 0.18260081255989083)
51
(0.0089710375731131779, 0.17568435178744018)
56
(0.0081181179580752799, 0.16655837035962073)
11
(0.033041549951091251, 0.34949357733297787)
16
(0.025423237769746643, 0.2972459612255548)
21
(0.019474201324534958, 0.26145561158583791)
26
(0.016514663337246528, 0.24252759478856803)
31
(0.013947928664272562, 0.21975365595049193)
36
(0.012325332077059556, 0.20794857137964534)
41
(0.010909616975106135, 0.19361301286830224)
46
(0.0096939218305166757, 0.18260081255989083)
51
(0.0089710375731131779, 0.17568435178744018)
56
(0.0081181179580752799, 0.16655837035962073)
for n in [12 + i*5 for i in range(10)]: print n c = chars(n) print c ar.append((n,c[0])) le.append((n,c[1])) 
        
12
(0.032315375948007603, 0.33713378524516813)
17
(0.02353685493238868, 0.28937447534125171)
22
(0.018605408755994823, 0.25538697741416461)
27
(0.015943130276404028, 0.23364664600817037)
32
(0.01366844647841845, 0.21846523527929462)
37
(0.011930589805927322, 0.20410152287448585)
42
(0.010741774076573653, 0.19253717012499311)
47
(0.0096521422780498946, 0.18213289257775669)
52
(0.0089323097626069822, 0.17584985618543592)
57
(0.0080943492665820488, 0.16608850419081381)
12
(0.032315375948007603, 0.33713378524516813)
17
(0.02353685493238868, 0.28937447534125171)
22
(0.018605408755994823, 0.25538697741416461)
27
(0.015943130276404028, 0.23364664600817037)
32
(0.01366844647841845, 0.21846523527929462)
37
(0.011930589805927322, 0.20410152287448585)
42
(0.010741774076573653, 0.19253717012499311)
47
(0.0096521422780498946, 0.18213289257775669)
52
(0.0089323097626069822, 0.17584985618543592)
57
(0.0080943492665820488, 0.16608850419081381)
for n in [13 + i*5 for i in range(10)]: print n c = chars(n) print c ar.append((n,c[0])) le.append((n,c[1])) 
        
13
(0.029349017019857811, 0.3225294790053192)
18
(0.022837253482773944, 0.28082043016913916)
23
(0.018486000000822816, 0.25505838468310488)
28
(0.015275439238188256, 0.230484608811555)
33
(0.013355998416664799, 0.21666155812294574)
38
(0.01159513810350752, 0.19990532286935067)
43
(0.010446572736107501, 0.19029679615613682)
48
(0.0095094653280709471, 0.18125285119954959)
53
(0.0086495229650470021, 0.17265634859582538)
58
(0.0078186129103578889, 0.16444494249990702)
13
(0.029349017019857811, 0.3225294790053192)
18
(0.022837253482773944, 0.28082043016913916)
23
(0.018486000000822816, 0.25505838468310488)
28
(0.015275439238188256, 0.230484608811555)
33
(0.013355998416664799, 0.21666155812294574)
38
(0.01159513810350752, 0.19990532286935067)
43
(0.010446572736107501, 0.19029679615613682)
48
(0.0095094653280709471, 0.18125285119954959)
53
(0.0086495229650470021, 0.17265634859582538)
58
(0.0078186129103578889, 0.16444494249990702)
for n in [14 + i*5 for i in range(10)]: print n c = chars(n) print c ar.append((n,c[0])) le.append((n,c[1])) 
        
14
(0.028117850600837681, 0.31813455937632162)
19
(0.021056710860006524, 0.27338728230989473)
24
(0.017492634715459764, 0.24717677830402493)
29
(0.014831007544140384, 0.22787789895856853)
34
(0.01297620092240348, 0.21210309745068073)
39
(0.011416791291913562, 0.19984909317484656)
44
(0.010266481510340798, 0.188431058020544)
49
(0.0092992180397503347, 0.17870290350894635)
54
(0.0084368787878254681, 0.17030922149658445)
59
(0.0078122219801313054, 0.16307371268188639)
14
(0.028117850600837681, 0.31813455937632162)
19
(0.021056710860006524, 0.27338728230989473)
24
(0.017492634715459764, 0.24717677830402493)
29
(0.014831007544140384, 0.22787789895856853)
34
(0.01297620092240348, 0.21210309745068073)
39
(0.011416791291913562, 0.19984909317484656)
44
(0.010266481510340798, 0.188431058020544)
49
(0.0092992180397503347, 0.17870290350894635)
54
(0.0084368787878254681, 0.17030922149658445)
59
(0.0078122219801313054, 0.16307371268188639)
list_plot(ar) 
       
logar = [(n,log(a)) for n,a in ar] list_plot(logar) 
       
list_plot(le) 
       
logle = [(n,log(a)) for n,a in le] list_plot(logle)