# [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.

> 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...