Finding Volume-Monte Carlo Method

Computer Science Level 5
Given an Icosahedron and its 12 Vertices. Find the intersecting volume of 10 cylinders of radius 1. Each cylinders centerline passes through the centroid of two faces(opposite faces). You can use a graphics package such as GeoGebra to aid in solving the problem.
The vertices of the icosahedron are as follows:
$(\pm e,0,\pm 1),(\pm 1,\pm e,0),(0,\pm 1,\pm e)$
Where $\displaystyle e=\frac{1+ \sqrt{5}}{2}$ is the Golden Ratio.
The answer is 4.27.

1 solution

Frank Petiprin
Jan 9, 2020
Program has 3 parts
I) Procedure Find_Planes: Using combination of 12 items taken 3 at a time to find all 3 points
that are 2 units apart.Each grouping of three points is a face of the ICOS. The
Centroid of the face is an equation of a plane perpendicular to the Cylinder through the origin.
                          (xC,yC,zC) -> xC*x+yC*y+zC*z=0 (Plane)
II) Procedure DsqC: will accept an array of random pts. (xp,yp,zp) an determine if they are
contained in one of the ten cylinders by using the Cylinders associated plane.
III) Procedure Main will generate the random points and call the two procedures and keep track of results
import numpy as np
from itertools import combinations
def Find_Planes():
    global Plane #Array to store the equation of ten planes each perpendicular to a cylinder at the origin.
    e,indx,comb=(1+np.sqrt(5))/2,1,combinations([1, 2, 3,4,5,6,7,8,9,10,11,12],3)
    Vert=np.array([[0,0,0],[e,0,1],[-e,0,1],[-e,0,-1],[e,0,-1],[-1,-e,0],[-1,e,0],[1,e,0],#Vertices of the ICOS
                   [1,-e,0],[0,1,e],[0,1,-e],[0,-1,-e],[0,-1,e]], np.float)
    Face1,Face2,Face3=np.zeros((21,3),np.float),np.zeros((21,3),np.float),np.zeros((21,3),np.float)
    Centr=np.zeros((21,3),np.float) #store centroids of each Face
    for i in list(comb):#Find all combinations of 3 Vert. 2 apart.Each Vert. of ICOS is assigned a digit 1 to 12 
        In1,In2,In3=Vert[i[0]],Vert[i[1]],Vert[i[2]]#(e,0,1) is a 1,(-e,0,1) is a 2 etc.. 
        Dis12=np.sqrt(((In1[0]-In2[0])**2+(In1[1]-In2[1])**2+(In1[2]-In2[2])**2))#distance between two points
        Dis13=np.sqrt(((In1[0]-In3[0])**2+(In1[1]-In3[1])**2+(In1[2]-In3[2])**2))
        Dis23=np.sqrt(((In3[0]-In2[0])**2+(In3[1]-In2[1])**2+(In3[2]-In2[2])**2))
        TorF=(Dis12==2.0)and(Dis13==2.0)and(Dis23==2.0)
        if(TorF):#If True the 3 points are 2 units distance from each other and we have a Face.
            Face1[indx],Face2[indx],Face3[indx] =In1,In2,In3 #In1,In2,In3 are points in 3-Spacde 
            indx+=1
    Centr=np.array((Face1+Face2+Face3)/3) #Find Centroid
    b_set = set(tuple(x) for x in Centr)
    Centr = [ list(x) for x in b_set ]
    Plane,indx=[[0,0,0]]*11,1#Of the 20 centroids only 10 are unique. Each giving an equation of a plane.
    for i in range(0,20):#Loop allows a centroid into array Plane only if it is unique.(Difference from the previous)
        val,valn=Centr[i],[-Centr[i][0],-Centr[i][1],-Centr[i][2]]
        if not((val in Plane) or (valn in Plane)):
            Plane[indx]=val
            indx+=1
    Plane=np.delete(np.array(np.append(Plane,np.zeros([len(Plane),1]),1)),0,0)
    return    #Refer above: Delete row of 0's and Add col. of 0's

