Linear-time algorithms for testing the realisability of line drawings of curved objects

摘要

This paper shows that the semantic labelling of line drawings of curved objects with piecewise C3 surfaces is solvable in linear time. This result is robust to changes in the assumptions on object shape. When all vanishing points are known, a different linear-time algorithm exists to solve the labelling problem. Furthermore, in both cases, all legally labelled line drawings of curved objects are shown to be physically realisable.