[Haskell-cafe] Find a point inside (x,y,z) -> Bool

Jerzy Karczmarczuk jerzy.karczmarczuk at unicaen.fr
Thu Oct 29 10:04:48 UTC 2015

"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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151029/6200e7c9/attachment-0001.html>

More information about the Haskell-Cafe mailing list