cubi intersecting sphere surface - sphere surface sampling
Tobias
I urgently need an answer to following:
My task is to discretize (to sample) the surface of the unit sphere.
In terms of simplicity I've chosen to do this by deviding the
surrounding cubus (borderlenght=2) in N*N*N little cubi
(borderlenght=2/N). Only those little cubi that intersect the surface
of the unitsphere are of interest.
My question now:
How many little cubi will intersect the surface of the unitsphere in
dependency of N ?
Somehow my brain seems (temporarily) too small for sufficient
thoughts. Thus I've investigated it experimentally. The result seems
to be:
((N/2)*(N/2)+1)*8 little cubi intersect the surface of the
unitsphere.
If correct, why ?? Can anyone help me ?
Greetings
(mad) Tobias
The Last Danish Pastry
news:94040883.03071...@posting.google.com...
Hi (mad) Tobias,
For N=2, your formula says that 16 (of 8) little cubi intersect the sphere.
This is surely wrong.
As regards sampling the surface of a sphere you might want to look at Dave
Seaman's reply in the thread starting at
http://tinylink.com/?qAd8iCXKHK
--
Clive Tooth
http://www.clivetooth.dk
Tobias
>
> For N=2, your formula says that 16 (of 8) little cubi intersect the sphere.
> This is surely wrong.
>
> As regards sampling the surface of a sphere you might want to look at Dave
> Seaman's reply in the thread starting at
> http://tinylink.com/?qAd8iCXKHK
Thank You Clive,
of course You're right. I forgot the constraint N>3.
Thanks for the website tip.
Tobias
HP
The first few values are
n n_cut
1 1
2 8
3 26 (1 central cube of 27 not hit)
4 56 (8 central cubes of 64 not hit)
Looking up [1,8,26,56] in the On-Line Encyclopedia of Integer Sequences
gives
http://www.research.att.com/projects/OEIS?Anum=A005897 :
Points on surface of cube: 6n^2 + 2 (coordination sequence for b.c.c.
lattice).
The continuation of the sequence is:
1,8,26,56,98,152,218,296,386,488,602,728,866,1016,1178,1352,...
Hugo Pfoertner
http://www.pfoertner.org/
The Last Danish Pastry
news:94040883.03071...@posting.google.com...
> > Hi (mad) Tobias,
Well...
I take each cubus [there is really no such word in English, but the term
seems useful here] to be a closed cube (that is, it includes all its faces,
edges and vertices). So two adjacent cubi share a common square face.
For N=4 your formula has 40 cubi intersecting the sphere.
But it seems to me that only the central 8 escape intersection, leading to
the conclusion that 56 (=4^3-2^3) intersect the sphere.
For N=5, I find that 98 cubi intersect the sphere. Your formula gives a
non-integer answer.
For N=6, we must be very careful how we count the cubi. Several of them
intersect our sphere in just a single point. I find that 176 of the cubi
intersect the sphere (48 of them at only a single point). So if we took the
cubi to be open cubes that number would go down to 128. Anyway, your formula
gives 80.
Of course, my numbers could be wrong.
The Last Danish Pastry
news:89c716bb.03071...@posting.google.com...
Ah... for n=6 that sequence gives 152. This is the mean of two answers (176
and 128) that I gave in another post in this thread and corresponds to
viewing the cubi as neither open nor closed. I have no idea how the
expression 6n^2+2 arises, though.
Dave Seaman
> "HP" <yae...@netscape.net> wrote in message
> news:89c716bb.03071...@posting.google.com...
>> The first few values are
>>
>> n n_cut
>> 1 1
>> 2 8
>> 3 26 (1 central cube of 27 not hit)
>> 4 56 (8 central cubes of 64 not hit)
>>
>> Looking up [1,8,26,56] in the On-Line Encyclopedia of Integer Sequences
>> gives
>> http://www.research.att.com/projects/OEIS?Anum=A005897 :
>> Points on surface of cube: 6n^2 + 2 (coordination sequence for b.c.c.
>> lattice).
>>
>> The continuation of the sequence is:
>> 1,8,26,56,98,152,218,296,386,488,602,728,866,1016,1178,1352,...
> Ah... for n=6 that sequence gives 152. This is the mean of two answers (176
> and 128) that I gave in another post in this thread and corresponds to
> viewing the cubi as neither open nor closed. I have no idea how the
> expression 6n^2+2 arises, though.
I suppose one could view each of the "cubi" as an n-dimensional interval
that is a Cartesian product of half-open intervals, so that they exactly
partition the space. This would lead to the half-way answer, I think.
I wrote a lisp program to compute the results up to n = 10 and I seem to
be in agreement with most of the results that have been posted, but there
are some differences compared to the A005897 sequence for n > 5:
n count
- -----
1 1
2 8
3 26
4 56
5 98
6 176 or 128
7 194
8 272
9 362
10 464 or 416
I also thought of looking up the sequence, but my sequence gave no matches.
--
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>
Hugo Pfoertner
>
6*n^2+2 is exactly what the sequence title says:
(Number of) Points on surface of cube. Thanks to Neil Sloane
for clarifying this.
A 1*1*1 cube has 6*1+2 (lattice) points
2*2*2 -> 26 points
3*3*3 -> 56 points
n*n*n -> 8 + 12*(n-1) + 6*(n-1)^2 = 6*n^2 + 2
vertices points on edges pts on faces
Number of cut sub-cubes (cut means not only touched)
= the number of lattice points on the surface of the
"(n-1)-subdivided" cube, but only for n<7.
See Dave Seaman's message and my reply.
Hugo Pfoertner
Hugo Pfoertner
I have now written a little Fortran program available at
http://www.randomwalk.de/sequences/cutcub.txt ,
including results for n<=100.
Here are the first few terms:
3 26
4 56
5 98
6 152
7 194
8 272
9 362
10 440
11 530
12 656
13 746
14 872
15 1034
16 1160
17 1298
18 1496
19 1658
20 1856
I have counted cubes only touched by the cutting sphere, with all
other vertices either inside or outside as 1/2, because they occur
always as inside/outside "pairs". If either > or >= is used
in the radius comparisons then I can reproduce both variants of
Dave's n=6 and n=10 results.
Hugo Pfoertner
http://www.pfoertner.org/
Dave Seaman
I have downloaded your Fortran program and checked it against my lisp
program (modified to print the average of the upper and lower results).
They agree.
The Last Danish Pastry
news:3F14A5D3...@abouthugo.de...
> The Last Danish Pastry wrote:
> >
> > "HP" <yae...@netscape.net> wrote in message
> > news:89c716bb.03071...@posting.google.com...
> >
> > > tma...@optik.uni-erlangen.de (Tobias) wrote in message
> > news:<94040883.03071...@posting.google.com>...
> > > >[snip]
> > >
> > > The first few values are
> > >
> > > n n_cut
> > > 1 1
> > > 2 8
> > > 3 26 (1 central cube of 27 not hit)
> > > 4 56 (8 central cubes of 64 not hit)
> > >
> > > Looking up [1,8,26,56] in the On-Line Encyclopedia of Integer
Sequences
> > > gives
> > > http://www.research.att.com/projects/OEIS?Anum=A005897 :
> > > Points on surface of cube: 6n^2 + 2 (coordination sequence for b.c.c.
> > > lattice).
> > >
> > > The continuation of the sequence is:
> > > 1,8,26,56,98,152,218,296,386,488,602,728,866,1016,1178,1352,...
> >
> > Ah... for n=6 that sequence gives 152. This is the mean of two answers
(176
> > and 128) that I gave in another post in this thread and corresponds to
> > viewing the cubi as neither open nor closed. I have no idea how the
> > expression 6n^2+2 arises, though.
>
> 6*n^2+2 is exactly what the sequence title says:
> (Number of) Points on surface of cube. Thanks to Neil Sloane
> for clarifying this.
>
> A 1*1*1 cube has 6*1+2 (lattice) points
> 2*2*2 -> 26 points
> 3*3*3 -> 56 points
> n*n*n -> 8 + 12*(n-1) + 6*(n-1)^2 = 6*n^2 + 2
> vertices points on edges pts on faces
>
> Number of cut sub-cubes (cut means not only touched)
> = the number of lattice points on the surface of the
> "(n-1)-subdivided" cube, but only for n<7.
>
> See Dave Seaman's message and my reply.
Thanks for that. I realised that 6n^2+2 was the number of lattice points on
the surface of a cube. [Most easily thought of, I suppose, as
(n+1)^3-(n-1)^3.] When I said "I have no idea how the expression 6n^2+2
arises" I (foolishly) meant "I have no idea why 6n^2+2 is the solution to
the original poster's question". I had not realised that it only applies for
n<7.
The Last Danish Pastry
news:bf2naf$prc$1...@mozo.cc.purdue.edu...
I have written a C# program and it agrees with both of you for n<=100.
I have included the relevant class declaration at the end of this post.
Summary of the problem and some suggested notation:
Let n be a positive integer. Consider a cube C, of side n, and its insphere
S. Consider the set of n^3 unit cubes, each of side 1, whose faces are
parallel to the faces of C and whose union is C. Each unit cube is closed,
that is, it includes its interior, and all its faces, edges and vertices.
Thus, in general, a unit cube will intersect each of its 6 surrounding unit
cubes in a square and, in general, each vertex is part of 8 unit cubes.
For each unit cube we may compute an "intersection value" as follows:
# if all the vertices of the unit cube are inside S, the intersection value
is 0.
# if all the vertices of the unit cube are outside S, the intersection value
is 0.
# if at least one vertex is inside S and at least one vertex is outside S,
the intersection value is 1.
# otherwise the unit cube has at least one vertex on S and all its other
vertices are either all inside or all outside S. In this case its
intersection value is 1/2.
Let the sum of the intersection values across all n^3 unit cubes be T(n).
So, for example, T(1)=0, T(2)=8 and T(6)=152.
The area of S is 4*pi*(n/2)^2 and we might expect T(n) to be about this
value, ie pi*n^2.
Computing T(n) and T(n)/(pi*n^2) for various n we get:
| n T(n) T(n)/(pi*n^2)
|
| 1 0 0.000000
| 2 8 0.636620
| 3 26 0.919562
| 4 56 1.114085
| 5 98 1.247775
| 6 152 1.343975
| 7 194 1.260247
| 8 272 1.352817
| 9 362 1.422570
| 10 440 1.400563
|
| 100 47,000 1.496056
| 101 48,002 1.497844
| 102 48,992 1.498908
| 103 49,826 1.494967
| 104 50,936 1.499023
| 105 51,770 1.494685
| 106 52,808 1.496022
| 107 53,810 1.496048
| 108 54,848 1.496799
| 109 55,850 1.496306
| 110 56,816 1.494636
|
| 200 188,432 1.499494
| 201 190,202 1.498556
| 202 192,056 1.498219
| 203 193,970 1.498279
| 204 196,040 1.499459
| 205 197,810 1.498272
| 206 199,880 1.499288
| 207 201,674 1.498164
| 208 203,648 1.498317
| 209 205,682 1.498835
| 210 207,680 1.499016
|
| 500 1,177,832 1.499662
| 501 1,182,698 1.499852
| 502 1,187,072 1.499408
| 503 1,192,082 1.499755
| 504 1,196,672 1.499561
| 505 1,201,514 1.499672
| 506 1,206,152 1.499516
| 507 1,211,114 1.499751
| 508 1,215,704 1.499514
| 509 1,220,498 1.499518
| 510 1,225,496 1.499760
|
| 1,000 4,712,000 1.499876
| 1,001 4,721,378 1.499860
This suggests that T(n) is asymptotic to (3/2)*pi*n^2.
I assume this is all well-known.
--
Clive Tooth
http://www.clivetooth.dk
public class CubeletsClass {
private int Inside;
private int N;
public int NIncrement;
private int NN;
public int NStart;
public int NStop;
private int On;
private int Outside;
public CubeletsClass(int Start, int Increment, int Stop) {
NStart= Start;
NIncrement= Increment;
NStop= Stop;
} // constructor
private void Look(int x, int y, int z) {
int a= U.Square(2*x-N)+U.Square(2*y-N)+U.Square(2*z-N);
if (a<NN) {
++Inside;
} else if (a>NN) {
++Outside;
} else {
++On;
}
} // Look
public void Counter() {
int Count;
int x;
int y;
int z;
for (N= NStart; N<=NStop; N+= NIncrement) {
Count= 0;
NN= N*N;
for (x= 0; x<N; ++x) {
for (y= 0; y<N; ++y) {
for (z= 0; z<N; ++z) {
Inside= 0;
On= 0;
Outside= 0;
Look(x, y, z );
Look(x, y, z+1);
Look(x, y+1, z );
Look(x, y+1, z+1);
Look(x+1, y, z );
Look(x+1, y, z+1);
Look(x+1, y+1, z );
Look(x+1, y+1, z+1);
if (Inside>0 && Outside>0) {
Count+= 2;
} else if (On>0) {
Count+= 1;
} else {
//
}
} // for z
} // for y
} // for x
if (Count%2!=0) {
U.Fail("Count%2<>0");
}
Count/= 2;
U.Emit(
U.Commas(N, 5)+" "+
U.Commas(Count, 11)+" "+
U.FNum(Count/(Math.PI*NN), 6)+
""
);
} // for N
} // Counter
} // CubeletsClass