Bentley-Ottmann algorithm
- Bentley-Ottmann algorithm
The Bentley-Ottmann algorithm is a sweep line algorithm for solving the line segment intersection problem on a plane. It works by considering the intersections of the line segments with a "sweep" line which is moved progressively across the set of line segments.
See also
* Scan-line rendering
* Shamos-Hoey algorithm
External links
* [http://geometryalgorithms.com/Archive/algorithm_0108/algorithm_0108.htm#Bentley-Ottmann%20Algorithm Bentley-Ottmann algorithm] at geometryalgorithms.com
Wikimedia Foundation.
2010.
Look at other dictionaries:
Sweep line algorithm — In computational geometry, a sweep line algorithm or plane sweep algorithm is a type of algorithm that uses a conceptual sweep line or sweep surface to solve various problems in Euclidean space. It is one of the key techniques in computational… … Wikipedia
Line segment intersection — In computational geometry, the line segment intersection problem supplies a list of line segments in the plane and asks us to determine whether any two of them intersect, or cross.Naive algorithms examine each pair of segments, but this is highly … Wikipedia
List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… … Wikipedia
List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… … Wikipedia
Boolean operations on polygons — are a set of Boolean operations (AND, OR, NOT, XOR, etc.) operating on one or more sets of polygons. These sets of operations are widely used in computer graphics, CAD, and in EDA (in integrated circuit physical design and verification… … Wikipedia
