[Haskell-cafe] Find a point inside (x,y,z) -> Bool
Olaf Klinke
olf at aatal-apotheke.de
Fri Oct 30 19:02:57 UTC 2015
Martin,
this may be impractical performance-wise, but Haskell offers magic
data structures for searching. Have a look at Martin Escardo's blog post
[1] on infinite search in finite time. There is a package on Hackage [2]
implementing it. The `shapes` you get are compact, non-empty subsets of
types. If you have a shape
shape :: Data.Searchable.Set a
then
Data.Searchable.search (const True) shape
will return some element of your shape. As far as I know nobody has ever
used this data structure for solid geometry. You'd need to combine it with
some implementation of exact reals [*] to have geometry in a product of
closed intervals. A downside is that general intersections don't exist,
since the shapes must be non-empty. But since images of searchable sets
are searchable, you could define complicated shapes by starting with a
simple one and distort it with a function.
If your type of space is discrete, then the search function might resort
to brute force enumeration if the shape was defined that way.
-- Olaf
[1]
http://math.andrej.com/2008/11/21/a-haskell-monad-for-infinite-search-in-finite-time/
[2]
http://hackage.haskell.org/package/infinite-search
[*]
As far as I am aware there is no appropriate package on Hackage, but
Haskell implementations exist in several theses.
More information about the Haskell-Cafe
mailing list