This HTML5 document contains 63 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n7http://geomalgorithms.com/
dbpedia-eshttp://es.dbpedia.org/resource/
n6https://global.dbpedia.org/id/
n18http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Sweep_line_2/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n4http://alienryderflex.com/intersect/
n17https://archive.org/details/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/
n22https://web.archive.org/web/20050601132020/http:/compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/
n23https://web.archive.org/web/20160707015648/http:/www.cs.wustl.edu/~pless/506/
n8https://web.archive.org/web/20171020091733/http:/www.cs.wustl.edu/~pless/546/

Statements

Subject Item
dbr:Intersection_(geometry)
rdfs:seeAlso
dbr:Multiple_line_segment_intersection
Subject Item
dbr:Multiple_line_segment_intersection
rdfs:label
Intersección de segmentos de recta Перетин відрізків Задача о пересечении отрезков Multiple line segment intersection
rdfs:comment
В обчислювальній геометрії, задача про перетин відрізків для заданого списку відрізоків на евклідовій площині з'ясовує чи знайдеться серед них пара відрізків, які будуть перетинатися. Примітивний алгоритм, який вирішує цю задачу, може перевіряти кожну пару відрізків на перетин. Швидкість такого алгоритму буде квадратичною для відрізків. Тому, коли потрібно перевірити дуже велику кількість відрізків на перетин, цей алгоритм стає все більш неефективним, оскільки більшість пар відрізків не є близькими один до одного для довільної послідовності відрізків. Найпоширеніший і більш ефективний спосіб розв'язати цю задачу для великої кількості відрізків — це використовувати метод замітання прямою, в якому пряма просувається по впорядкованій послідовності відрізків, а ми перевіряємо на перетин ті в En geometría computacional el problema de intersección de segmentos de recta está dado de la siguiente manera: dado un conjunto de n segmentos en el plano euclidiano se deben reportar todos los puntos de intersección en todo el conjunto . Задача о пересечении отрезков заключается в определении, пересекаются ли какие-либо два отрезка из заданного списка на плоскости. Простые алгоритмы проверяют каждую пару отрезков. Однако если нужно проверить большое число отрезков на пересечение, задача становится возрастающе неэффективной, поскольку большинство пар отрезков при обычном вводе не лежат близко друг от друга. Наиболее общий и более эффективный путь решения этой задачи для большого числа отрезков заключается в использовании алгоритма заметающей прямой, в котором мы воображаем себе прямую, проходящую через отрезки, и отслеживаем пересечения отрезков с помощью структуры данных, основанной на двоичных деревьях поиска. Алгоритм Шамоса — Хауи применяет этот принцип для решения задачи нахождения пересечения отрезков, как описано выш In computational geometry, the multiple line segment intersection problem supplies a list of line segments in the Euclidean plane and asks whether any two of them intersect (cross). Simple algorithms examine each pair of segments. However, if a large number of possibly intersecting segments are to be checked, this becomes increasingly inefficient since most pairs of segments are not close to one another in a typical input sequence. The most common, and more efficient, way to solve this problem for a high number of segments is to use a sweep line algorithm, where we imagine a line sliding across the line segments and we track which line segments it intersects at each point in time using a dynamic data structure based on binary search trees. The applies this principle to solve the line segm
dct:subject
dbc:Computational_geometry dbc:Geometric_algorithms dbc:Geometric_intersection
dbo:wikiPageID
3194098
dbo:wikiPageRevisionID
1061441057
dbo:wikiPageWikiLink
dbr:Ronald_L._Rivest dbc:Computational_geometry dbr:Thomas_H._Cormen dbc:Geometric_algorithms dbr:Intersection_(Euclidean_geometry) dbr:Bentley–Ottmann_algorithm dbr:CGAL dbr:Euclidean_plane dbr:Introduction_to_Algorithms dbr:Computational_geometry dbr:Shamos–Hoey_algorithm dbr:Binary_search_tree dbr:Clifford_Stein dbr:Washington_University_in_St._Louis dbc:Geometric_intersection dbr:Charles_E._Leiserson dbr:Sweep_line_algorithm dbr:Line_segment
dbo:wikiPageExternalLink
n4: n7:a05-_intersect-1.html n8: n17:computationalgeo00berg n18:Chapter_main.html n22:x06-sweepline.pdf n23:l4.html
owl:sameAs
n6:4qLKY dbpedia-es:Intersección_de_segmentos_de_recta dbpedia-ru:Задача_о_пересечении_отрезков dbpedia-uk:Перетин_відрізків wikidata:Q6553330
dbp:wikiPageUsesTemplate
dbt:Cite_book dbt:ISBN dbt:For_multi dbt:Reflist dbt:Algorithm-stub
dbo:abstract
En geometría computacional el problema de intersección de segmentos de recta está dado de la siguiente manera: dado un conjunto de n segmentos en el plano euclidiano se deben reportar todos los puntos de intersección en todo el conjunto . Mucha de la motivación para el estudio de los problemas de intersección recae en el simple hecho de que dos cuerpos no pueden ocupar el mismo lugar. La importancia de estudiar y diseñar algoritmos eficientes para detectar intersecciones está dada por la ambición de la industria, una imagen complicada puede contener cientos de miles de vectores. Una base de datos puede contener más de un millón de elementos, un circuito integrado puede contener millones de componentes; en estos casos tener un algoritmo inclusive de complejidad cuadrática son inaceptables. En geometría existen problemas los cuales puede ser resueltos mediante la solución del problema de intersección de segmentos como pueden ser el decidir cuando un polígono es simple o no. Un primer intento en resolver este problema está dado por lo siguiente: tomar todas las parejas de segmentos y ver si se intersecan. Este método es de orden (se dice que este algoritmo usa fuerza bruta, pues prueba todas las opciones posibles). A primera instancia es un algoritmo óptimo; sin embargo, es de orden , es decir, aun si no se presenta alguna intersección el algoritmo toma tiempo cuadrático. Es necesario un algoritmo "output sensitive" (sensible a la salida) para reducir este tiempo a algo cercano a ​ Задача о пересечении отрезков заключается в определении, пересекаются ли какие-либо два отрезка из заданного списка на плоскости. Простые алгоритмы проверяют каждую пару отрезков. Однако если нужно проверить большое число отрезков на пересечение, задача становится возрастающе неэффективной, поскольку большинство пар отрезков при обычном вводе не лежат близко друг от друга. Наиболее общий и более эффективный путь решения этой задачи для большого числа отрезков заключается в использовании алгоритма заметающей прямой, в котором мы воображаем себе прямую, проходящую через отрезки, и отслеживаем пересечения отрезков с помощью структуры данных, основанной на двоичных деревьях поиска. Алгоритм Шамоса — Хауи применяет этот принцип для решения задачи нахождения пересечения отрезков, как описано выше. Алгоритм Бентли — Оттманна работает по тому же принципу и находит список всех пересечений за логарифмическое время на одно пересечение. В обчислювальній геометрії, задача про перетин відрізків для заданого списку відрізоків на евклідовій площині з'ясовує чи знайдеться серед них пара відрізків, які будуть перетинатися. Примітивний алгоритм, який вирішує цю задачу, може перевіряти кожну пару відрізків на перетин. Швидкість такого алгоритму буде квадратичною для відрізків. Тому, коли потрібно перевірити дуже велику кількість відрізків на перетин, цей алгоритм стає все більш неефективним, оскільки більшість пар відрізків не є близькими один до одного для довільної послідовності відрізків. Найпоширеніший і більш ефективний спосіб розв'язати цю задачу для великої кількості відрізків — це використовувати метод замітання прямою, в якому пряма просувається по впорядкованій послідовності відрізків, а ми перевіряємо на перетин ті відрізки, які пряма перетинає в кожен момент часу в динамічній структурі даних побудованій на основі бінарного дерева пошуку. застосовує цей принцип для розв'язання задачи виявлення перетину відрізків, як зазначено вище, для визначення того, чи має множина відрізків перетин. Алгоритм Бентлі — Оттманна працює за тим же принципом для того, щоб перелічити всі перетини за логарифмічний час. In computational geometry, the multiple line segment intersection problem supplies a list of line segments in the Euclidean plane and asks whether any two of them intersect (cross). Simple algorithms examine each pair of segments. However, if a large number of possibly intersecting segments are to be checked, this becomes increasingly inefficient since most pairs of segments are not close to one another in a typical input sequence. The most common, and more efficient, way to solve this problem for a high number of segments is to use a sweep line algorithm, where we imagine a line sliding across the line segments and we track which line segments it intersects at each point in time using a dynamic data structure based on binary search trees. The applies this principle to solve the line segment intersection detection problem, as stated above, of determining whether or not a set of line segments has an intersection; the Bentley–Ottmann algorithm works by the same principle to list all intersections in logarithmic time per intersection.
prov:wasDerivedFrom
wikipedia-en:Multiple_line_segment_intersection?oldid=1061441057&ns=0
dbo:wikiPageLength
3519
foaf:isPrimaryTopicOf
wikipedia-en:Multiple_line_segment_intersection
Subject Item
dbr:Intersection_of_line_segments
dbo:wikiPageWikiLink
dbr:Multiple_line_segment_intersection
dbo:wikiPageRedirects
dbr:Multiple_line_segment_intersection
Subject Item
dbr:Line_intersection_problem
dbo:wikiPageWikiLink
dbr:Multiple_line_segment_intersection
dbo:wikiPageRedirects
dbr:Multiple_line_segment_intersection
Subject Item
dbr:Line_segment_intersection_problem
dbo:wikiPageWikiLink
dbr:Multiple_line_segment_intersection
dbo:wikiPageRedirects
dbr:Multiple_line_segment_intersection
Subject Item
wikipedia-en:Multiple_line_segment_intersection
foaf:primaryTopic
dbr:Multiple_line_segment_intersection