Suppose that we have two polyhedra $P_1$ and $P_2$ in $\mathbb{R}^3$. I would like to define such a metric $\rho(P_1, P_2)$ that depends on several factors, but currently I don't know how to do it better.

The distance is intended to be smaller if:

  1. "big facets" of $P_1$ have one-to-one correspondence with "big facets" of $P_2$,

  2. "big facets" of $P_1$ and $P_2$ that correspond to each other are close to each other within Hausdorff distance,

  3. "big facets" $f_{1,1}$ and $f_{1,2}$ of $P_1$ that share some edge $e_1$ have corresponding "big facets" $f_{2,1}$ and $f_{2,2}$ that also share some edge $e_2$, and $f_{1,1}$ is close to $f_{2,1}$, $f_{1,2}$ is close to $f_{2,2}$, and $e_1$ is close to $e_2$ within Hausdorff distance,

  4. the same as (3), but "share some edge $e_1$" is replaced with "have close edges $e_{1,1}$ and $e_{1, 2}$" and so on.

Actually, the facet is considered to be "big" if its area $area(f)$ is "big". We may introduce some parameter $\varepsilon$ which will show whether the facet is big: $area(f) > \varepsilon$. But it seems that it would be better if the metric is parameter-free.

So my question consists of the following parts:

  1. Is the concept described above already studied in the literature? Or at least anything related to this?

  2. What is the most convenient way to make the metric definition? It seems that this is a hybrid of Hausdorff distance in Euclidean space and graph distance.

Actually, I'm trying to make the reconstruction in this metric, and to prove the properties of any algorithm I need to make a strict definition of this metric. So it would be great to make it as simple as possible.

Any ideas are welcome!


Two suggestions of literature that might lead you somewhere useful (but neither of these references in themselves seem to address your several criteria). The first below uses curvature distributions. The second uses Minkowski's mixed volumes. Both introductions survey "shape similarity" measures.

Shum, Heung-Yeung, Martial Hebert, and Katsushi Ikeuchi. "On 3D shape similarity." In Proceedings CVPR IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 526-531. IEEE, 1996. PDF download.

Roerdink, Jos BTM, and Henk Bekker. "Similarity measure computation of convex polyhedra revisited." In Digital and Image Geometry, pp. 389-399. Springer, Berlin, Heidelberg, 2001. Book link.

  • 1
    $\begingroup$ Thanks for reference! After looking first one, I can say that this measure reflects the incidence structure somehow. But in the second paper, the mixed volume is $\sum{h_A(u_i)S(f_i)}$ where $f_i$ are facets of B and $u_i$ are their outer normals. What I can say is that if we divide one of facets onto two facets, the value of formula doesn't change. So it doesn't reflect the incidence structure. But the formula looks very attractive. Maybe we can modify it in a way that to make it reflect the incidence structure: $$\sum{h_A(u_i)c(S(f_i))}$$ where $c()$ is concave function. What do you think? $\endgroup$ – Ilya Palachev Mar 13 '20 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.