You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Alex Herbert <al...@gmail.com> on 2021/04/23 21:41:57 UTC
[RNG][Geometry] TriangleSampler and other shape samplers
I recently added a UnitBallSampler to the sampling module to sample
coordinates inside a unit ball. I also have a working TriangleSampler to
sample within a triangle and intend to create a TetrahedronSampler to
sample within a tetrahedron.
Currently in the released version (1.3) we only have a UnitSphereSampler in:
o.a.c.rng.sampling
The only other package is o.a.c.rng.sampling.distribution for probability
distributions.
Should new coordinate based samplers be moved to a package inside for
example:
o.a.c.rng.sampling.geometry
o.a.c.rng.sampling.shape
These shape samplers also require a valid input for the geometry. Currently
in my working example for the TriangleSampler I have not validated the
input is a triangle. I state that if the points are collinear then the
distribution of the samples is undefined. It will not be uniform on the
line segment connecting the vertices.
I think that validation of the input shape is out of scope. Are shape
samplers themselves also out of scope for RNG and would be a better fit in
commons Geometry?
Re: [RNG][Geometry] TriangleSampler and other shape samplers
Posted by Gilles Sadowski <gi...@gmail.com>.
Le sam. 24 avr. 2021 à 23:32, Alex Herbert <al...@gmail.com> a écrit :
>
> On Sat, 24 Apr 2021 at 17:36, Matt Juntunen <ma...@hotmail.com>
> wrote:
>
> > This is very interesting. With this amount of geometry code, I could
> > picture this as part of a commons-geometry-rng module. The SurfaceSampler,
> > for example, could make use of the TriangleMesh and Triangle3D classes.
> > This would also be an opportunity to expand support for N-dimensional
> > points and vectors.
> >
>
> commons-geometry-sampling?
+1 for a new module.
>
> I like the idea of providing geometry and as a framework for validating the
> shapes that are input.
A new module would indeed make it possible to have it depend on
(some part of) [Geometry], while not imposing those dependencies
on users of the low(er)-level sampling utilities.
> Anyway I suggest to move the UnitBallSampler to a o.a.c.rng.sampling.shape
> package and to start adding items there. When the samplers are done then
> the package can be reviewed and the options with regard to geometry can
> be discussed, e.g. a geometry module using it, or the functionality being
> moved to geometry.
I don't think we'd ever regret having an additional module.
Regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [RNG][Geometry] TriangleSampler and other shape samplers
Posted by Alex Herbert <al...@gmail.com>.
On Sat, 24 Apr 2021 at 17:36, Matt Juntunen <ma...@hotmail.com>
wrote:
> This is very interesting. With this amount of geometry code, I could
> picture this as part of a commons-geometry-rng module. The SurfaceSampler,
> for example, could make use of the TriangleMesh and Triangle3D classes.
> This would also be an opportunity to expand support for N-dimensional
> points and vectors.
>
commons-geometry-sampling?
I like the idea of providing geometry and as a framework for validating the
shapes that are input.
Anyway I suggest to move the UnitBallSampler to a o.a.c.rng.sampling.shape
package and to start adding items there. When the samplers are done then
the package can be reviewed and the options with regard to geometry can
be discussed, e.g. a geometry module using it, or the functionality being
moved to geometry.
Alex
Re: [RNG][Geometry] TriangleSampler and other shape samplers
Posted by Matt Juntunen <ma...@hotmail.com>.
This is very interesting. With this amount of geometry code, I could picture this as part of a commons-geometry-rng module. The SurfaceSampler, for example, could make use of the TriangleMesh and Triangle3D classes. This would also be an opportunity to expand support for N-dimensional points and vectors.
-Matt
________________________________
From: Alex Herbert <al...@gmail.com>
Sent: Saturday, April 24, 2021 9:48 AM
To: Commons Developers List <de...@commons.apache.org>
Subject: Re: [RNG][Geometry] TriangleSampler and other shape samplers
On Fri, 23 Apr 2021 at 23:31, Gilles Sadowski <gi...@gmail.com> wrote:
> Le ven. 23 avr. 2021 à 23:42, Alex Herbert <al...@gmail.com> a
> écrit :
>
> > Should new coordinate based samplers be moved to a package inside for
> > example:
> >
> > o.a.c.rng.sampling.geometry
> > o.a.c.rng.sampling.shape
>
> Maybe. I guess that "UnitSphereSampler" would be moved too (and thus
> deprecated in the package where it currently resides).
>
> Do you foresee many "shapes"?
> And a way to "combine" them?
>
I required a unit disc for use in testing a convex hull algorithm. This
created the UnitBallSampler. When looking at options I found the Wolfram
page 'Random Point Picking' has a lot of sampling examples and expected
results of sampling [1]. I thought that primitive shapes would be useful
for someone. So at least:
- TriangleSampler (ND)
- LineSampler (ND)
- TetrahedronSampler (3D only)
There is also a UnitSimplexSampler which samples from the surface of an ND
simplex: x1 + x2 + ... + xn = 1; 0 <= xi <= 1. This can be done by sampling
from an exponential distribution and normalising so would be possible with
the current library. I thought about a UnitCubeSampler which although
trivial may be useful.
For sampling a surface the TriangleSampler can be combined with the
AliasMethodSamplerDiscreteSampler. The surface should be triangulated. The
area of each triangle is used to create a distribution of which triangle to
pick using the alias method. A sample is then taken from the chosen
triangle. This would require a robust method to compute the area of a
triangle even when containing very acute or obtuse angles. Input could be
vertices and face indices:
public static SurfaceSampler of(double[] vertices, int[][] faces,
UniformRandomProvider);
The AliasMethodSamplerDiscreteSampler handles up to 2^31-1 discrete items
so should work even with very large surfaces (with a lot of memory).
A similar approach can be done with a volume using the TetrahedronSampler
but would be restricted to 3D. Thus far I have not found a method to sample
from an ND volume other than the UnitBall or UnitCube.
The UnitSphereSampler can be deprecated and a new version created to use a
factory method to create the sampler (allowing optimisation for low
dimensions). This would have:
o.a.c.rng.sampling.shape
UnitSphereSampler (N-surface)
UnitBallSampler (N-volume)
UnitSimplexSampler (N-surface)
LineSegmentSampler (N-dimension points on a line segment between 2 points)
TriangleSampler (N-dimension points within a triangle in a 2D plane)
TetrahedronSampler (3D points inside a tetrahedron)
SurfaceSampler (ND points on a triangulated surface)
VolumeSampler (3D points inside a volume composed of tetrahedrons)
? UnitCubeSampler (N-volume)
On Sat, 24 Apr 2021 at 12:27, Matt Juntunen <ma...@hotmail.com>
wrote:
> One more question: what are the originating use cases for these shape
> samplers?
>
I use them for testing programs that deal with 2/3D points that are part of
a shape. For example I've a program that performs 3 channel unmixing on
photoactivated flourophores. To test this it is useful to draw random
structures of points in each channel that are different such as lines,
circles and triangles. If the unmixing works then the same shaped
structures are all the same colour when viewed as an RBG image. Another
example is drawing 2D/3D points for testing convex and concave hull
algorithms. It is easy to draw some primitive shapes and test if the hull
produces an area/volume as expected.
[1] https://mathworld.wolfram.com/topics/RandomPointPicking.html
Re: [RNG][Geometry] TriangleSampler and other shape samplers
Posted by Alex Herbert <al...@gmail.com>.
On Fri, 23 Apr 2021 at 23:31, Gilles Sadowski <gi...@gmail.com> wrote:
> Le ven. 23 avr. 2021 à 23:42, Alex Herbert <al...@gmail.com> a
> écrit :
>
> > Should new coordinate based samplers be moved to a package inside for
> > example:
> >
> > o.a.c.rng.sampling.geometry
> > o.a.c.rng.sampling.shape
>
> Maybe. I guess that "UnitSphereSampler" would be moved too (and thus
> deprecated in the package where it currently resides).
>
> Do you foresee many "shapes"?
> And a way to "combine" them?
>
I required a unit disc for use in testing a convex hull algorithm. This
created the UnitBallSampler. When looking at options I found the Wolfram
page 'Random Point Picking' has a lot of sampling examples and expected
results of sampling [1]. I thought that primitive shapes would be useful
for someone. So at least:
- TriangleSampler (ND)
- LineSampler (ND)
- TetrahedronSampler (3D only)
There is also a UnitSimplexSampler which samples from the surface of an ND
simplex: x1 + x2 + ... + xn = 1; 0 <= xi <= 1. This can be done by sampling
from an exponential distribution and normalising so would be possible with
the current library. I thought about a UnitCubeSampler which although
trivial may be useful.
For sampling a surface the TriangleSampler can be combined with the
AliasMethodSamplerDiscreteSampler. The surface should be triangulated. The
area of each triangle is used to create a distribution of which triangle to
pick using the alias method. A sample is then taken from the chosen
triangle. This would require a robust method to compute the area of a
triangle even when containing very acute or obtuse angles. Input could be
vertices and face indices:
public static SurfaceSampler of(double[] vertices, int[][] faces,
UniformRandomProvider);
The AliasMethodSamplerDiscreteSampler handles up to 2^31-1 discrete items
so should work even with very large surfaces (with a lot of memory).
A similar approach can be done with a volume using the TetrahedronSampler
but would be restricted to 3D. Thus far I have not found a method to sample
from an ND volume other than the UnitBall or UnitCube.
The UnitSphereSampler can be deprecated and a new version created to use a
factory method to create the sampler (allowing optimisation for low
dimensions). This would have:
o.a.c.rng.sampling.shape
UnitSphereSampler (N-surface)
UnitBallSampler (N-volume)
UnitSimplexSampler (N-surface)
LineSegmentSampler (N-dimension points on a line segment between 2 points)
TriangleSampler (N-dimension points within a triangle in a 2D plane)
TetrahedronSampler (3D points inside a tetrahedron)
SurfaceSampler (ND points on a triangulated surface)
VolumeSampler (3D points inside a volume composed of tetrahedrons)
? UnitCubeSampler (N-volume)
On Sat, 24 Apr 2021 at 12:27, Matt Juntunen <ma...@hotmail.com>
wrote:
> One more question: what are the originating use cases for these shape
> samplers?
>
I use them for testing programs that deal with 2/3D points that are part of
a shape. For example I've a program that performs 3 channel unmixing on
photoactivated flourophores. To test this it is useful to draw random
structures of points in each channel that are different such as lines,
circles and triangles. If the unmixing works then the same shaped
structures are all the same colour when viewed as an RBG image. Another
example is drawing 2D/3D points for testing convex and concave hull
algorithms. It is easy to draw some primitive shapes and test if the hull
produces an area/volume as expected.
[1] https://mathworld.wolfram.com/topics/RandomPointPicking.html
Re: [RNG][Geometry] TriangleSampler and other shape samplers
Posted by Matt Juntunen <ma...@hotmail.com>.
One more question: what are the originating use cases for these shape samplers?
-Matt J
________________________________
From: Matt Juntunen <ma...@hotmail.com>
Sent: Saturday, April 24, 2021 7:25 AM
To: Commons Developers List <de...@commons.apache.org>
Subject: Re: [RNG][Geometry] TriangleSampler and other shape samplers
Hello,
> Currently in my working example for the TriangleSampler I have not validated the
> input is a triangle. I state that if the points are collinear then the distribution of the samples is undefined.
That seems fine to me for the triangle case. If you attempted to validate the shape, you'd probably want
to use some sort of epsilon or type like Precision.DoubleEquivalence [1] to ensure that floating point errors
don't interfere with the validation. That seems overly complicated to me for this use case, though.
> I think that validation of the input shape is out of scope. Are shape
> samplers themselves also out of scope for RNG and would be a better fit in
> commons Geometry?
I agree with Gilles that it seems more out of scope to put RNG in geometry than vice versa.
Perhaps RNG could document that the input shapes are not validated or are only validated to
the minimum extent necessary to generate samples. Callers could then use geometry separately
to generate the correct shapes to supply to RNG.
Regards,
Matt J
[1] I'm starting to get used to the name, Gilles 🙂
________________________________
From: Gilles Sadowski <gi...@gmail.com>
Sent: Friday, April 23, 2021 6:31 PM
To: Commons Developers List <de...@commons.apache.org>
Subject: Re: [RNG][Geometry] TriangleSampler and other shape samplers
Le ven. 23 avr. 2021 à 23:42, Alex Herbert <al...@gmail.com> a écrit :
>
> I recently added a UnitBallSampler to the sampling module to sample
> coordinates inside a unit ball. I also have a working TriangleSampler to
> sample within a triangle and intend to create a TetrahedronSampler to
> sample within a tetrahedron.
>
> Currently in the released version (1.3) we only have a UnitSphereSampler in:
>
> o.a.c.rng.sampling
>
> The only other package is o.a.c.rng.sampling.distribution for probability
> distributions.
>
> Should new coordinate based samplers be moved to a package inside for
> example:
>
> o.a.c.rng.sampling.geometry
> o.a.c.rng.sampling.shape
Maybe. I guess that "UnitSphereSampler" would be moved too (and thus
deprecated in the package where it currently resides).
Do you foresee many "shapes"?
And a way to "combine" them?
> These shape samplers also require a valid input for the geometry. Currently
> in my working example for the TriangleSampler I have not validated the
> input is a triangle. I state that if the points are collinear then the
> distribution of the samples is undefined. It will not be uniform on the
> line segment connecting the vertices.
>
> I think that validation of the input shape is out of scope.
I'd tend to agree; otherwise, it would duplicate code that would certainly
also be needed in [Geometry].
> Are shape
> samplers themselves also out of scope for RNG and would be a better fit in
> commons Geometry?
At first sight, sampling codes would seem more out of scope in [Geometry]
than "shape" sampling in [RNG].
Regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [RNG][Geometry] TriangleSampler and other shape samplers
Posted by Matt Juntunen <ma...@hotmail.com>.
Hello,
> Currently in my working example for the TriangleSampler I have not validated the
> input is a triangle. I state that if the points are collinear then the distribution of the samples is undefined.
That seems fine to me for the triangle case. If you attempted to validate the shape, you'd probably want
to use some sort of epsilon or type like Precision.DoubleEquivalence [1] to ensure that floating point errors
don't interfere with the validation. That seems overly complicated to me for this use case, though.
> I think that validation of the input shape is out of scope. Are shape
> samplers themselves also out of scope for RNG and would be a better fit in
> commons Geometry?
I agree with Gilles that it seems more out of scope to put RNG in geometry than vice versa.
Perhaps RNG could document that the input shapes are not validated or are only validated to
the minimum extent necessary to generate samples. Callers could then use geometry separately
to generate the correct shapes to supply to RNG.
Regards,
Matt J
[1] I'm starting to get used to the name, Gilles 🙂
________________________________
From: Gilles Sadowski <gi...@gmail.com>
Sent: Friday, April 23, 2021 6:31 PM
To: Commons Developers List <de...@commons.apache.org>
Subject: Re: [RNG][Geometry] TriangleSampler and other shape samplers
Le ven. 23 avr. 2021 à 23:42, Alex Herbert <al...@gmail.com> a écrit :
>
> I recently added a UnitBallSampler to the sampling module to sample
> coordinates inside a unit ball. I also have a working TriangleSampler to
> sample within a triangle and intend to create a TetrahedronSampler to
> sample within a tetrahedron.
>
> Currently in the released version (1.3) we only have a UnitSphereSampler in:
>
> o.a.c.rng.sampling
>
> The only other package is o.a.c.rng.sampling.distribution for probability
> distributions.
>
> Should new coordinate based samplers be moved to a package inside for
> example:
>
> o.a.c.rng.sampling.geometry
> o.a.c.rng.sampling.shape
Maybe. I guess that "UnitSphereSampler" would be moved too (and thus
deprecated in the package where it currently resides).
Do you foresee many "shapes"?
And a way to "combine" them?
> These shape samplers also require a valid input for the geometry. Currently
> in my working example for the TriangleSampler I have not validated the
> input is a triangle. I state that if the points are collinear then the
> distribution of the samples is undefined. It will not be uniform on the
> line segment connecting the vertices.
>
> I think that validation of the input shape is out of scope.
I'd tend to agree; otherwise, it would duplicate code that would certainly
also be needed in [Geometry].
> Are shape
> samplers themselves also out of scope for RNG and would be a better fit in
> commons Geometry?
At first sight, sampling codes would seem more out of scope in [Geometry]
than "shape" sampling in [RNG].
Regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [RNG][Geometry] TriangleSampler and other shape samplers
Posted by Gilles Sadowski <gi...@gmail.com>.
Le ven. 23 avr. 2021 à 23:42, Alex Herbert <al...@gmail.com> a écrit :
>
> I recently added a UnitBallSampler to the sampling module to sample
> coordinates inside a unit ball. I also have a working TriangleSampler to
> sample within a triangle and intend to create a TetrahedronSampler to
> sample within a tetrahedron.
>
> Currently in the released version (1.3) we only have a UnitSphereSampler in:
>
> o.a.c.rng.sampling
>
> The only other package is o.a.c.rng.sampling.distribution for probability
> distributions.
>
> Should new coordinate based samplers be moved to a package inside for
> example:
>
> o.a.c.rng.sampling.geometry
> o.a.c.rng.sampling.shape
Maybe. I guess that "UnitSphereSampler" would be moved too (and thus
deprecated in the package where it currently resides).
Do you foresee many "shapes"?
And a way to "combine" them?
> These shape samplers also require a valid input for the geometry. Currently
> in my working example for the TriangleSampler I have not validated the
> input is a triangle. I state that if the points are collinear then the
> distribution of the samples is undefined. It will not be uniform on the
> line segment connecting the vertices.
>
> I think that validation of the input shape is out of scope.
I'd tend to agree; otherwise, it would duplicate code that would certainly
also be needed in [Geometry].
> Are shape
> samplers themselves also out of scope for RNG and would be a better fit in
> commons Geometry?
At first sight, sampling codes would seem more out of scope in [Geometry]
than "shape" sampling in [RNG].
Regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org