| 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 (es)
- 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. (en)
- Задача о пересечении отрезков заключается в определении, пересекаются ли какие-либо два отрезка из заданного списка на плоскости. Простые алгоритмы проверяют каждую пару отрезков. Однако если нужно проверить большое число отрезков на пересечение, задача становится возрастающе неэффективной, поскольку большинство пар отрезков при обычном вводе не лежат близко друг от друга. Наиболее общий и более эффективный путь решения этой задачи для большого числа отрезков заключается в использовании алгоритма заметающей прямой, в котором мы воображаем себе прямую, проходящую через отрезки, и отслеживаем пересечения отрезков с помощью структуры данных, основанной на двоичных деревьях поиска. Алгоритм Шамоса — Хауи применяет этот принцип для решения задачи нахождения пересечения отрезков, как описано выше. Алгоритм Бентли — Оттманна работает по тому же принципу и находит список всех пересечений за логарифмическое время на одно пересечение. (ru)
- В обчислювальній геометрії, задача про перетин відрізків для заданого списку відрізоків на евклідовій площині з'ясовує чи знайдеться серед них пара відрізків, які будуть перетинатися. Примітивний алгоритм, який вирішує цю задачу, може перевіряти кожну пару відрізків на перетин. Швидкість такого алгоритму буде квадратичною для відрізків. Тому, коли потрібно перевірити дуже велику кількість відрізків на перетин, цей алгоритм стає все більш неефективним, оскільки більшість пар відрізків не є близькими один до одного для довільної послідовності відрізків. Найпоширеніший і більш ефективний спосіб розв'язати цю задачу для великої кількості відрізків — це використовувати метод замітання прямою, в якому пряма просувається по впорядкованій послідовності відрізків, а ми перевіряємо на перетин ті відрізки, які пряма перетинає в кожен момент часу в динамічній структурі даних побудованій на основі бінарного дерева пошуку. застосовує цей принцип для розв'язання задачи виявлення перетину відрізків, як зазначено вище, для визначення того, чи має множина відрізків перетин. Алгоритм Бентлі — Оттманна працює за тим же принципом для того, щоб перелічити всі перетини за логарифмічний час. (uk)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3519 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| 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 . (es)
- 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 (en)
- Задача о пересечении отрезков заключается в определении, пересекаются ли какие-либо два отрезка из заданного списка на плоскости. Простые алгоритмы проверяют каждую пару отрезков. Однако если нужно проверить большое число отрезков на пересечение, задача становится возрастающе неэффективной, поскольку большинство пар отрезков при обычном вводе не лежат близко друг от друга. Наиболее общий и более эффективный путь решения этой задачи для большого числа отрезков заключается в использовании алгоритма заметающей прямой, в котором мы воображаем себе прямую, проходящую через отрезки, и отслеживаем пересечения отрезков с помощью структуры данных, основанной на двоичных деревьях поиска. Алгоритм Шамоса — Хауи применяет этот принцип для решения задачи нахождения пересечения отрезков, как описано выш (ru)
- В обчислювальній геометрії, задача про перетин відрізків для заданого списку відрізоків на евклідовій площині з'ясовує чи знайдеться серед них пара відрізків, які будуть перетинатися. Примітивний алгоритм, який вирішує цю задачу, може перевіряти кожну пару відрізків на перетин. Швидкість такого алгоритму буде квадратичною для відрізків. Тому, коли потрібно перевірити дуже велику кількість відрізків на перетин, цей алгоритм стає все більш неефективним, оскільки більшість пар відрізків не є близькими один до одного для довільної послідовності відрізків. Найпоширеніший і більш ефективний спосіб розв'язати цю задачу для великої кількості відрізків — це використовувати метод замітання прямою, в якому пряма просувається по впорядкованій послідовності відрізків, а ми перевіряємо на перетин ті в (uk)
|
| rdfs:label
|
- Intersección de segmentos de recta (es)
- Multiple line segment intersection (en)
- Задача о пересечении отрезков (ru)
- Перетин відрізків (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is rdfs:seeAlso
of | |
| is foaf:primaryTopic
of | |
