Find a point inside (x,y,z) -> Bool
Hello all, I hope this is not a too silly question. It goes like this: Suppose I have a shape defined as (x,y,z) -> Bool how can I find a Point inside this shape? Obviously I could iterate through all possible x,y and z, but this appears very expensive. There may be no point at all at x=0. With brute force iteration I would have no clue that the False I am receiving with (0,1,1) is caused by x=0 and I may nedlessly try all combinations of y and z without ever receiving a True. Are there any alternative ways of finding points inside a shape?
Hello all, > > I hope this is not a too silly question. It goes like this: > > Suppose I have a shape defined as > > (x,y,z) -> Bool > > how can I find a Point inside this shape? Obviously I could iterate through all
Are there any alternative ways of finding points inside a shape? > > _______________________________________________ > Haskell-Cafe mailing
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 You could try to use a data structure like a kd-tree, which can find the nearest neighbours to your point quite efficient. On 10/29/2015 10:01 AM, martin wrote: possible x,y and z, but this appears > very expensive. > > There may be no point at all at x=0. With brute force iteration I would have no clue that the False I am receiving with > (0,1,1) is caused by x=0 and I may nedlessly try all combinations of y and z without ever receiving a True. list > Haskell-Cafe@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iQEcBAEBCAAGBQJWMeMHAAoJEM0PYZBmfhoBcKUH/04/jSdP3660Ld1uWgK2P9BB iqAB4NnrRaCNbFNLSY6vNz1lFVm8p9ygxzZ4i+wfNbpa9V8tOvx2E2NJXaq/mLOr CDV9lS0LoQNWQCE41bH7QmEoK3ZiJjX1X0NolLpS2oBYhY1Jvwy/X8IUqoXAqZiu y+8CkExpJEL8dHmNXHwB4OmfRstRdcTumf/SVNhzwoHO+q+u8wz3d5PRSkCLSooB a5voFRdQpicfInzpW57+MHaQJtc1FtQ/+Ub4NQGh+rw5Npps/blQbvqgt/u1qcXL VwJqEonmF4T3NFxYAzfMR6rv/36MZcd39DK1+H2O5IrzIZXnXy007fw7irkiQ+0= =IIRy -----END PGP SIGNATURE-----
This representation ((x,y,z) _> bool) makes it very hard to find a point
inside. Basically it does not give you any info: does the shape have area?
What is it bounding box? Is it convex? Supposing x y and z are rationals
(arbitrary precision), then all these questions are not computable. I
suggest you use a different representation, such as a list of points for a
polygon.
On Oct 29, 2015 10:13 AM, "Jonas Scholl"
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256
You could try to use a data structure like a kd-tree, which can find the nearest neighbours to your point quite efficient.
Hello all, > > I hope this is not a too silly question. It goes like
Are there any alternative ways of finding points inside a shape? > > _______________________________________________ > Haskell-Cafe mailing
On 10/29/2015 10:01 AM, martin wrote: this: > > Suppose I have a shape defined as > > (x,y,z) -> Bool > > how can I find a Point inside this shape? Obviously I could iterate through all possible x,y and z, but this appears > very expensive. > > There may be no point at all at x=0. With brute force iteration I would have no clue that the False I am receiving with > (0,1,1) is caused by x=0 and I may nedlessly try all combinations of y and z without ever receiving a True. list > Haskell-Cafe@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
-----BEGIN PGP SIGNATURE----- Version: GnuPG v2
iQEcBAEBCAAGBQJWMeMHAAoJEM0PYZBmfhoBcKUH/04/jSdP3660Ld1uWgK2P9BB iqAB4NnrRaCNbFNLSY6vNz1lFVm8p9ygxzZ4i+wfNbpa9V8tOvx2E2NJXaq/mLOr CDV9lS0LoQNWQCE41bH7QmEoK3ZiJjX1X0NolLpS2oBYhY1Jvwy/X8IUqoXAqZiu y+8CkExpJEL8dHmNXHwB4OmfRstRdcTumf/SVNhzwoHO+q+u8wz3d5PRSkCLSooB a5voFRdQpicfInzpW57+MHaQJtc1FtQ/+Ub4NQGh+rw5Npps/blQbvqgt/u1qcXL VwJqEonmF4T3NFxYAzfMR6rv/36MZcd39DK1+H2O5IrzIZXnXy007fw7irkiQ+0= =IIRy -----END PGP SIGNATURE-----
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
On Thu, Oct 29, 2015 at 10:01:49AM +0100, martin wrote:
I hope this is not a too silly question. It goes like this:
Suppose I have a shape defined as
(x,y,z) -> Bool
how can I find a Point inside this shape? Obviously I could iterate through all possible x,y and z, but this appears very expensive.
There is no better way in general, so if you want to find points inside a shape you should use a different encoding of shapes. Tom
What if it is additionally known that the shape represented by (x,y,z) -> Bool has a closed, convex area (for example)? Most likely there are then techniques from algorithmic geometry that can find an inside point more efficiently than by iterating blindly through all coordinate triples. Am Donnerstag, 29. Oktober 2015 schrieb Tom Ellis :
I hope this is not a too silly question. It goes like this:
Suppose I have a shape defined as
(x,y,z) -> Bool
how can I find a Point inside this shape? Obviously I could iterate
On Thu, Oct 29, 2015 at 10:01:49AM +0100, martin wrote: through all possible x,y and z, but this appears
very expensive.
There is no better way in general, so if you want to find points inside a shape you should use a different encoding of shapes.
Tom _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org javascript:; http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Or maybe not. :-) If nothing more is known, say, about the ratio of the shape's area to the whole region's area. Am Donnerstag, 29. Oktober 2015 schrieb Janis Voigtländer :
What if it is additionally known that the shape represented by (x,y,z) -> Bool has a closed, convex area (for example)? Most likely there are then techniques from algorithmic geometry that can find an inside point more efficiently than by iterating blindly through all coordinate triples.
Am Donnerstag, 29. Oktober 2015 schrieb Tom Ellis :
I hope this is not a too silly question. It goes like this:
Suppose I have a shape defined as
(x,y,z) -> Bool
how can I find a Point inside this shape? Obviously I could iterate
On Thu, Oct 29, 2015 at 10:01:49AM +0100, martin wrote: through all possible x,y and z, but this appears
very expensive.
There is no better way in general, so if you want to find points inside a shape you should use a different encoding of shapes.
Tom _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
"Martin" asks:
Suppose I have a shape defined as (x,y,z) -> Bool how can I find a Point inside this shape? Obviously I could iterate through all possible x,y and z, but this appears very expensive.
Janis Voigtländer comments :
What if it is additionally known that the shape represented by (x,y,z) -> Bool has a closed, convex area (for example)? Most likely there are then techniques from algorithmic geometry that can find an inside point more efficiently than by iterating blindly through all coordinate triples.
Am Donnerstag, 29. Oktober 2015 schrieb Tom Ellis :
... There is no better way in general, so if you want to find points inside a shape you should use a different encoding of shapes.
You might discourage Martin from using his encoding, suggest using something different, nevertheless /*some people NEED implicit surfaces*/, useful for many purposes (e.g. for the ray tracing; polygonizing them may be horrible...) I don't understand what does it mean "find a point". ANY point? There is no "clever" solution for this yes/no relation. But people in image synthesis use more treatable representation: surf :: Point -> Real (e.g. a sphere = x^2+y^2+z^2-R^2, and not: x^2+y^2+z^2-R^2 < 0 . ) where, say, the interior is negative, exterior positive. Then with some initial, perhaps random steps, you may search with the aid of a moving simplex, or similar. And if the function is reasonably decent, gradient methods are good. This permits to find interesting points, such as barycenters or the surface itself. Jerzy Karczmarczuk
On 10/29/2015 11:36 AM, Janis Voigtländer wrote:
What if it is additionally known that the shape represented by (x,y,z) -> Bool has a closed, convex area (for example)? Most likely there are then techniques from algorithmic geometry that can find an inside point more efficiently than by iterating blindly through all coordinate triples.
It's easy to prove that this is not decidable (assuming we're talking about unbounded numbers, such as Data.Ratio.Rational, and not finite Double). Say you have an algorithm. Run it first on the empty space, and wait until it gives up after a finite number of probes. These probes all lie within some ball U. If you now insert your shape, however large, outside of the ball U, then the algorithm won't find it. Roman
It's easy to prove that this is not decidable
I'm not sure what you mean by "this", but if you mean "to find a point in
an infinitely large space by finitely many experiments", then of course it
is not decidable, and I'm surprised you go to such length to prove it. :-)
It is not in the original question as formulated (except as hints if you
look for them), but let's assume the problem is that you have (x,y,z) ->
Bool for x,y,z natural numbers below 100. And some of the 10^6 points are
True, others False. Is there a better algorithm for finding a True point
than blindly iterating through all 10^6 points?
I suggested that yes, there might be, if the shape is known to be convex
and a ratio is known of how much volume of the whole region it takes up.
Consider, for example, that the ratio is 0.5. Then only one check suffices
to find a point!
2015-10-29 13:23 GMT+01:00 Roman Cheplyaka
What if it is additionally known that the shape represented by (x,y,z) -> Bool has a closed, convex area (for example)? Most likely there are then techniques from algorithmic geometry that can find an inside point more efficiently than by iterating blindly through all coordinate
On 10/29/2015 11:36 AM, Janis Voigtländer wrote: triples.
It's easy to prove that this is not decidable (assuming we're talking about unbounded numbers, such as Data.Ratio.Rational, and not finite Double).
Say you have an algorithm. Run it first on the empty space, and wait until it gives up after a finite number of probes. These probes all lie within some ball U. If you now insert your shape, however large, outside of the ball U, then the algorithm won't find it.
Roman
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
On 10/29/2015 02:45 PM, Janis Voigtländer wrote:
It's easy to prove that this is not decidable
I'm not sure what you mean by "this", but if you mean "to find a point in an infinitely large space by finitely many experiments", then of course it is not decidable, and I'm surprised you go to such length to prove it. :-)
I guess I was equally surprised to see you suggesting doing that!
It is not in the original question as formulated (except as hints if you look for them), but let's assume the problem is that you have (x,y,z) -> Bool for x,y,z natural numbers below 100. And some of the 10^6 points are True, others False. Is there a better algorithm for finding a True point than blindly iterating through all 10^6 points?
I suggested that yes, there might be, if the shape is known to be convex and a ratio is known of how much volume of the whole region it takes up.
Consider, for example, that the ratio is 0.5. Then only one check suffices to find a point!
Now we are guessing, of course, but in my experience, when people casually talk about a shape in a 3-dimensional space without further clarification, they usually mean the 3d real Euclidean space or some approximation thereof.
Now we are guessing, of course, but in my experience, when people casually talk about a shape in a 3-dimensional space without further clarification, they usually mean the 3d real Euclidean space or some approximation thereof.
As long as we talk about a bounded range (cube) from that space, I am
actually willing to maintain my claim. (And the claim wouldn't make much
sense without such bounding, because I talked about the ratio of the
shape's volume vs. the range's volume.)
The discreteness, the coordinates being natural numbers in a finite range,
is not really important.
Say we look at the 3d space spanned by (0,0,0) to (1,1,1) in real numbers.
If there is a shape in there that is convex and takes up 0.5 of the volume,
I can find a point belonging to it with a single query.
If the ratio is 0.3 instead, what is the best querying strategy?
And so on.
2015-10-29 14:01 GMT+01:00 Roman Cheplyaka
On 10/29/2015 02:45 PM, Janis Voigtländer wrote:
It's easy to prove that this is not decidable
I'm not sure what you mean by "this", but if you mean "to find a point in an infinitely large space by finitely many experiments", then of course it is not decidable, and I'm surprised you go to such length to prove it. :-)
I guess I was equally surprised to see you suggesting doing that!
It is not in the original question as formulated (except as hints if you look for them), but let's assume the problem is that you have (x,y,z) -> Bool for x,y,z natural numbers below 100. And some of the 10^6 points are True, others False. Is there a better algorithm for finding a True point than blindly iterating through all 10^6 points?
I suggested that yes, there might be, if the shape is known to be convex and a ratio is known of how much volume of the whole region it takes up.
Consider, for example, that the ratio is 0.5. Then only one check suffices to find a point!
Now we are guessing, of course, but in my experience, when people casually talk about a shape in a 3-dimensional space without further clarification, they usually mean the 3d real Euclidean space or some approximation thereof.
On 10/29/2015 09:08 AM, Janis Voigtländer wrote:
Say we look at the 3d space spanned by (0,0,0) to (1,1,1) in real numbers. If there is a shape in there that is convex and takes up 0.5 of the volume, I can find a point belonging to it with a single query.
Better make that CLOSED and convex =)
2015-10-29 17:54 GMT+01:00 Michael Orlitzky
On 10/29/2015 09:08 AM, Janis Voigtländer wrote:
Say we look at the 3d space spanned by (0,0,0) to (1,1,1) in real numbers. If there is a shape in there that is convex and takes up 0.5 of the volume, I can find a point belonging to it with a single query.
Better make that CLOSED and convex =)
I guess I wouldn't call something without a border a "shape". So yes, closedness was assumed.
This problem can be considered as an instance of the more general SAT
problem, in which you're trying to find a satisfying assignment to a
predicate. You might want to give that approach a try, though it does
require changes in representation. Here's a *very* simple example:
Prelude> :m Data.SBV
Prelude Data.SBV> let f (x, y, z) = 0 .<= x &&& y .>= 2 &&& z .<=
x+(y::SInteger)
Prelude Data.SBV> sat f
Satisfiable. Model:
s0 = 0 :: Integer
s1 = 2 :: Integer
s2 = 2 :: Integer
Your "f" is probably going to be much more complicated, but if you can
afford to move to symbolic types, then SBV can bridge the gap and a SAT/SMT
solver can give you the required points. Or tell you if there isn't any,
like in the following example:
Prelude Data.SBV> sat $ \x y -> x .> y &&& x .< (y::SInteger)
Unsatisfiable
-Levent.
On Thu, Oct 29, 2015 at 2:01 AM, martin
Hello all,
I hope this is not a too silly question. It goes like this:
Suppose I have a shape defined as
(x,y,z) -> Bool
how can I find a Point inside this shape? Obviously I could iterate through all possible x,y and z, but this appears very expensive.
There may be no point at all at x=0. With brute force iteration I would have no clue that the False I am receiving with (0,1,1) is caused by x=0 and I may nedlessly try all combinations of y and z without ever receiving a True.
Are there any alternative ways of finding points inside a shape?
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
I understand that with (x,y,z)->Bool there is not much I can do other than brute force. But I am not forced to use this representation. The only thing I'd rather not do, is enumerate all the points. I thought the reactive guys found ways to manipulate Time->a functions without having to enumerate all the possible (Time,a) occurrences. But there live is "easy", because the possible times only depend on the start time and the sampling frequency (I may be awfully mistaken here). I thought about doing similar things, but with more than one coordinate, i.e. Time and Space. With just one coordinate I can answer "what will be at Time=t", but with two coordinates, the answer will be a function of space. But I can also ask "what will be at position x" and the result will be a function of time. Now, that does not look too difficult. I can always convert (x,y,z)->Bool to (y,z)->Bool if I happen to know x. I looks like I have to work on step one of the Fenyman Problem Solution Method ("write down the problem"). Thanks again. Am 10/29/2015 um 10:01 AM schrieb martin:
Hello all,
I hope this is not a too silly question. It goes like this:
Suppose I have a shape defined as
(x,y,z) -> Bool
how can I find a Point inside this shape? Obviously I could iterate through all possible x,y and z, but this appears very expensive.
There may be no point at all at x=0. With brute force iteration I would have no clue that the False I am receiving with (0,1,1) is caused by x=0 and I may nedlessly try all combinations of y and z without ever receiving a True.
Are there any alternative ways of finding points inside a shape?
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
On 29/10/2015, at 10:01 pm, martin
Hello all,
I hope this is not a too silly question. It goes like this:
Suppose I have a shape defined as
(x,y,z) -> Bool
how can I find a Point inside this shape?
What are x, y, z? Consider a simplified case: (Natural, Natural) -> Bool You can search (0,0) (1,0), (0,1) (2,0), (1,1), (0,2) (3,0), (2,1), (1,2), (0,3) ... and if the shape is not empty you'll find some point in it. For 3D, consider (0,0,0) (1,0,0) (0,1,0) (0,0,1) (2,0,0) (1,1,0) (1,0,1) (0,2,0) (0,1,1) (0,0,2) ...
Obviously I could iterate through all possible x,y and z, but this appears very expensive.
Yes it is, but if that's _all_ you know about a shape ... What if the shape is empty?
participants (11)
-
Atze van der Ploeg -
Imants Cekusins -
Janis Voigtländer -
Jerzy Karczmarczuk -
Jonas Scholl -
Levent Erkok -
martin -
Michael Orlitzky -
Richard A. O'Keefe -
Roman Cheplyaka -
Tom Ellis