def DsqC(xpl,ypl,zpl,con):#DsqC will return points(i.e. arrays (px,py,pz)) contained in the cylinder    
    global px,py,pz,radSQ #associated with plane xpl*x+ypl*y+zpl*z=con
#Equation of line X=(px,py,pz)+t*(xpl,ypl,zpl) that is perpendicular to the plane and passes through (px,py,pz)
    tNumer=(con-np.multiply(xpl,px)-np.multiply(ypl,py)-np.multiply(zpl,pz))
    tDenom=(np.multiply(xpl,xpl)+np.multiply(ypl,ypl)+np.multiply(zpl,zpl))
    t=np.divide(tNumer,tDenom) #Solving for t gives a point on the plane and on the line X
    xptP,yptP,zptP=px+t*xpl,py+t*ypl,pz+t*zpl #Point (xptP,yptP,zptP) is on the plane and the line X
    dsqC=np.array(xptP**2+yptP**2+zptP**2)#Square of the Distance (xptP,yptP,zptP) is from (0,0,0)
    Result=(dsqC<=radSQ) #Result is a True or False array. If True then a point was in the intersection.
    px,py,pz=px[Result],py[Result],pz[Result] #px,py,pz contains only points in the intersection
    return

#Begin Procedures Main
global px,py,pz,radSQ,Plane
seed=9015
#np.random.seed(seed) #Use as neded for testing 
CylColor=['Green','Blue','Red','Grey','Yellow','Brown','Orange','Purple-Dark','Purple Lite','Pink']
Find_Planes() #Find Ten planes perpendicular to each cylinder at the Origin.
ind,Trials,Attem,TotVolCyls,cntHits=0,20,50000000,0,0#Index,Trials,Attempts,Averageof Trials,Count Of Intersects
TarS,rad=1.2,1 #Approximation of target cube was determined by using GeoGebra (Graphics Software)
radSQ,TarVol=rad**2,(2*TarS)**3 #Vol. of Target Cube. 
for i in range(1,Trials+1):
    px,py=np.random.uniform(-TarS,TarS,Attem),np.random.uniform(-TarS,TarS,Attem)
    pz=np.random.uniform(-TarS,TarS,Attem)
    for j in range(0,10):#Each time through the loop will eliminate points not in one of the TEN Cylinders.
        x,y,z,con=Plane[j][0],Plane[j][1],Plane[j][2],Plane[j][3]
        DsqC(x,y,z,con)
        print(CylColor[j],' Hits',len(px))
        cntHits=len(px)
    VolCyl=(cntHits/Attem)*TarVol
    print('Total Hits',cntHits,'Vol. Of The Cylinders Intersect',VolCyl,'Trial',i)
    print('------------------------------------------------------------------')
    TotVolCyls+=VolCyl
