0
$\begingroup$

I have a sampled function sruface

$$ z = f(x, y) $$

represented as a grayscale raster image. How to find the upper convex hull of that surface. That is I am looking for the minimal

$$ g(x, y) $$

such that

$$ g(x, y) \geq f(x, y), \text{Eigenvalues}(\text{Hessian}(g)) < 0 $$

It is possible to convert the image into a 3d mesh, and then use qhull or similar, but that would result in too much overhead.

Improve this question
$\endgroup$
7
  • $\begingroup$ Why do you think that qhull is inappropriate ? $\endgroup$ Commented Feb 18, 2023 at 14:18
  • $\begingroup$ @YvesDaoust Memory concerns. Converting a large image (16 MP) to a mesh will take a lot of memory. $\endgroup$ Commented Feb 18, 2023 at 14:41
  • $\begingroup$ Then roll your own qhull using the points straight from the image. The hull should be much more compact (unless your surface is already convex). $\endgroup$ Commented Feb 18, 2023 at 14:52
  • 1
    $\begingroup$ Note that a convex hull algorithm does not need a mesh but just points. If they are represented on 3 ints or floats, this is 12 bytes per point. $\endgroup$ Commented Feb 18, 2023 at 14:57
  • $\begingroup$ @YvesDaust And then you need to construct a triangulation, followed by a polygonal fill. $\endgroup$ Commented Feb 18, 2023 at 16:09

1 Answer 1

Reset to default
0
$\begingroup$

I figured out that there is a problem with the convex hull of a raster image, namely the fact that it is essentially constructed of quads, which gives an ambiguity. For example, consider the example below:

0 1 1 0

This could be interprted like

0 -- 1 | / | | / | 1 -- 0 
0 -- 1 | \ | | \ | 1 -- 0

Which obviously results in a different upper convex hull. Thus, a general convex hull algorithm would be required.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.