NCH: cerrando las brechas

Introducción

A continuación de mi último artículo sobre NCH siendo invariante a roto-traslaciones, la idea de este es cubrir lo que considero las brechas más importantes que deja el breve artículo original. Mi expectativa es que hacer esto ayude a entender mejor por qué NCH funciona y, con suerte, permita obtener alguna intuición sobre cómo mejorarlo.

Equivalencia de formulaciones

La ecuación (4) del artículo dice:

f_{i}^{r_{i}} (x) = \frac{1}{2 r _{i}} (r_{i}^{2} - ∣∣ x - (p_{i} + r_{i} n_{i}) ∣ ∣^{2})

Sin embargo, la definición usada en (2) es ligeramente diferente. ¿De dónde viene (2)? De expandir los productos internos en el segundo término de la suma:

∣∣ x - (p_{i} + r_{i} n_{i}) ∣ ∣^{2} = ⟨ x - p_{i} - r_{i} n_{i}, x - p_{i} - r_{i} n_{i} ⟩ = ⟨ x - p_{i}, x - p_{i} ⟩ + ⟨ x - p_{i}, - r_{i} n_{i} ⟩ + ⟨ - r_{i} n_{i}, x - p_{i} ⟩ + ⟨ - r_{i} n_{i}, - r_{i} n_{i} ⟩ = ∣∣ x - p_{i} ∣ ∣^{2} + (- 2 r_{i}) ⟨ n_{i}, x - p_{i} ⟩ + r_{i}^{2}

Entonces, al reemplazar en la definición original:

f_{i}^{r_{i}} (x) = \frac{1}{2 r _{i}} (r_{i}^{2} - (∣∣ x - p_{i} ∣ ∣^{2} + (- 2 r_{i}) ⟨ n_{i}, x - p_{i} ⟩ + r_{i}^{2})) = \frac{1}{2 r _{i}} (- ∣∣ x - p_{i} ∣ ∣^{2} + (2 r_{i}) ⟨ n_{i}, x - p_{i} ⟩) = ⟨ n_{i}, x - p_{i} ⟩ - \frac{1}{2 r _{i}} ∣∣ x - p_{i} ∣ ∣^{2}

Que es exactamente lo que queríamos.

Los ρᵢs fantásticos y dónde encontrarlos

En la ecuación (3), el autor indica cuál debería ser el valor de $ρ_i$ . Luego define $r_{i}$ como el valor más grande de $r$ tal que $f_{i}^{r} (p_{j}) \leq 0\forall p_{j} \in P, j \neq = i$ . Si lo escribís explícitamente:

0 \geq f_{i}^{r} (p_{j}) = ⟨ n_{i}, p_{j} - p_{i} ⟩ - \frac{1}{2 r _{i}} ∣∣ p_{j} - p_{i} ∣ ∣^{2}

Y por lo tanto

\frac{1}{2 r _{i}} \geq \frac{⟨ n _{i} , p _{j} - p _{i} ⟩}{∣∣ p _{j} - p _{i} ∣ ∣ ^{2}}

Si reunís las restricciones para todos los $p_{j}$ juntos, entonces tenés que

ρ_i \geq p_{j} \in P, i \neq = j max \frac{⟨ n _{i} , p _{j} - p _{i} ⟩}{∣∣ p _{j} - p _{i} ∣ ∣ ^{2}}

Y además necesitamos que $ρ_i \geq 0$ en el caso en que el conjunto de soporte termine siendo simplemente el semiespacio lineal (como debería ocurrir al ajustar planos, por ejemplo).

Los ρs y los θs

Una cosa interesante para notar a partir de la estimación de $ρ$ es que (en notación no estándar, pero suficiente para entender):

ρ_{i} = p_{j} \in P, i \neq = j max {0, \frac{⟨ n _{i} , p _{j} - p _{i} ⟩}{∣∣ p _{j} - p _{i} ∣ ∣ ^{2}}} = p_{j} \in P, i \neq = j max {0, \frac{1}{∣∣ p _{j} - p _{i} ∣∣} ⟨ n_{i}, \frac{p _{j} - p _{i}}{∣∣ p _{j} - p _{i} ∣∣} ⟩} = p_{j} \in P, i \neq = j max {0, \frac{cos_sim ( n _{i} , p _{j} - p _{i} )}{∣∣ p _{j} - p _{i} ∣∣}}

Donde $cos_sim$ denota la similitud coseno entre los dos vectores; es decir, el ángulo entre ellos. Los siguientes gráficos muestran la componente del máximo de arriba para un $p_{i}$ y un $n_{i}$ dados (notá que $p_{i}$ NO está incluido en el gráfico, por razones obvias), así como la similitud coseno. Podés ajustar los parámetros:

Los resultados son los esperados: hacia el exterior de la superficie (es decir, en la dirección inversa a la normal) obtenemos valores negativos, y hacia el interior obtenemos valores positivos. Sin embargo, la contribución de un punto al máximo decrece muy rápidamente a medida que uno se aleja del punto central, porque la similitud coseno está acotada entre $- 1$ y $1$ , mientras que la distancia por la que se divide puede ser arbitrariamente grande.

Esto puede ser una forma interesante de construir una heurística para acelerar NCH: procesar únicamente los $O (N)$ puntos más cercanos al calcular el rho.

Introducción

Equivalencia de formulaciones

Los ρᵢs fantásticos y dónde encontrarlos

Los ρs y los θs

Más en la serie “Non-Convex Hull”

Relacionados