[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