Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #144756 > unrolled thread

Re: Choosing a random point on a sphere surface

Back to article view | Back to comp.lang.c

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Choosing a random point on a sphere surface Clifford Heath <no.spam@please.net> - 2019-06-12 09:47 +1000
    Re: Choosing a random point on a sphere surface Keith Thompson <kst-u@mib.org> - 2019-06-11 18:33 -0700
      Re: Choosing a random point on a sphere surface James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-06-11 22:30 -0400
        Re: Choosing a random point on a sphere surface Clifford Heath <no.spam@please.net> - 2019-06-12 12:54 +1000
        Re: Choosing a random point on a sphere surface "Chris M. Thomasson" <invalid_chris_thomasson_invalid@invalid.com> - 2019-06-12 00:42 -0700
    Re: Choosing a random point on a sphere surface fir <profesor.fir@gmail.com> - 2019-06-18 11:21 -0700

#144756 — Re: Choosing a random point on a sphere surface

On 11/6/19 1:54 am, Stefan Ram wrote:
>    The following picture shows a unit ball (sphere) with a width
>    and a height of «1».

I just came up with a very nice alternate way to uniformly choose a 
point on a unit sphere, with arbitrary granularity. Use a hierarchical 
triangular mesh with a random binary bit-string of 3+2n bits. Convert 
the HTM value into your chosen coordinate system, job done.

HTM is a generalised coordinate system for points on the globe, based on 
an iterated triangular subdivision of the sides of an octahedron.

<http://www.skyserver.org/htm/>
<https://www.microsoft.com/en-us/research/publication/indexing-the-sphere-with-the-hierarchical-triangular-mesh/>

Clifford Heath.

[toc] | [next] | [standalone]

#144758

Clifford Heath <no.spam@please.net> writes:
> On 11/6/19 1:54 am, Stefan Ram wrote:
>>    The following picture shows a unit ball (sphere) with a width
>>    and a height of «1».
>
> I just came up with a very nice alternate way to uniformly choose a 
> point on a unit sphere, with arbitrary granularity. Use a hierarchical 
> triangular mesh with a random binary bit-string of 3+2n bits. Convert 
> the HTM value into your chosen coordinate system, job done.
>
> HTM is a generalised coordinate system for points on the globe, based on 
> an iterated triangular subdivision of the sides of an octahedron.
>
> <http://www.skyserver.org/htm/>
> <https://www.microsoft.com/en-us/research/publication/indexing-the-sphere-with-the-hierarchical-triangular-mesh/>

I don't believe the selection is uniform.

Quoting from your second link (emphasis added):

    We describe a method to subdivide the surface of a sphere into
    spherical triangles of similar, *but not identical*, shapes
    and sizes.

We start with the surface of the sphere partitioned into 8 identical
spherical triangles, with 90-degree vertices.  Considering one
of the 8 triangles, we draw great circle segments connecting the
midpoints of the edges, partitioning it into 4 smaller triangles.
I believe the outer 3 triangles are congruent to each other, but
the central one is not.

