Random 3D points uniformly distributed on an ellipse shaped window of a sphere
$begingroup$
How can I generate random points uniformly distributed on the surface of a sphere such that a line that originates at the center of the sphere, and passes through one of the points, will intersect a plane within a circle. Following are more illustrations and details to make this clearer. The white dots are the points, the red is the sphere, the black circle is the circle in the plane, the green is the elliptical cone enclosing the points:
Why not Point-rejection?
To generate random points uniformly distributed on the surface of a sphere, this works (pseudo Matlab code; where $n$ is the number of the points):
z = rand(n)*2-1
θ = rand(n)*2π
x = sqrt(1. - z.*z).*cos(θ)
y = sqrt(1. - z.*z).*sin(θ)
To generate random points uniformly distributed on the surface of a sphere within a circle shaped window, the following works:
α = .9
cosα = cos(α)
z = rand(n)*(cosα - 1.) - cosα
θ = rand(n)*2π
x = sqrt(1. - z.*z).*cos(θ)
y = sqrt(1. - z.*z).*sin(θ)
Notice that this algorithm is much more efficient than first generating points uniformly distributed on a sphere (using the previous algorithm) and then rejecting all the points that are outside the circle shaped window. I'm hoping for some mathematical-wizardry to answer my question, and in the same way it does not make any sense to use a point-rejection method for the circle shaped window problem, I hope to avoid it here too.
geometry 3d random
asked Sep 18 '14 at 0:16
12.yakir12.yakir
615
$endgroup$
|
show 1 more comment
$begingroup$
How can I generate random points uniformly distributed on the surface of a sphere such that a line that originates at the center of the sphere, and passes through one of the points, will intersect a plane within a circle. Following are more illustrations and details to make this clearer. The white dots are the points, the red is the sphere, the black circle is the circle in the plane, the green is the elliptical cone enclosing the points:
Why not Point-rejection?
To generate random points uniformly distributed on the surface of a sphere, this works (pseudo Matlab code; where $n$ is the number of the points):
z = rand(n)*2-1
θ = rand(n)*2π
x = sqrt(1. - z.*z).*cos(θ)
y = sqrt(1. - z.*z).*sin(θ)
To generate random points uniformly distributed on the surface of a sphere within a circle shaped window, the following works:
α = .9
cosα = cos(α)
z = rand(n)*(cosα - 1.) - cosα
θ = rand(n)*2π
x = sqrt(1. - z.*z).*cos(θ)
y = sqrt(1. - z.*z).*sin(θ)
Notice that this algorithm is much more efficient than first generating points uniformly distributed on a sphere (using the previous algorithm) and then rejecting all the points that are outside the circle shaped window. I'm hoping for some mathematical-wizardry to answer my question, and in the same way it does not make any sense to use a point-rejection method for the circle shaped window problem, I hope to avoid it here too.
geometry 3d random
asked Sep 18 '14 at 0:16
12.yakir12.yakir
615
$endgroup$
1
$begingroup$
What you call "cheating", which is simply the reject method, is by far the computationally simplest method and probably the overall best one. To refine it, one can include the cap delimited by the ellipse in the smallest cap delimited by a circle (this amounts to replacing $a$ and $b$ by $max(a,b)$) and reject from this slightly larger cap instead of from the whole sphere.
$endgroup$
– Did
Oct 15 '14 at 5:42
$begingroup$
I understand what you're saying, but I have to disagree: the efficiency of the rejection method inversely depends on the difference betweenaandb. If the formula for generating this distribution is ultra complicated then, yes, maybe it's not worth it, and only whenais a lot larger/smaller thanbthen this complicated and elusive formula will pay off. But since the formula for a circle shaped window was so straightforward, I hope that this extra step isn't that complicated.
$endgroup$
– 12.yakir
Oct 15 '14 at 8:41
$begingroup$
What do you disagree about? I see no contradiction between the factual part of your comment and mine (except that you probably mean the ratio $a/b$ instead of their difference $a-b$). Note that, if the regime of interest to you is $agg b$, this should be mentioned in the question.
$endgroup$
– Did
Oct 15 '14 at 8:46
$begingroup$
You are correct. I guess it all depends on how complicated the solution will be. I'm interested in whatever works in the best possible way. If it turns out that the analytic solution is ultra complicated then it's possible that even when the $a/b$ ratio is very large or small then it will still be slower than the rejection method. I'm hoping for something better. Better in the same way that the circle window method is better than producing uniform random points on a sphere and then rejecting the ones that are outside the circular window (this is relevant when you want $n$ points).
$endgroup$
– 12.yakir
Oct 15 '14 at 9:04
$begingroup$
Have you considered hit-and-run sampling?
$endgroup$
– Rahul
Jul 15 '18 at 4:31
|
show 1 more comment
$begingroup$
How can I generate random points uniformly distributed on the surface of a sphere such that a line that originates at the center of the sphere, and passes through one of the points, will intersect a plane within a circle. Following are more illustrations and details to make this clearer. The white dots are the points, the red is the sphere, the black circle is the circle in the plane, the green is the elliptical cone enclosing the points:
Why not Point-rejection?
To generate random points uniformly distributed on the surface of a sphere, this works (pseudo Matlab code; where $n$ is the number of the points):
z = rand(n)*2-1
θ = rand(n)*2π
x = sqrt(1. - z.*z).*cos(θ)
y = sqrt(1. - z.*z).*sin(θ)
To generate random points uniformly distributed on the surface of a sphere within a circle shaped window, the following works:
α = .9
cosα = cos(α)
z = rand(n)*(cosα - 1.) - cosα
θ = rand(n)*2π
x = sqrt(1. - z.*z).*cos(θ)
y = sqrt(1. - z.*z).*sin(θ)
Notice that this algorithm is much more efficient than first generating points uniformly distributed on a sphere (using the previous algorithm) and then rejecting all the points that are outside the circle shaped window. I'm hoping for some mathematical-wizardry to answer my question, and in the same way it does not make any sense to use a point-rejection method for the circle shaped window problem, I hope to avoid it here too.
geometry 3d random
asked Sep 18 '14 at 0:16
12.yakir12.yakir
615
$endgroup$
How can I generate random points uniformly distributed on the surface of a sphere such that a line that originates at the center of the sphere, and passes through one of the points, will intersect a plane within a circle. Following are more illustrations and details to make this clearer. The white dots are the points, the red is the sphere, the black circle is the circle in the plane, the green is the elliptical cone enclosing the points:
Why not Point-rejection?
To generate random points uniformly distributed on the surface of a sphere, this works (pseudo Matlab code; where $n$ is the number of the points):
z = rand(n)*2-1
θ = rand(n)*2π
x = sqrt(1. - z.*z).*cos(θ)
y = sqrt(1. - z.*z).*sin(θ)
To generate random points uniformly distributed on the surface of a sphere within a circle shaped window, the following works:
α = .9
cosα = cos(α)
z = rand(n)*(cosα - 1.) - cosα
θ = rand(n)*2π
x = sqrt(1. - z.*z).*cos(θ)
y = sqrt(1. - z.*z).*sin(θ)
Notice that this algorithm is much more efficient than first generating points uniformly distributed on a sphere (using the previous algorithm) and then rejecting all the points that are outside the circle shaped window. I'm hoping for some mathematical-wizardry to answer my question, and in the same way it does not make any sense to use a point-rejection method for the circle shaped window problem, I hope to avoid it here too.
geometry 3d random
geometry 3d random
asked Sep 18 '14 at 0:16
12.yakir12.yakir
615
asked Sep 18 '14 at 0:16
12.yakir12.yakir
615
edited Oct 27 '14 at 6:00
12.yakir
asked Sep 18 '14 at 0:16
12.yakir12.yakir
615
asked Sep 18 '14 at 0:16
12.yakir12.yakir
615
asked Sep 18 '14 at 0:16
12.yakir12.yakir
615
615
1
$begingroup$
What you call "cheating", which is simply the reject method, is by far the computationally simplest method and probably the overall best one. To refine it, one can include the cap delimited by the ellipse in the smallest cap delimited by a circle (this amounts to replacing $a$ and $b$ by $max(a,b)$) and reject from this slightly larger cap instead of from the whole sphere.
$endgroup$
– Did
Oct 15 '14 at 5:42
$begingroup$
I understand what you're saying, but I have to disagree: the efficiency of the rejection method inversely depends on the difference betweenaandb. If the formula for generating this distribution is ultra complicated then, yes, maybe it's not worth it, and only whenais a lot larger/smaller thanbthen this complicated and elusive formula will pay off. But since the formula for a circle shaped window was so straightforward, I hope that this extra step isn't that complicated.
$endgroup$
– 12.yakir
Oct 15 '14 at 8:41
$begingroup$
What do you disagree about? I see no contradiction between the factual part of your comment and mine (except that you probably mean the ratio $a/b$ instead of their difference $a-b$). Note that, if the regime of interest to you is $agg b$, this should be mentioned in the question.
$endgroup$
– Did
Oct 15 '14 at 8:46
$begingroup$
You are correct. I guess it all depends on how complicated the solution will be. I'm interested in whatever works in the best possible way. If it turns out that the analytic solution is ultra complicated then it's possible that even when the $a/b$ ratio is very large or small then it will still be slower than the rejection method. I'm hoping for something better. Better in the same way that the circle window method is better than producing uniform random points on a sphere and then rejecting the ones that are outside the circular window (this is relevant when you want $n$ points).
$endgroup$
– 12.yakir
Oct 15 '14 at 9:04
$begingroup$
Have you considered hit-and-run sampling?
$endgroup$
– Rahul
Jul 15 '18 at 4:31
|
show 1 more comment
1
$begingroup$
What you call "cheating", which is simply the reject method, is by far the computationally simplest method and probably the overall best one. To refine it, one can include the cap delimited by the ellipse in the smallest cap delimited by a circle (this amounts to replacing $a$ and $b$ by $max(a,b)$) and reject from this slightly larger cap instead of from the whole sphere.
$endgroup$
– Did
Oct 15 '14 at 5:42
$begingroup$
I understand what you're saying, but I have to disagree: the efficiency of the rejection method inversely depends on the difference betweenaandb. If the formula for generating this distribution is ultra complicated then, yes, maybe it's not worth it, and only whenais a lot larger/smaller thanbthen this complicated and elusive formula will pay off. But since the formula for a circle shaped window was so straightforward, I hope that this extra step isn't that complicated.
$endgroup$
– 12.yakir
Oct 15 '14 at 8:41
$begingroup$
What do you disagree about? I see no contradiction between the factual part of your comment and mine (except that you probably mean the ratio $a/b$ instead of their difference $a-b$). Note that, if the regime of interest to you is $agg b$, this should be mentioned in the question.
$endgroup$
– Did
Oct 15 '14 at 8:46
$begingroup$
You are correct. I guess it all depends on how complicated the solution will be. I'm interested in whatever works in the best possible way. If it turns out that the analytic solution is ultra complicated then it's possible that even when the $a/b$ ratio is very large or small then it will still be slower than the rejection method. I'm hoping for something better. Better in the same way that the circle window method is better than producing uniform random points on a sphere and then rejecting the ones that are outside the circular window (this is relevant when you want $n$ points).
$endgroup$
– 12.yakir
Oct 15 '14 at 9:04
$begingroup$
Have you considered hit-and-run sampling?
$endgroup$
– Rahul
Jul 15 '18 at 4:31
1
1
$begingroup$
What you call "cheating", which is simply the reject method, is by far the computationally simplest method and probably the overall best one. To refine it, one can include the cap delimited by the ellipse in the smallest cap delimited by a circle (this amounts to replacing $a$ and $b$ by $max(a,b)$) and reject from this slightly larger cap instead of from the whole sphere.
$endgroup$
– Did
Oct 15 '14 at 5:42
$begingroup$
What you call "cheating", which is simply the reject method, is by far the computationally simplest method and probably the overall best one. To refine it, one can include the cap delimited by the ellipse in the smallest cap delimited by a circle (this amounts to replacing $a$ and $b$ by $max(a,b)$) and reject from this slightly larger cap instead of from the whole sphere.
$endgroup$
– Did
Oct 15 '14 at 5:42
$begingroup$
I understand what you're saying, but I have to disagree: the efficiency of the rejection method inversely depends on the difference between
a and b. If the formula for generating this distribution is ultra complicated then, yes, maybe it's not worth it, and only when a is a lot larger/smaller than b then this complicated and elusive formula will pay off. But since the formula for a circle shaped window was so straightforward, I hope that this extra step isn't that complicated.$endgroup$
– 12.yakir
Oct 15 '14 at 8:41
$begingroup$
I understand what you're saying, but I have to disagree: the efficiency of the rejection method inversely depends on the difference between
a and b. If the formula for generating this distribution is ultra complicated then, yes, maybe it's not worth it, and only when a is a lot larger/smaller than b then this complicated and elusive formula will pay off. But since the formula for a circle shaped window was so straightforward, I hope that this extra step isn't that complicated.$endgroup$
– 12.yakir
Oct 15 '14 at 8:41
$begingroup$
What do you disagree about? I see no contradiction between the factual part of your comment and mine (except that you probably mean the ratio $a/b$ instead of their difference $a-b$). Note that, if the regime of interest to you is $agg b$, this should be mentioned in the question.
$endgroup$
– Did
Oct 15 '14 at 8:46
$begingroup$
What do you disagree about? I see no contradiction between the factual part of your comment and mine (except that you probably mean the ratio $a/b$ instead of their difference $a-b$). Note that, if the regime of interest to you is $agg b$, this should be mentioned in the question.
$endgroup$
– Did
Oct 15 '14 at 8:46
$begingroup$
You are correct. I guess it all depends on how complicated the solution will be. I'm interested in whatever works in the best possible way. If it turns out that the analytic solution is ultra complicated then it's possible that even when the $a/b$ ratio is very large or small then it will still be slower than the rejection method. I'm hoping for something better. Better in the same way that the circle window method is better than producing uniform random points on a sphere and then rejecting the ones that are outside the circular window (this is relevant when you want $n$ points).
$endgroup$
– 12.yakir
Oct 15 '14 at 9:04
$begingroup$
You are correct. I guess it all depends on how complicated the solution will be. I'm interested in whatever works in the best possible way. If it turns out that the analytic solution is ultra complicated then it's possible that even when the $a/b$ ratio is very large or small then it will still be slower than the rejection method. I'm hoping for something better. Better in the same way that the circle window method is better than producing uniform random points on a sphere and then rejecting the ones that are outside the circular window (this is relevant when you want $n$ points).
$endgroup$
– 12.yakir
Oct 15 '14 at 9:04
$begingroup$
Have you considered hit-and-run sampling?
$endgroup$
– Rahul
Jul 15 '18 at 4:31
$begingroup$
Have you considered hit-and-run sampling?
$endgroup$
– Rahul
Jul 15 '18 at 4:31
|
show 1 more comment
2 Answers
2
active
oldest
votes
$begingroup$
This may be way off of what you're looking for. But perhaps it might point you in the right direction. Why not use the brute force method?
First, write the equation of the circle (shadow) which will be $f(x,y,z) = 0$
Now take any random point $(x_1,y_1,z_1)$ in the plane of the circle, such that $f(x_1,y_1,z_1) leq 0$ which would mean the point $(x_1,y_1,z_1)$ lies within or on the circle.
If the center of the sphere is $(x_c,y_c,z_c)$, the desired point on sphere $(x_2,y_2,z_2)$ is the point of intersection of given sphere and the line joining $(x_1,y_1,z_1)$ and $(x_c,y_c,z_c)$
If we try to find the locus of $(x_2,y_2,z_2)$ we would get the part of the surface of sphere whose projection on the plane from the center is the circle.
If we want just some discrete points, then instead of finding the locus we simply choose $n$ random $(x_1,y_1,z_1)$ points to get required $n$ points $(x_2,y_2,z_2)$
If we want uniformly distributed such points, then we make sure that the choice of these random $(x_1,y_1,z_1)$ points themselves is uniformly distributed (within the circle)
answered Sep 20 '17 at 12:21
yathishyathish
267111
$endgroup$
$begingroup$
Thanks for your input, but please read the section titled "Why not Point-rejection?" in my question. You see, brute force has been suggested before (e.g. below), and lead me to add that section to my question in an attempt to avoid such answers. It is possible that brute force is the only true answer, but I was (is) hoping for an analytical one.
$endgroup$
– 12.yakir
Jul 24 '18 at 11:17
add a comment |
$begingroup$
You might try a point-rejection approach that rejects a relatively small percentage of the points.
As observed in comments, you can improve on sampling over the entire sphere by finding a circular cap that barely covers the elliptical window, and using the method you have already devised to sample uniformly within that cap.
This works well for elliptical windows that are nearly circular.
For elliptical windows whose "length" is much greater than their "width,"
you could refine the method in various ways, two of which I will try to describe.
Alternative Method 1
Find the line through the center of the sphere and the center of the elliptical "window,"
and construct several circles on the sphere with centers on that line.
The smallest circle could have a radius slightly larger than the smaller semi-diameter of the ellipse, and the largest circle could have a radius equal to the larger semi-diameter of the ellipse.
Between each adjacent pair of circles is a spherical zone.
If you use the line through the center of the elliptical window as the axis of a set of spherical coordinates, the zone lies between two lines of latitude.
Now divide the zone into smaller regions along lines of longitude so that two of the smaller regions cover the intersection of the elliptical window and the zone. Once you have done this for all zones, the elliptical window will be completely contained within the union of the spherical cap bounded by the smallest circle and the selected parts of all the zones.
The union of the cap and the selected parts of the zones will be your sampling region.
By changing the number of circles and their radii and the longitudes of the selected regions within each zone, you can reduce the ratio between the
area of the sampling region and the area of the elliptical window to be as close to $1$ as you want.
Now select a point uniformly distributed within the sampling region. To do this, you can take transformed Cartesian coordinates $x',y',z'$ with origin at the center of the sphere such that the $z'$ axis passes through the center of the elliptical window.
Randomly select an appropriately distributed $z'$ coordinate using the inverse cumulative distribution of $z'$ within the sampling region, which is a piecewise linear function.
Then, depending on which zone that puts the randomly generated point, you randomly select a longitude within the applicable ranges of longitude and find the $x'$ and $y'$ coordinates.
Determine whether the random point is within the elliptical window;
if not, reject it and try again.
In practice there is probably some number of zones that balances the extra effort of evaluating a piecewise function with that many pieces against the extra effort of generating random coordinates that will be rejected.
Alternative Method 2
A simpler approach is to orient the transformed coordinates
$x',y',z'$ so that the $z'$ axis is parallel to the semi-minor axis of the elliptical window. Using the $z'$ axis as the axis of a set of spherical coordinates, the elliptical window lies between two lines of latitude and two lines of longitude.
You can generate the $z'$ coordinate uniformly between its minimum and maximum values, and the $x'$ and $y'$ coordinates by generating a longitude uniformly between the two bounding longitudes.
I think this means that more than $3/4$ of the random points generated will fall within the elliptical window, so fewer than $1/4$ are rejected.
You can improve the rejection ratio even further by dividing the sampling region into strips by latitude and including just enough difference in longitude in each strip to cover the elliptical window, but this may not be worthwhile.
Conclusion
I would probably implement Alternative Method 2 (without any additional subdivision of the sampling region) unless the center of the circle in the plane was so close to the coordinates $(0,0)$ (from the figures in the question) that the rejection rate would be better for a spherical cap that contained the elliptical window, and in that case I would use the cap.
answered Nov 25 '17 at 15:40
David KDavid K
53k340115
$endgroup$
$begingroup$
Cool. But I'm really after some analytical solution (or an approximation of) rather than yet another rejection algorithm. Don't get me wrong, this is super cool, but not quite what I'm after. Thanks!!!
$endgroup$
– 12.yakir
Dec 3 '17 at 21:13
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f935763%2frandom-3d-points-uniformly-distributed-on-an-ellipse-shaped-window-of-a-sphere%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
This may be way off of what you're looking for. But perhaps it might point you in the right direction. Why not use the brute force method?
First, write the equation of the circle (shadow) which will be $f(x,y,z) = 0$
Now take any random point $(x_1,y_1,z_1)$ in the plane of the circle, such that $f(x_1,y_1,z_1) leq 0$ which would mean the point $(x_1,y_1,z_1)$ lies within or on the circle.
If the center of the sphere is $(x_c,y_c,z_c)$, the desired point on sphere $(x_2,y_2,z_2)$ is the point of intersection of given sphere and the line joining $(x_1,y_1,z_1)$ and $(x_c,y_c,z_c)$
If we try to find the locus of $(x_2,y_2,z_2)$ we would get the part of the surface of sphere whose projection on the plane from the center is the circle.
If we want just some discrete points, then instead of finding the locus we simply choose $n$ random $(x_1,y_1,z_1)$ points to get required $n$ points $(x_2,y_2,z_2)$
If we want uniformly distributed such points, then we make sure that the choice of these random $(x_1,y_1,z_1)$ points themselves is uniformly distributed (within the circle)
answered Sep 20 '17 at 12:21
yathishyathish
267111
$endgroup$
$begingroup$
Thanks for your input, but please read the section titled "Why not Point-rejection?" in my question. You see, brute force has been suggested before (e.g. below), and lead me to add that section to my question in an attempt to avoid such answers. It is possible that brute force is the only true answer, but I was (is) hoping for an analytical one.
$endgroup$
– 12.yakir
Jul 24 '18 at 11:17
add a comment |
$begingroup$
This may be way off of what you're looking for. But perhaps it might point you in the right direction. Why not use the brute force method?
First, write the equation of the circle (shadow) which will be $f(x,y,z) = 0$
Now take any random point $(x_1,y_1,z_1)$ in the plane of the circle, such that $f(x_1,y_1,z_1) leq 0$ which would mean the point $(x_1,y_1,z_1)$ lies within or on the circle.
If the center of the sphere is $(x_c,y_c,z_c)$, the desired point on sphere $(x_2,y_2,z_2)$ is the point of intersection of given sphere and the line joining $(x_1,y_1,z_1)$ and $(x_c,y_c,z_c)$
If we try to find the locus of $(x_2,y_2,z_2)$ we would get the part of the surface of sphere whose projection on the plane from the center is the circle.
If we want just some discrete points, then instead of finding the locus we simply choose $n$ random $(x_1,y_1,z_1)$ points to get required $n$ points $(x_2,y_2,z_2)$
If we want uniformly distributed such points, then we make sure that the choice of these random $(x_1,y_1,z_1)$ points themselves is uniformly distributed (within the circle)
answered Sep 20 '17 at 12:21
yathishyathish
267111
$endgroup$
$begingroup$
Thanks for your input, but please read the section titled "Why not Point-rejection?" in my question. You see, brute force has been suggested before (e.g. below), and lead me to add that section to my question in an attempt to avoid such answers. It is possible that brute force is the only true answer, but I was (is) hoping for an analytical one.
$endgroup$
– 12.yakir
Jul 24 '18 at 11:17
add a comment |
$begingroup$
This may be way off of what you're looking for. But perhaps it might point you in the right direction. Why not use the brute force method?
First, write the equation of the circle (shadow) which will be $f(x,y,z) = 0$
Now take any random point $(x_1,y_1,z_1)$ in the plane of the circle, such that $f(x_1,y_1,z_1) leq 0$ which would mean the point $(x_1,y_1,z_1)$ lies within or on the circle.
If the center of the sphere is $(x_c,y_c,z_c)$, the desired point on sphere $(x_2,y_2,z_2)$ is the point of intersection of given sphere and the line joining $(x_1,y_1,z_1)$ and $(x_c,y_c,z_c)$
If we try to find the locus of $(x_2,y_2,z_2)$ we would get the part of the surface of sphere whose projection on the plane from the center is the circle.
If we want just some discrete points, then instead of finding the locus we simply choose $n$ random $(x_1,y_1,z_1)$ points to get required $n$ points $(x_2,y_2,z_2)$
If we want uniformly distributed such points, then we make sure that the choice of these random $(x_1,y_1,z_1)$ points themselves is uniformly distributed (within the circle)
answered Sep 20 '17 at 12:21
yathishyathish
267111
$endgroup$
This may be way off of what you're looking for. But perhaps it might point you in the right direction. Why not use the brute force method?
First, write the equation of the circle (shadow) which will be $f(x,y,z) = 0$
Now take any random point $(x_1,y_1,z_1)$ in the plane of the circle, such that $f(x_1,y_1,z_1) leq 0$ which would mean the point $(x_1,y_1,z_1)$ lies within or on the circle.
If the center of the sphere is $(x_c,y_c,z_c)$, the desired point on sphere $(x_2,y_2,z_2)$ is the point of intersection of given sphere and the line joining $(x_1,y_1,z_1)$ and $(x_c,y_c,z_c)$
If we try to find the locus of $(x_2,y_2,z_2)$ we would get the part of the surface of sphere whose projection on the plane from the center is the circle.
If we want just some discrete points, then instead of finding the locus we simply choose $n$ random $(x_1,y_1,z_1)$ points to get required $n$ points $(x_2,y_2,z_2)$
If we want uniformly distributed such points, then we make sure that the choice of these random $(x_1,y_1,z_1)$ points themselves is uniformly distributed (within the circle)
answered Sep 20 '17 at 12:21
yathishyathish
267111
answered Sep 20 '17 at 12:21
yathishyathish
267111
answered Sep 20 '17 at 12:21
yathishyathish
267111
answered Sep 20 '17 at 12:21
yathishyathish
267111
267111
$begingroup$
Thanks for your input, but please read the section titled "Why not Point-rejection?" in my question. You see, brute force has been suggested before (e.g. below), and lead me to add that section to my question in an attempt to avoid such answers. It is possible that brute force is the only true answer, but I was (is) hoping for an analytical one.
$endgroup$
– 12.yakir
Jul 24 '18 at 11:17
add a comment |
$begingroup$
Thanks for your input, but please read the section titled "Why not Point-rejection?" in my question. You see, brute force has been suggested before (e.g. below), and lead me to add that section to my question in an attempt to avoid such answers. It is possible that brute force is the only true answer, but I was (is) hoping for an analytical one.
$endgroup$
– 12.yakir
Jul 24 '18 at 11:17
$begingroup$
Thanks for your input, but please read the section titled "Why not Point-rejection?" in my question. You see, brute force has been suggested before (e.g. below), and lead me to add that section to my question in an attempt to avoid such answers. It is possible that brute force is the only true answer, but I was (is) hoping for an analytical one.
$endgroup$
– 12.yakir
Jul 24 '18 at 11:17
$begingroup$
Thanks for your input, but please read the section titled "Why not Point-rejection?" in my question. You see, brute force has been suggested before (e.g. below), and lead me to add that section to my question in an attempt to avoid such answers. It is possible that brute force is the only true answer, but I was (is) hoping for an analytical one.
$endgroup$
– 12.yakir
Jul 24 '18 at 11:17
add a comment |
$begingroup$
You might try a point-rejection approach that rejects a relatively small percentage of the points.
As observed in comments, you can improve on sampling over the entire sphere by finding a circular cap that barely covers the elliptical window, and using the method you have already devised to sample uniformly within that cap.
This works well for elliptical windows that are nearly circular.
For elliptical windows whose "length" is much greater than their "width,"
you could refine the method in various ways, two of which I will try to describe.
Alternative Method 1
Find the line through the center of the sphere and the center of the elliptical "window,"
and construct several circles on the sphere with centers on that line.
The smallest circle could have a radius slightly larger than the smaller semi-diameter of the ellipse, and the largest circle could have a radius equal to the larger semi-diameter of the ellipse.
Between each adjacent pair of circles is a spherical zone.
If you use the line through the center of the elliptical window as the axis of a set of spherical coordinates, the zone lies between two lines of latitude.
Now divide the zone into smaller regions along lines of longitude so that two of the smaller regions cover the intersection of the elliptical window and the zone. Once you have done this for all zones, the elliptical window will be completely contained within the union of the spherical cap bounded by the smallest circle and the selected parts of all the zones.
The union of the cap and the selected parts of the zones will be your sampling region.
By changing the number of circles and their radii and the longitudes of the selected regions within each zone, you can reduce the ratio between the
area of the sampling region and the area of the elliptical window to be as close to $1$ as you want.
Now select a point uniformly distributed within the sampling region. To do this, you can take transformed Cartesian coordinates $x',y',z'$ with origin at the center of the sphere such that the $z'$ axis passes through the center of the elliptical window.
Randomly select an appropriately distributed $z'$ coordinate using the inverse cumulative distribution of $z'$ within the sampling region, which is a piecewise linear function.
Then, depending on which zone that puts the randomly generated point, you randomly select a longitude within the applicable ranges of longitude and find the $x'$ and $y'$ coordinates.
Determine whether the random point is within the elliptical window;
if not, reject it and try again.
In practice there is probably some number of zones that balances the extra effort of evaluating a piecewise function with that many pieces against the extra effort of generating random coordinates that will be rejected.
Alternative Method 2
A simpler approach is to orient the transformed coordinates
$x',y',z'$ so that the $z'$ axis is parallel to the semi-minor axis of the elliptical window. Using the $z'$ axis as the axis of a set of spherical coordinates, the elliptical window lies between two lines of latitude and two lines of longitude.
You can generate the $z'$ coordinate uniformly between its minimum and maximum values, and the $x'$ and $y'$ coordinates by generating a longitude uniformly between the two bounding longitudes.
I think this means that more than $3/4$ of the random points generated will fall within the elliptical window, so fewer than $1/4$ are rejected.
You can improve the rejection ratio even further by dividing the sampling region into strips by latitude and including just enough difference in longitude in each strip to cover the elliptical window, but this may not be worthwhile.
Conclusion
I would probably implement Alternative Method 2 (without any additional subdivision of the sampling region) unless the center of the circle in the plane was so close to the coordinates $(0,0)$ (from the figures in the question) that the rejection rate would be better for a spherical cap that contained the elliptical window, and in that case I would use the cap.
answered Nov 25 '17 at 15:40
David KDavid K
53k340115
$endgroup$
$begingroup$
Cool. But I'm really after some analytical solution (or an approximation of) rather than yet another rejection algorithm. Don't get me wrong, this is super cool, but not quite what I'm after. Thanks!!!
$endgroup$
– 12.yakir
Dec 3 '17 at 21:13
add a comment |
$begingroup$
You might try a point-rejection approach that rejects a relatively small percentage of the points.
As observed in comments, you can improve on sampling over the entire sphere by finding a circular cap that barely covers the elliptical window, and using the method you have already devised to sample uniformly within that cap.
This works well for elliptical windows that are nearly circular.
For elliptical windows whose "length" is much greater than their "width,"
you could refine the method in various ways, two of which I will try to describe.
Alternative Method 1
Find the line through the center of the sphere and the center of the elliptical "window,"
and construct several circles on the sphere with centers on that line.
The smallest circle could have a radius slightly larger than the smaller semi-diameter of the ellipse, and the largest circle could have a radius equal to the larger semi-diameter of the ellipse.
Between each adjacent pair of circles is a spherical zone.
If you use the line through the center of the elliptical window as the axis of a set of spherical coordinates, the zone lies between two lines of latitude.
Now divide the zone into smaller regions along lines of longitude so that two of the smaller regions cover the intersection of the elliptical window and the zone. Once you have done this for all zones, the elliptical window will be completely contained within the union of the spherical cap bounded by the smallest circle and the selected parts of all the zones.
The union of the cap and the selected parts of the zones will be your sampling region.
By changing the number of circles and their radii and the longitudes of the selected regions within each zone, you can reduce the ratio between the
area of the sampling region and the area of the elliptical window to be as close to $1$ as you want.
Now select a point uniformly distributed within the sampling region. To do this, you can take transformed Cartesian coordinates $x',y',z'$ with origin at the center of the sphere such that the $z'$ axis passes through the center of the elliptical window.
Randomly select an appropriately distributed $z'$ coordinate using the inverse cumulative distribution of $z'$ within the sampling region, which is a piecewise linear function.
Then, depending on which zone that puts the randomly generated point, you randomly select a longitude within the applicable ranges of longitude and find the $x'$ and $y'$ coordinates.
Determine whether the random point is within the elliptical window;
if not, reject it and try again.
In practice there is probably some number of zones that balances the extra effort of evaluating a piecewise function with that many pieces against the extra effort of generating random coordinates that will be rejected.
Alternative Method 2
A simpler approach is to orient the transformed coordinates
$x',y',z'$ so that the $z'$ axis is parallel to the semi-minor axis of the elliptical window. Using the $z'$ axis as the axis of a set of spherical coordinates, the elliptical window lies between two lines of latitude and two lines of longitude.
You can generate the $z'$ coordinate uniformly between its minimum and maximum values, and the $x'$ and $y'$ coordinates by generating a longitude uniformly between the two bounding longitudes.
I think this means that more than $3/4$ of the random points generated will fall within the elliptical window, so fewer than $1/4$ are rejected.
You can improve the rejection ratio even further by dividing the sampling region into strips by latitude and including just enough difference in longitude in each strip to cover the elliptical window, but this may not be worthwhile.
Conclusion
I would probably implement Alternative Method 2 (without any additional subdivision of the sampling region) unless the center of the circle in the plane was so close to the coordinates $(0,0)$ (from the figures in the question) that the rejection rate would be better for a spherical cap that contained the elliptical window, and in that case I would use the cap.
answered Nov 25 '17 at 15:40
David KDavid K
53k340115
$endgroup$
$begingroup$
Cool. But I'm really after some analytical solution (or an approximation of) rather than yet another rejection algorithm. Don't get me wrong, this is super cool, but not quite what I'm after. Thanks!!!
$endgroup$
– 12.yakir
Dec 3 '17 at 21:13
add a comment |
$begingroup$
You might try a point-rejection approach that rejects a relatively small percentage of the points.
As observed in comments, you can improve on sampling over the entire sphere by finding a circular cap that barely covers the elliptical window, and using the method you have already devised to sample uniformly within that cap.
This works well for elliptical windows that are nearly circular.
For elliptical windows whose "length" is much greater than their "width,"
you could refine the method in various ways, two of which I will try to describe.
Alternative Method 1
Find the line through the center of the sphere and the center of the elliptical "window,"
and construct several circles on the sphere with centers on that line.
The smallest circle could have a radius slightly larger than the smaller semi-diameter of the ellipse, and the largest circle could have a radius equal to the larger semi-diameter of the ellipse.
Between each adjacent pair of circles is a spherical zone.
If you use the line through the center of the elliptical window as the axis of a set of spherical coordinates, the zone lies between two lines of latitude.
Now divide the zone into smaller regions along lines of longitude so that two of the smaller regions cover the intersection of the elliptical window and the zone. Once you have done this for all zones, the elliptical window will be completely contained within the union of the spherical cap bounded by the smallest circle and the selected parts of all the zones.
The union of the cap and the selected parts of the zones will be your sampling region.
By changing the number of circles and their radii and the longitudes of the selected regions within each zone, you can reduce the ratio between the
area of the sampling region and the area of the elliptical window to be as close to $1$ as you want.
Now select a point uniformly distributed within the sampling region. To do this, you can take transformed Cartesian coordinates $x',y',z'$ with origin at the center of the sphere such that the $z'$ axis passes through the center of the elliptical window.
Randomly select an appropriately distributed $z'$ coordinate using the inverse cumulative distribution of $z'$ within the sampling region, which is a piecewise linear function.
Then, depending on which zone that puts the randomly generated point, you randomly select a longitude within the applicable ranges of longitude and find the $x'$ and $y'$ coordinates.
Determine whether the random point is within the elliptical window;
if not, reject it and try again.
In practice there is probably some number of zones that balances the extra effort of evaluating a piecewise function with that many pieces against the extra effort of generating random coordinates that will be rejected.
Alternative Method 2
A simpler approach is to orient the transformed coordinates
$x',y',z'$ so that the $z'$ axis is parallel to the semi-minor axis of the elliptical window. Using the $z'$ axis as the axis of a set of spherical coordinates, the elliptical window lies between two lines of latitude and two lines of longitude.
You can generate the $z'$ coordinate uniformly between its minimum and maximum values, and the $x'$ and $y'$ coordinates by generating a longitude uniformly between the two bounding longitudes.
I think this means that more than $3/4$ of the random points generated will fall within the elliptical window, so fewer than $1/4$ are rejected.
You can improve the rejection ratio even further by dividing the sampling region into strips by latitude and including just enough difference in longitude in each strip to cover the elliptical window, but this may not be worthwhile.
Conclusion
I would probably implement Alternative Method 2 (without any additional subdivision of the sampling region) unless the center of the circle in the plane was so close to the coordinates $(0,0)$ (from the figures in the question) that the rejection rate would be better for a spherical cap that contained the elliptical window, and in that case I would use the cap.
answered Nov 25 '17 at 15:40
David KDavid K
53k340115
$endgroup$
You might try a point-rejection approach that rejects a relatively small percentage of the points.
As observed in comments, you can improve on sampling over the entire sphere by finding a circular cap that barely covers the elliptical window, and using the method you have already devised to sample uniformly within that cap.
This works well for elliptical windows that are nearly circular.
For elliptical windows whose "length" is much greater than their "width,"
you could refine the method in various ways, two of which I will try to describe.
Alternative Method 1
Find the line through the center of the sphere and the center of the elliptical "window,"
and construct several circles on the sphere with centers on that line.
The smallest circle could have a radius slightly larger than the smaller semi-diameter of the ellipse, and the largest circle could have a radius equal to the larger semi-diameter of the ellipse.
Between each adjacent pair of circles is a spherical zone.
If you use the line through the center of the elliptical window as the axis of a set of spherical coordinates, the zone lies between two lines of latitude.
Now divide the zone into smaller regions along lines of longitude so that two of the smaller regions cover the intersection of the elliptical window and the zone. Once you have done this for all zones, the elliptical window will be completely contained within the union of the spherical cap bounded by the smallest circle and the selected parts of all the zones.
The union of the cap and the selected parts of the zones will be your sampling region.
By changing the number of circles and their radii and the longitudes of the selected regions within each zone, you can reduce the ratio between the
area of the sampling region and the area of the elliptical window to be as close to $1$ as you want.
Now select a point uniformly distributed within the sampling region. To do this, you can take transformed Cartesian coordinates $x',y',z'$ with origin at the center of the sphere such that the $z'$ axis passes through the center of the elliptical window.
Randomly select an appropriately distributed $z'$ coordinate using the inverse cumulative distribution of $z'$ within the sampling region, which is a piecewise linear function.
Then, depending on which zone that puts the randomly generated point, you randomly select a longitude within the applicable ranges of longitude and find the $x'$ and $y'$ coordinates.
Determine whether the random point is within the elliptical window;
if not, reject it and try again.
In practice there is probably some number of zones that balances the extra effort of evaluating a piecewise function with that many pieces against the extra effort of generating random coordinates that will be rejected.
Alternative Method 2
A simpler approach is to orient the transformed coordinates
$x',y',z'$ so that the $z'$ axis is parallel to the semi-minor axis of the elliptical window. Using the $z'$ axis as the axis of a set of spherical coordinates, the elliptical window lies between two lines of latitude and two lines of longitude.
You can generate the $z'$ coordinate uniformly between its minimum and maximum values, and the $x'$ and $y'$ coordinates by generating a longitude uniformly between the two bounding longitudes.
I think this means that more than $3/4$ of the random points generated will fall within the elliptical window, so fewer than $1/4$ are rejected.
You can improve the rejection ratio even further by dividing the sampling region into strips by latitude and including just enough difference in longitude in each strip to cover the elliptical window, but this may not be worthwhile.
Conclusion
I would probably implement Alternative Method 2 (without any additional subdivision of the sampling region) unless the center of the circle in the plane was so close to the coordinates $(0,0)$ (from the figures in the question) that the rejection rate would be better for a spherical cap that contained the elliptical window, and in that case I would use the cap.
answered Nov 25 '17 at 15:40
David KDavid K
53k340115
answered Nov 25 '17 at 15:40
David KDavid K
53k340115
answered Nov 25 '17 at 15:40
David KDavid K
53k340115
answered Nov 25 '17 at 15:40
David KDavid K
53k340115
53k340115
$begingroup$
Cool. But I'm really after some analytical solution (or an approximation of) rather than yet another rejection algorithm. Don't get me wrong, this is super cool, but not quite what I'm after. Thanks!!!
$endgroup$
– 12.yakir
Dec 3 '17 at 21:13
add a comment |
$begingroup$
Cool. But I'm really after some analytical solution (or an approximation of) rather than yet another rejection algorithm. Don't get me wrong, this is super cool, but not quite what I'm after. Thanks!!!
$endgroup$
– 12.yakir
Dec 3 '17 at 21:13
$begingroup$
Cool. But I'm really after some analytical solution (or an approximation of) rather than yet another rejection algorithm. Don't get me wrong, this is super cool, but not quite what I'm after. Thanks!!!
$endgroup$
– 12.yakir
Dec 3 '17 at 21:13
$begingroup$
Cool. But I'm really after some analytical solution (or an approximation of) rather than yet another rejection algorithm. Don't get me wrong, this is super cool, but not quite what I'm after. Thanks!!!
$endgroup$
– 12.yakir
Dec 3 '17 at 21:13
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f935763%2frandom-3d-points-uniformly-distributed-on-an-ellipse-shaped-window-of-a-sphere%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
What you call "cheating", which is simply the reject method, is by far the computationally simplest method and probably the overall best one. To refine it, one can include the cap delimited by the ellipse in the smallest cap delimited by a circle (this amounts to replacing $a$ and $b$ by $max(a,b)$) and reject from this slightly larger cap instead of from the whole sphere.
$endgroup$
– Did
Oct 15 '14 at 5:42
$begingroup$
I understand what you're saying, but I have to disagree: the efficiency of the rejection method inversely depends on the difference between
aandb. If the formula for generating this distribution is ultra complicated then, yes, maybe it's not worth it, and only whenais a lot larger/smaller thanbthen this complicated and elusive formula will pay off. But since the formula for a circle shaped window was so straightforward, I hope that this extra step isn't that complicated.$endgroup$
– 12.yakir
Oct 15 '14 at 8:41
$begingroup$
What do you disagree about? I see no contradiction between the factual part of your comment and mine (except that you probably mean the ratio $a/b$ instead of their difference $a-b$). Note that, if the regime of interest to you is $agg b$, this should be mentioned in the question.
$endgroup$
– Did
Oct 15 '14 at 8:46
$begingroup$
You are correct. I guess it all depends on how complicated the solution will be. I'm interested in whatever works in the best possible way. If it turns out that the analytic solution is ultra complicated then it's possible that even when the $a/b$ ratio is very large or small then it will still be slower than the rejection method. I'm hoping for something better. Better in the same way that the circle window method is better than producing uniform random points on a sphere and then rejecting the ones that are outside the circular window (this is relevant when you want $n$ points).
$endgroup$
– 12.yakir
Oct 15 '14 at 9:04
$begingroup$
Have you considered hit-and-run sampling?
$endgroup$
– Rahul
Jul 15 '18 at 4:31