In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments, i.e. it finds the intersection points (or, simply, intersections) of line segments. It extends the , a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of line segments with crossings (or intersections), the Bentley–Ottmann algorithm takes time . In cases where , this is an improvement on a naïve algorithm that tests every pair of segments, which takes .
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Bentley–Ottmann algorithm (en)
- Algorithme de Bentley-Ottmann (fr)
- Алгоритм Бентли — Оттманна (ru)
- Алгоритм Бентлі — Оттманна (uk)
|
| rdfs:comment
| - In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments, i.e. it finds the intersection points (or, simply, intersections) of line segments. It extends the , a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of line segments with crossings (or intersections), the Bentley–Ottmann algorithm takes time . In cases where , this is an improvement on a naïve algorithm that tests every pair of segments, which takes . (en)
- En géométrie algorithmique, l'algorithme de Bentley-Ottmann est un algorithme de sweep line pour trouver les (en). C'est une généralisation de l'algorithme de Shamos et Hoey qui vérifie si un ensemble de segments possède des intersections ou non. Pour n segments avec k intersections, la complexité en temps de l'algorithme de Bentley-Ottmann est O((n + k) log n). Dans le cas où k = o(n2 / log n), c'est une amélioration de l'algorithme naïf qui teste chaque pair de segments en temps O(n2). (fr)
- Алгоритм Бентли — Оттманна (1979) позволяет найти все точки пересечений прямолинейных отрезков на плоскости. В нем применяется метод выметающей прямой (заметающей прямой, движущейся прямой, сканирующей линии; англ. sweeping line). В методе используется вертикальная выметающая прямая, движущаяся слева направо, при этом отрезки, которые она пересекает при данной координате , можно упорядочить по координате , тем самым их можно сравнивать между собой (какой выше, какой ниже). Это сравнение можно осуществить, например, используя уравнение прямой, проходящей через две точки (отрезки заданы двумя своими конечными точками): , где , и , — координаты, соответственно, первой и второй точек отрезка. Выметающая прямая перемещается по так называемым точкам событий (левым и правым концам отрезков, а т (ru)
- Алгоритм Бентлі — Оттманна в обчислювальній геометрії використовує метод замітання прямою для пошуку всіх точок перетину прямолінійних відрізків на площині. Він узагальнює алгоритм Шеймоса-Нойї, який задану множину відрізків перевіряв на наявність будь-якого перетину. Для вхідних даних, які містять відрізків, що мають переринів, алгоритм Бентлі — Оттманна виконується за час . У випадку, коли , його можна розглядати як удосконалення алгоритму повного перебору, який виконується за час . (uk)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| date
| |
| first
| |
| last
| - Bentley (en)
- Ottmann (en)
|
| reason
| - it's not explained what internal and leaf nodes of the binary search tree represent. How are line segments compared to each other, while inserting, deleting or finding the predecessor or successor of a line segment? What makes a line segment the predecessor and successor of another line segment? (en)
- It may not be easy to visualize this concept without a simple animation, unless you already know the algorithm. (en)
|
| small
| |
| year
| |
| has abstract
| - In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments, i.e. it finds the intersection points (or, simply, intersections) of line segments. It extends the , a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of line segments with crossings (or intersections), the Bentley–Ottmann algorithm takes time . In cases where , this is an improvement on a naïve algorithm that tests every pair of segments, which takes . The algorithm was initially developed by Jon Bentley and Thomas Ottmann; it is described in more detail in the textbooks , , and . Although asymptotically faster algorithms are now known by and , the Bentley–Ottmann algorithm remains a practical choice due to its simplicity and low memory requirements. (en)
- En géométrie algorithmique, l'algorithme de Bentley-Ottmann est un algorithme de sweep line pour trouver les (en). C'est une généralisation de l'algorithme de Shamos et Hoey qui vérifie si un ensemble de segments possède des intersections ou non. Pour n segments avec k intersections, la complexité en temps de l'algorithme de Bentley-Ottmann est O((n + k) log n). Dans le cas où k = o(n2 / log n), c'est une amélioration de l'algorithme naïf qui teste chaque pair de segments en temps O(n2). L'algorithme a été développé à l'origine par . Il est décrit plus en détail dans les articles de , , et . Bien que des algorithmes asymptotiquement plus rapides sont connus, l'algorithme de Bentley-Ottmann reste un choix pratique en raison de sa simplicité et de faibles besoins en mémoire. (fr)
- Алгоритм Бентли — Оттманна (1979) позволяет найти все точки пересечений прямолинейных отрезков на плоскости. В нем применяется метод выметающей прямой (заметающей прямой, движущейся прямой, сканирующей линии; англ. sweeping line). В методе используется вертикальная выметающая прямая, движущаяся слева направо, при этом отрезки, которые она пересекает при данной координате , можно упорядочить по координате , тем самым их можно сравнивать между собой (какой выше, какой ниже). Это сравнение можно осуществить, например, используя уравнение прямой, проходящей через две точки (отрезки заданы двумя своими конечными точками): , где , и , — координаты, соответственно, первой и второй точек отрезка. Выметающая прямая перемещается по так называемым точкам событий (левым и правым концам отрезков, а также точкам пересечения отрезков). После точки пересечения отрезки следует менять местами, так как, например, самый верхний из пересекающихся отрезков после точки пересечения становится самым нижним. Приведенный ниже алгоритм не рассчитан на случай, когда два отрезка пересекаются больше, чем в одной точке. NB Выметающую прямую можно также представить как горизонтальную, движущуюся сверху вниз по координате , и сравнивать пересекающие её отрезки по координате . (ru)
- Алгоритм Бентлі — Оттманна в обчислювальній геометрії використовує метод замітання прямою для пошуку всіх точок перетину прямолінійних відрізків на площині. Він узагальнює алгоритм Шеймоса-Нойї, який задану множину відрізків перевіряв на наявність будь-якого перетину. Для вхідних даних, які містять відрізків, що мають переринів, алгоритм Бентлі — Оттманна виконується за час . У випадку, коли , його можна розглядати як удосконалення алгоритму повного перебору, який виконується за час . Алгоритм був розроблений Джоном Бентлі та Томасом Оттманном у 1979 році. Більш детально він описаний у книгах , , та . Хоча й відомі асимптотично більш швідкі алгоритми, алгоритм Бентлі — Оттманна залишається затребуваним завдяки простоті та використанню низького об'єму пам'яті[джерело?]. (uk)
|
| author1-link
| |
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is Wikipage disambiguates
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)