It looks like a useful way to define a coordinate system on the
surface of a sphere, but it doesn't produce equal-area triangles
(and it's not intended to).

I don't quite have the math to confirm or refute this.  Anyone else?

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Will write code for food.
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#144760

On 6/11/19 9:33 PM, Keith Thompson wrote:
> Clifford Heath <no.spam@please.net> writes:
...
>> I just came up with a very nice alternate way to uniformly choose a 
>> point on a unit sphere, with arbitrary granularity. Use a hierarchical 
>> triangular mesh with a random binary bit-string of 3+2n bits. Convert 
>> the HTM value into your chosen coordinate system, job done.
>>
>> HTM is a generalised coordinate system for points on the globe, based on 
>> an iterated triangular subdivision of the sides of an octahedron.
>>
>> <http://www.skyserver.org/htm/>
>> <https://www.microsoft.com/en-us/research/publication/indexing-the-sphere-with-the-hierarchical-triangular-mesh/>
> 
> I don't believe the selection is uniform.
> 
> Quoting from your second link (emphasis added):
> 
>     We describe a method to subdivide the surface of a sphere into
>     spherical triangles of similar, *but not identical*, shapes
>     and sizes.
> 
> We start with the surface of the sphere partitioned into 8 identical
> spherical triangles, with 90-degree vertices.  Considering one
> of the 8 triangles, we draw great circle segments connecting the
> midpoints of the edges, partitioning it into 4 smaller triangles.
> I believe the outer 3 triangles are congruent to each other, but
> the central one is not.
> 
> It looks like a useful way to define a coordinate system on the
> surface of a sphere, but it doesn't produce equal-area triangles
> (and it's not intended to).
> 
> I don't quite have the math to confirm or refute this.  Anyone else?

The document itself says that, at any given level of sub-division, the
biggest triangles have roughly twice the area of the smallest triangles,
so it's definitely not a way to produce a spherically uniform set of points.

[toc] | [prev] | [next] | [standalone]

#144761

On 12/6/19 12:30 pm, James Kuyper wrote:
> On 6/11/19 9:33 PM, Keith Thompson wrote:
>> Clifford Heath <no.spam@please.net> writes:
> ...
>>> I just came up with a very nice alternate way to uniformly choose a
>>> point on a unit sphere, with arbitrary granularity. Use a hierarchical
>>> triangular mesh with a random binary bit-string of 3+2n bits. Convert
>>> the HTM value into your chosen coordinate system, job done.
>>>
>>> HTM is a generalised coordinate system for points on the globe, based on
>>> an iterated triangular subdivision of the sides of an octahedron.
>>>
>>> <http://www.skyserver.org/htm/>
>>> <https://www.microsoft.com/en-us/research/publication/indexing-the-sphere-with-the-hierarchical-triangular-mesh/>
>>
>> I don't believe the selection is uniform.
>>
>> Quoting from your second link (emphasis added):
>>
>>      We describe a method to subdivide the surface of a sphere into
>>      spherical triangles of similar, *but not identical*, shapes
>>      and sizes.
>>
>> We start with the surface of the sphere partitioned into 8 identical
>> spherical triangles, with 90-degree vertices.  Considering one
>> of the 8 triangles, we draw great circle segments connecting the
>> midpoints of the edges, partitioning it into 4 smaller triangles.
>> I believe the outer 3 triangles are congruent to each other, but
>> the central one is not.
>>
>> It looks like a useful way to define a coordinate system on the
>> surface of a sphere, but it doesn't produce equal-area triangles
>> (and it's not intended to).
>>
>> I don't quite have the math to confirm or refute this.  Anyone else?
> 
> The document itself says that, at any given level of sub-division, the
> biggest triangles have roughly twice the area of the smallest triangles,
> so it's definitely not a way to produce a spherically uniform set of points.

Hmmm ok, that's a nuisance. Not true at the root octahedron of course, 
but after that it makes sense. I wonder if there's a way to skew the 
subdivision to triangles of equal area? That would probably require 
trig, I assume.

Still, it has some very useful properties, such as in a geospatial tree 
for clustering objects by locality, so perhaps some here would find it 
useful.

Clifford Heath.

[toc] | [prev] | [next] | [standalone]

#144762

On 6/11/2019 7:30 PM, James Kuyper wrote:
> On 6/11/19 9:33 PM, Keith Thompson wrote:
>> Clifford Heath <no.spam@please.net> writes:
> ...
>>> I just came up with a very nice alternate way to uniformly choose a
>>> point on a unit sphere, with arbitrary granularity. Use a hierarchical
>>> triangular mesh with a random binary bit-string of 3+2n bits. Convert
>>> the HTM value into your chosen coordinate system, job done.
>>>
>>> HTM is a generalised coordinate system for points on the globe, based on
>>> an iterated triangular subdivision of the sides of an octahedron.
>>>
>>> <http://www.skyserver.org/htm/>
>>> <https://www.microsoft.com/en-us/research/publication/indexing-the-sphere-with-the-hierarchical-triangular-mesh/>
>>
>> I don't believe the selection is uniform.
>>
>> Quoting from your second link (emphasis added):
>>
>>      We describe a method to subdivide the surface of a sphere into
>>      spherical triangles of similar, *but not identical*, shapes
>>      and sizes.
>>
>> We start with the surface of the sphere partitioned into 8 identical
>> spherical triangles, with 90-degree vertices.  Considering one
>> of the 8 triangles, we draw great circle segments connecting the
>> midpoints of the edges, partitioning it into 4 smaller triangles.
>> I believe the outer 3 triangles are congruent to each other, but
>> the central one is not.
>>
>> It looks like a useful way to define a coordinate system on the
>> surface of a sphere, but it doesn't produce equal-area triangles
>> (and it's not intended to).
>>
>> I don't quite have the math to confirm or refute this.  Anyone else?
> 
> The document itself says that, at any given level of sub-division, the
> biggest triangles have roughly twice the area of the smallest triangles,
> so it's definitely not a way to produce a spherically uniform set of points.
> 

Sounds very fractal... Humm...

[toc] | [prev] | [next] | [standalone]

#144968

W dniu środa, 12 czerwca 2019 01:47:33 UTC+2 użytkownik Clifford Heath napisał:
> On 11/6/19 1:54 am, Stefan Ram wrote:
> >    The following picture shows a unit ball (sphere) with a width
> >    and a height of «1».
> 
btw if someone wouldlike to visualise things 3d AND is afraid of using my closed source library he could use old glut.dll

its very old and supports oldschool opengl 1.1 (or 1.2 i dont remember) but its relatively easy (unlike modern ogl)
and could be used

if someone would want maybe i would write some simpel demo or something showing how to use it (i not used glut except one day or so but probably could try and show how to do it)

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web