Recognition of concurrency relations between inaccurate lines

Abstract

In this paper, we propose a new efficient method for recognizing multiple concurrency relations between inaccurately drawn lines. The proposed technique constructs a solution by combining borderline cases. For each line there is a parameter domain, which specifies how the line can move within the borders imposed by a set of support lines and support points. To encode the way in which the borderline cases can be combined we introduce the concept of a rank vector. This vector measures how many degrees of freedom (dof) are left when a line is pushed within its borders towards a solution. Experimental evaluation has demonstrated that with respect to geometric concurrency problems the proposed method can solve problems that are far beyond the reach of conventional non-linear problem-solvers. This is mainly due to the use of rank vectors that encode all the possible ways in which a solution can be constructed.

Keywords:

• concurrency relations
• sketch recognition
• geometric constructions

Keywords:

• 52C35
• 52C45
• 68U05