print('Average Volume of Intersections',TotVolCyls/Trials,'Each Trial made ',Attem,'Attempts')
#Run Of Twenty Trials
Green  Hits 28370364
Blue  Hits 21364746
Red  Hits 17078212
Grey  Hits 16350647
Yellow  Hits 15912056
Brown  Hits 15638481
Orange  Hits 15578529
Purple-Dark  Hits 15530236
Purple Lite  Hits 15493970
Pink  Hits 15469474
Total Hits 15469474 Vol. Of The Cylinders Intersect 4.277000171519999 Trial 1
------------------------------------------------------------------
Green  Hits 28360598
Blue  Hits 21359823
Red  Hits 17075686
Grey  Hits 16350367
Yellow  Hits 15911522
Brown  Hits 15639077
Orange  Hits 15579082
Purple-Dark  Hits 15531450
Purple Lite  Hits 15495452
Pink  Hits 15470903
Total Hits 15470903 Vol. Of The Cylinders Intersect 4.27739526144 Trial 2
------------------------------------------------------------------
Green  Hits 28371901
Blue  Hits 21363499
Red  Hits 17076779
Grey  Hits 16351105
Yellow  Hits 15913659
Brown  Hits 15642136
Orange  Hits 15581717
Purple-Dark  Hits 15533575
Purple Lite  Hits 15497205
Pink  Hits 15472388
Total Hits 15472388 Vol. Of The Cylinders Intersect 4.27780583424 Trial 3
------------------------------------------------------------------
Green  Hits 28368550
Blue  Hits 21361018
Red  Hits 17073257
Grey  Hits 16347108
Yellow  Hits 15909114
Brown  Hits 15637113
Orange  Hits 15577536
Purple-Dark  Hits 15529629
Purple Lite  Hits 15492933
Pink  Hits 15468201
Total Hits 15468201 Vol. Of The Cylinders Intersect 4.27664821248 Trial 4
------------------------------------------------------------------
Green  Hits 28366712
Blue  Hits 21358304
Red  Hits 17068930
Grey  Hits 16343351
Yellow  Hits 15905610
Brown  Hits 15633751
Orange  Hits 15573616
Purple-Dark  Hits 15525763
Purple Lite  Hits 15489290
Pink  Hits 15464443
Total Hits 15464443 Vol. Of The Cylinders Intersect 4.275609200639999 Trial 5
------------------------------------------------------------------
Green  Hits 28362602
Blue  Hits 21361880
Red  Hits 17078142
Grey  Hits 16354456
Yellow  Hits 15916402
Brown  Hits 15643956
Orange  Hits 15584252
Purple-Dark  Hits 15536165
Purple Lite  Hits 15499881
Pink  Hits 15475174
Total Hits 15475174 Vol. Of The Cylinders Intersect 4.278576107519999 Trial 6
------------------------------------------------------------------
Green  Hits 28360460
Blue  Hits 21357588
Red  Hits 17075246
Grey  Hits 16351579
Yellow  Hits 15914297
Brown  Hits 15641872
Orange  Hits 15581536
Purple-Dark  Hits 15533654
Purple Lite  Hits 15497257
Pink  Hits 15472532
Total Hits 15472532 Vol. Of The Cylinders Intersect 4.2778456473599995 Trial 7
------------------------------------------------------------------
Green  Hits 28367851
Blue  Hits 21362680
Red  Hits 17076530
Grey  Hits 16351757
Yellow  Hits 15913857
Brown  Hits 15640679
Orange  Hits 15580448
Purple-Dark  Hits 15532338
Purple Lite  Hits 15495964
Pink  Hits 15471291
Total Hits 15471291 Vol. Of The Cylinders Intersect 4.27750253568 Trial 8
------------------------------------------------------------------
Green  Hits 28366501
Blue  Hits 21362528
Red  Hits 17078640
Grey  Hits 16352960
Yellow  Hits 15914871
Brown  Hits 15643462
Orange  Hits 15583515
Purple-Dark  Hits 15535072
Purple Lite  Hits 15498735
Pink  Hits 15473974
Total Hits 15473974 Vol. Of The Cylinders Intersect 4.278244331519999 Trial 9
------------------------------------------------------------------
Green  Hits 28366036
Blue  Hits 21358588
Red  Hits 17076729
Grey  Hits 16350822
Yellow  Hits 15912774
Brown  Hits 15640991
Orange  Hits 15580941
Purple-Dark  Hits 15532778
Purple Lite  Hits 15496525
Pink  Hits 15471537
Total Hits 15471537 Vol. Of The Cylinders Intersect 4.277570549759999 Trial 10
------------------------------------------------------------------
Green  Hits 28369919
Blue  Hits 21361477
Red  Hits 17074678
Grey  Hits 16350010
Yellow  Hits 15913319
Brown  Hits 15640570
Orange  Hits 15580559
Purple-Dark  Hits 15532562
Purple Lite  Hits 15496360
Pink  Hits 15471673
Total Hits 15471673 Vol. Of The Cylinders Intersect 4.277608151039999 Trial 11
------------------------------------------------------------------
Green  Hits 28366934
Blue  Hits 21360150
Red  Hits 17072929
Grey  Hits 16347516
Yellow  Hits 15910412
Brown  Hits 15638894
Orange  Hits 15578632
Purple-Dark  Hits 15530257
Purple Lite  Hits 15493844
Pink  Hits 15469188
Total Hits 15469188 Vol. Of The Cylinders Intersect 4.27692109824 Trial 12
------------------------------------------------------------------
Green  Hits 28367162
Blue  Hits 21359376
Red  Hits 17076453
Grey  Hits 16351056
Yellow  Hits 15912786
Brown  Hits 15640222
Orange  Hits 15580167
Purple-Dark  Hits 15531573
Purple Lite  Hits 15495039
Pink  Hits 15470428
Total Hits 15470428 Vol. Of The Cylinders Intersect 4.2772639334399996 Trial 13
------------------------------------------------------------------
Green  Hits 28366247
Blue  Hits 21358069
Red  Hits 17071574
Grey  Hits 16347013
Yellow  Hits 15907790
Brown  Hits 15635289
Orange  Hits 15574954
Purple-Dark  Hits 15526721
Purple Lite  Hits 15490407
Pink  Hits 15466121
Total Hits 15466121 Vol. Of The Cylinders Intersect 4.276073134079999 Trial 14
------------------------------------------------------------------
Green  Hits 28366611
Blue  Hits 21359418
Red  Hits 17074453
Grey  Hits 16350188
Yellow  Hits 15911067
Brown  Hits 15638745
Orange  Hits 15578210
Purple-Dark  Hits 15529886
Purple Lite  Hits 15493646
Pink  Hits 15468987
Total Hits 15468987 Vol. Of The Cylinders Intersect 4.27686552576 Trial 15
------------------------------------------------------------------
Green  Hits 28362482
Blue  Hits 21355688
Red  Hits 17070388
Grey  Hits 16345907
Yellow  Hits 15909187
Brown  Hits 15636816
Orange  Hits 15577170
Purple-Dark  Hits 15528830
Purple Lite  Hits 15492432
Pink  Hits 15467875
Total Hits 15467875 Vol. Of The Cylinders Intersect 4.276558079999999 Trial 16
------------------------------------------------------------------
Green  Hits 28368957
Blue  Hits 21360647
Red  Hits 17076988
Grey  Hits 16354074
Yellow  Hits 15915595
Brown  Hits 15644123
Orange  Hits 15584396
Purple-Dark  Hits 15536486
Purple Lite  Hits 15500130
Pink  Hits 15475532
Total Hits 15475532 Vol. Of The Cylinders Intersect 4.278675087359999 Trial 17
------------------------------------------------------------------
Green  Hits 28366145
Blue  Hits 21359210
Red  Hits 17072228
Grey  Hits 16346732
Yellow  Hits 15908464
Brown  Hits 15636658
Orange  Hits 15576231
Purple-Dark  Hits 15528323
Purple Lite  Hits 15491637
Pink  Hits 15466955
Total Hits 15466955 Vol. Of The Cylinders Intersect 4.2763037183999995 Trial 18
------------------------------------------------------------------
Green  Hits 28365829
Blue  Hits 21359476
Red  Hits 17075013
Grey  Hits 16350285
Yellow  Hits 15913703
Brown  Hits 15642026
Orange  Hits 15582200
Purple-Dark  Hits 15533915
Purple Lite  Hits 15497770
Pink  Hits 15473149
Total Hits 15473149 Vol. Of The Cylinders Intersect 4.278016235519999 Trial 19
------------------------------------------------------------------
Green  Hits 28363594
Blue  Hits 21356520
Red  Hits 17072170
Grey  Hits 16348249
Yellow  Hits 15909871
Brown  Hits 15638026
Orange  Hits 15578252
Purple-Dark  Hits 15530155
Purple Lite  Hits 15493727
Pink  Hits 15469374
Total Hits 15469374 Vol. Of The Cylinders Intersect 4.27697252352 Trial 20
------------------------------------------------------------------
Average Volume of Intersections 4.277272766975999 Each Trial made  50000000 Attempts
You can use np.vectorize to greatly speed up the computation because it's parallel.
Julian Poon - 10 months ago
Finding Volume-Monte Carlo Method

The answer is 4.27.

1 solution

0 pending reports
