Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Arrangement of lines
Résumé
In geometry, an arrangement of lines is the subdivision of the plane formed by a collection of lines. Problems of counting the features of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.
Intuitively, any finite set of lines in the plane cuts the plane into two-dimensional polygons (cells), one-dimensional line segments or rays, and zero-dimensional crossing points. This can be formalized mathematically by classifying the points of the plane according to which side of each line they are on. Each line separates the plane into two open half-planes, and each point of the plane has three possibilities per line: it can be in either one of these two half-planes, or it can be on the line itself. Two points can be considered to be equivalent if they have the same classification with respect to all of the lines. This is an equivalence relation, whose equivalence classes are subsets of equivalent points. These subsets subdivide the plane into shapes of the following three types:
The cells or chambers of the arrangement are two-dimensional regions not part of any line. They form the interiors of bounded or unbounded convex polygons. If the plane is cut along all of the lines, these are the connected components of the points that remain uncut.
The edges or panels of the arrangement are one-dimensional regions belonging to a single line. They are the open line segments and open infinite rays into which each line is partitioned by its crossing points with the other lines. That is, if one of the lines is cut by all the other lines, these are the connected components of its uncut points.
The vertices of the arrangement are isolated points belonging to two or more lines, where those lines cross each other.
The boundary of a cell is the system of edges that touch it, and the boundary of an edge is the set of vertices that touch it (one vertex for a ray and two for a line segment).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.