Line Segments Intersection in a Discrete Domain

• Grant number: 12/19196-0
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: February 01, 2013
• End date: January 31, 2014
• Field of knowledge: Engineering - Mechanical Engineering
• Principal Investigator: Marcos de Sales Guerra Tsuzuki
• Grantee: Marcel Lourenço de Luna
• Host Institution: Escola Politécnica (EP). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

The segments of line have already been studied under various aspects in the mathematics field, like vector analysis and numerical analysis. A common problem in that field is the determination of the intersection between two or more line segments. It is known that the comparison among floating point numbers through a tolerance is not transitive. For this reason, robust geometric algorithms do not use floating point, but the integer representation. Determining the intersection among segments of line in discrete domain is even more complex. Particularly, in this research, it is shown that the actual methods for determining the intersection among line segments in discrete domain are not commutative. In this research project, a new representation will be proposed such that the intersection among line segments becomes commutative.