Sweep line algorithm (original) (raw)
En géométrie algorithmique, un algorithme de sweep line (ligne de balayage) est un type d'algorithme utilisant une "ligne de balayage" virtuelle pour résoudre des problèmes dans l'espace euclidien.
| Property | Value |
|---|---|
| dbo:abstract | Als Sweep, Sweep-Verfahren oder manchmal auch Scan-Verfahren wird ein Paradigma in der Informatik verstanden, das beim Design von Algorithmen Anwendung findet. Ein derartiger Algorithmus wird auch Sweep-Algorithmus genannt. Kern eines Sweep im Zweidimensionalen ist die Sweep-Line (Sweep-Gerade) bzw. im Dreidimensionalen die Sweep-Plane (Sweep-Ebene). Durch sie wird der Raum „ausgefegt“, das heißt, man bewegt sie durch den gesamten Raum, bis alle Objekte des Problems besucht und verarbeitet wurden. Dazu wird eine Datenstruktur verwendet, die die von der Sweep-Line oder -Plane berührten Objekte speichert. Eine solche Datenstruktur wird dann als Sweep-Status-Struktur bezeichnet. Besonders häufig werden dadurch Probleme der Algorithmischen Geometrie gelöst. Allgemein wird bei einem Sweep ein -dimensionales statisches Problem in ein (n-1)-dimensionales dynamisches Problem umgewandelt. (de) En géométrie algorithmique, un algorithme de sweep line (ligne de balayage) est un type d'algorithme utilisant une "ligne de balayage" virtuelle pour résoudre des problèmes dans l'espace euclidien. (fr) In computational geometry, a sweep line algorithm or plane sweep algorithm is an algorithmic paradigm 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 geometry. The idea behind algorithms of this type is to imagine that a line (often a vertical line) is swept or moved across the plane, stopping at some points. Geometric operations are restricted to geometric objects that either intersect or are in the immediate vicinity of the sweep line whenever it stops, and the complete solution is available once the line has passed over all objects. (en) Алгоритм заметающей прямой или алгоритм выметания плоскости — это алгоритмическая парадигма, которая использует умозрительную выметающую прямую или выметающую поверхность для решения различных задач в евклидовом пространстве. Это одна из ключевых техник в вычислительной геометрии. Идея алгоритмов этого типа заключается в представлении себе воображаемой прямой (чаще вертикальной), которая движется по плоскости, останавливаясь в некоторых точках. Геометрические операции ограничены геометрическими объектами, которые или пересекаются, или примыкают к выметающей прямой, а полное решение доступно, когда прямая пройдёт через все объекты. (ru) Алгоритм замітання прямою або алгоритм замітання площини — це алгоритмічна парадигма, яка використовує уявну замітальну пряму або замітальну поверхню для розв'язування різних задач у евклідовому просторі. Це одна з ключових технік обчислювальної геометрії. Ідея алгоритмів цього типу полягає у використанні уявної прямої (частіше вертикальної), яка рухається площиною і зупиняється у деяких точках, де відбуваються обчислення. Геометричні операції обмежені геометричними об'єктами, які або перетинаються, або прилягають до замітальної прямої, а повний розв'язок доступний, коли пряма пройде через усі об'єкти. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Fortunes-algorithm.gif?width=300 |
| dbo:wikiPageID | 8700856 (xsd:integer) |
| dbo:wikiPageLength | 4021 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123298252 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algorithmic_paradigm dbr:Delaunay_triangulation dbr:Integrated_circuit_layout dbr:Analysis_of_algorithms dbr:Bentley–Ottmann_algorithm dbc:Geometric_algorithms dbr:Computational_geometry dbr:Computer_graphics dbr:Euclidean_space dbr:Fortune's_algorithm dbr:Big_O_notation dbr:Boolean_operations_on_polygons dbr:Rotating_calipers dbr:Michael_Ian_Shamos dbr:Voronoi_diagram dbr:Self-balancing_binary_search_tree dbr:Scanline_algorithm dbr:Line_segment_intersection dbr:Projective_dual dbr:File:Fortunes-algorithm.gif |
| dbp:wikiPageUsesTemplate | dbt:Citation_needed dbt:Reflist dbt:Algorithmic_paradigms |
| dct:subject | dbc:Geometric_algorithms |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGeometricAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms |
| rdfs:comment | En géométrie algorithmique, un algorithme de sweep line (ligne de balayage) est un type d'algorithme utilisant une "ligne de balayage" virtuelle pour résoudre des problèmes dans l'espace euclidien. (fr) Als Sweep, Sweep-Verfahren oder manchmal auch Scan-Verfahren wird ein Paradigma in der Informatik verstanden, das beim Design von Algorithmen Anwendung findet. Ein derartiger Algorithmus wird auch Sweep-Algorithmus genannt. Kern eines Sweep im Zweidimensionalen ist die Sweep-Line (Sweep-Gerade) bzw. im Dreidimensionalen die Sweep-Plane (Sweep-Ebene). Durch sie wird der Raum „ausgefegt“, das heißt, man bewegt sie durch den gesamten Raum, bis alle Objekte des Problems besucht und verarbeitet wurden. Dazu wird eine Datenstruktur verwendet, die die von der Sweep-Line oder -Plane berührten Objekte speichert. Eine solche Datenstruktur wird dann als Sweep-Status-Struktur bezeichnet. Besonders häufig werden dadurch Probleme der Algorithmischen Geometrie gelöst. Allgemein wird bei einem Sweep ein - (de) In computational geometry, a sweep line algorithm or plane sweep algorithm is an algorithmic paradigm 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 geometry. (en) Алгоритм замітання прямою або алгоритм замітання площини — це алгоритмічна парадигма, яка використовує уявну замітальну пряму або замітальну поверхню для розв'язування різних задач у евклідовому просторі. Це одна з ключових технік обчислювальної геометрії. (uk) Алгоритм заметающей прямой или алгоритм выметания плоскости — это алгоритмическая парадигма, которая использует умозрительную выметающую прямую или выметающую поверхность для решения различных задач в евклидовом пространстве. Это одна из ключевых техник в вычислительной геометрии. (ru) |
| rdfs:label | Sweep (Informatik) (de) Algorithme de sweep line (fr) Sweep line algorithm (en) Алгоритм заметающей прямой (ru) Алгоритм замітання прямою (uk) |
| owl:sameAs | freebase:Sweep line algorithm yago-res:Sweep line algorithm wikidata:Sweep line algorithm dbpedia-de:Sweep line algorithm dbpedia-fa:Sweep line algorithm dbpedia-fr:Sweep line algorithm dbpedia-ru:Sweep line algorithm dbpedia-uk:Sweep line algorithm https://global.dbpedia.org/id/2Ex8T |
| prov:wasDerivedFrom | wikipedia-en:Sweep_line_algorithm?oldid=1123298252&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Fortunes-algorithm.gif |
| foaf:isPrimaryTopicOf | wikipedia-en:Sweep_line_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:Sweep |
| is dbo:wikiPageRedirects of | dbr:Generalizations_of_the_sweep_line_algorithm dbr:Line_sweep_algorithm dbr:Plane_sweep dbr:Sweep_line dbr:Sweepline dbr:Sweepline_algorithm |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Visibility_polygon dbr:Algorithmic_paradigm dbr:Theta_graph dbr:Generalizations_of_the_sweep_line_algorithm dbr:Bentley–Ottmann_algorithm dbr:Closest_pair_of_points_problem dbr:Sweep dbr:Fortune's_algorithm dbr:Kinetic_convex_hull dbr:Rectilinear_minimum_spanning_tree dbr:Monotone_priority_queue dbr:Polygon_triangulation dbr:Boolean_operations_on_polygons dbr:Catalan's_minimal_surface dbr:Rotating_calipers dbr:Michael_Ian_Shamos dbr:Multiple_line_segment_intersection dbr:Line_sweep_algorithm dbr:Plane_sweep dbr:Sweep_line dbr:Sweepline dbr:Sweepline_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Sweep_line_algorithm |
