Identifying Non-Smooth Boundary Curve Segments

December 24th, 2008

Let $P$ be a closed, non-self-intersecting, piecewise linear curve given by the points $P_l$ , which lie on a continuous surface. We seek, in a simplified sense here, a closed, non-self-intersecting piecewise linear curve $Q$ given by the points $Q_l$ , which still lie on the surface $S$ (and $Q$ is within a small distance from the surface) such that $Q$ ‘s distance to $P$ on the outside of the region bounded by $P$ is at most $\epsilon^+$ and to the inside at most $\epsilon^-$ . $Q$ should be in some sense smoother or fairer than $P$ . One approach to compute $Q$ is to first identify non-smooth segments of $P$ which can then be improved by some algorithm. Also see http://www.langbein.org/research/curves/smoothing/boundary-smoothing/.

In general a smooth or fair curve can be characterised by having a minimal number of segments with monotonic curvature (in our case geodesic curvature), i.e. minimise inflection points. Furthermore, the curve should overall have rather low curvature, i.e. minimise the curvature energy $\int \kappa^2\;ds$ , as far as this can be achieved under the constraints (see Euler’s elastica where the curve is only constrained by its end-points).

For a piecewise-linear curve a discrete curvature can be defined via the turning angles at its vertices. The turning angle values, however, depend on the sampling density as they are effectively the integrals over the curvature ( $d\phi = \kappa ds$ ). Using Taylor expansion of the curve the curvature at a vertex can be approximated by $\hat{\kappa}_l = 2\phi_l / (\|P_l-P_{l-1}\|+\|P_{l+1}-P_l\|)$ , which is optimal for three-point approximations in the linear terms and converges of fourth order for elastica if all edges have equal length (Langer et al, 2005, http://tinyurl.com/a25thy).

Using the above approximation we can determine inflection points as sign changes and using a maximum (absolute) curvature limit can furthermore label curve vertices as non-smooth if they exceed the limit. However, this alone does not identify non-smoothness of a curve on a larger scale than the local sampling distance. Moreover, the sampling distance should be reasonably uniform, which may or may not be the case for $P$ . If $P$ is noisy it may also result in rather noisy local curvature estimates, which can over- and under-estimate the curvature behaviour on a larger scale.

One way of identifying non-smooth curve segments on a larger scale is to ask how far the curve can be smoothed within the tolerance zone set by $\epsilon^+$ and $\epsilon^-$ in terms of how much $\int \kappa^2\;ds$ can be minimised within the tolerance zone. An efficient way to do this without actually solving the optimisation problem may be to estimate how far $\hat{\kappa}_l$ can be minimised by moving the three $P_l$ within the tolerance zone. Obviously one can then always minimise this to 0 by arranging the points along a (very short) line segment, so further restrictions are needed. One can restrict to move only $P_{l-1}, P_{l+1}$ along the curve to a maximum distance and find the minimal curvature to estimate the improvement possible by taking the difference between the minimum and the actual local estimate. Or move the points “orthogonal” to the curve in the tolerance zone again to find the best improvement. Or possibly find the (approximately) longest line segment through $P_l$ lying inside the tolerance zone to set the scale along which $P_{l-1},P_{l+1}$ can be moved along the curve to estimate the curvature improvement.

In general estimating the variation of curvature possible over a certain length range seems to indicate quite well how much the curve may be smoothed locally under the constraints and hence either label vertices with high potential for smoothing as non-smooth or even derive a smoothing priority for the vertices. See the figures below where the curve is plotted in black, the maximal improvement of the absolute curvature in magenta and curve vertices which can be improved by more than a certain amount are marked blue. Underneath the estimated vertex curvature is plotted in red, the maximal and minimal curvature achieved by moving the two adjacent points along the curve a certain maximal distance are plotted in green and the mean curvature is plotted in blue. The range the points could be moved is about four times as big in the first figure compared to the second figure.