Список тем — различия между версиями
(Новая страница: «===Устойчивая реализация алгоритмов вычислительной геометрии.=== * Как устроены числа с пла...») |
Proshev (обсуждение | вклад) |
||
| (не показано 10 промежуточных версий 3 участников) | |||
| Строка 1: | Строка 1: | ||
===Устойчивая реализация алгоритмов вычислительной геометрии.=== | ===Устойчивая реализация алгоритмов вычислительной геометрии.=== | ||
* Как устроены числа с плавающей точкой? | * Как устроены числа с плавающей точкой? | ||
| − | * Расчет погрешности вычисления предиката (на примере вычисления предиката поворота). | + | *: [[Представление_вещественных_чисел]] |
| − | Обратите внимание, что готовить эту тему следует по моей видеолекции, там я расписал вычисление погрешности гораздо аккуратнее. | + | *: [[Представление_чисел_с_плавающей_точкой]] |
| − | * Интервальная арифметика.Длинная арифметика. ESSA. | + | * Расчет погрешности вычисления предиката (на примере вычисления предиката поворота). Обратите внимание, что готовить эту тему следует по моей видеолекции, там я расписал вычисление погрешности гораздо аккуратнее. |
| + | *: [http://compsciclub.ru/node/1563 презентация в csклубе] | ||
| + | * Интервальная арифметика. Длинная арифметика. ESSA. | ||
| + | *: [[Интервальная_арифметика]] | ||
| + | *: {{TODO |t=по ESSA вообще ничего не нашел}} | ||
| + | :: - пожалуйста: [http://pages.cpsc.ucalgary.ca/~marina/papers/Segment_intersection.ps] | ||
* Adaptive precision арифметика. | * Adaptive precision арифметика. | ||
| + | *: [[Adaptive_precision_arithmetic]] | ||
| + | *: [http://www.cs.cmu.edu/~quake/robust.html статья Шевчука] | ||
===Конфигурации пространства. Определение и построение.=== | ===Конфигурации пространства. Определение и построение.=== | ||
* Предикат пересечения отрезков. | * Предикат пересечения отрезков. | ||
| + | *: [[Предикат_"левый_поворот"]] | ||
* Пересечение множества отрезков (Bentley-Ottmann). | * Пересечение множества отрезков (Bentley-Ottmann). | ||
| + | *: [[Алгоритм_Бентли-Оттмана]] | ||
* Представление конфигураций плоскости (DCEL). Конфигурация множества прямых на плоскости. Конфигурация множества отрезков на плоскости. | * Представление конфигураций плоскости (DCEL). Конфигурация множества прямых на плоскости. Конфигурация множества отрезков на плоскости. | ||
| + | *: [[Конфигурация]] | ||
===Конфигурации пространства. Локализация.=== | ===Конфигурации пространства. Локализация.=== | ||
* Локализация в выпуклом многоугольнике. Локализация в многоугольнике общего вида. Геометрический хеш. | * Локализация в выпуклом многоугольнике. Локализация в многоугольнике общего вида. Геометрический хеш. | ||
| + | *: [http://en.wikipedia.org/wiki/Geometric_hashing Wikipedia — Geometric hashing] — на лекции не был, посмотрите, мало ли это не то. | ||
* Алгоритм Киркпатрика. | * Алгоритм Киркпатрика. | ||
| + | *: | ||
| + | <s>[http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B8%D1%80%D0%BA%D0%BF%D0%B0%D1%82%D1%80%D0%B8%D0%BA%D0%B0 Википедия — Алгорити Киркпатика] — что это делает здесь, казалось бы, это надо в выпуклые оболочки.</s> кококо, это все-таки то самое, Препарата, Шамос, страница 75. Всем вычгеом. | ||
* Трапецоидная карта. | * Трапецоидная карта. | ||
| + | *: [http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2002/JukkaKaartinen/] | ||
* Инкрементальная локализация на дереве отрезков. | * Инкрементальная локализация на дереве отрезков. | ||
| + | :* Может, тут все-таки имелось в виду [http://en.wikipedia.org/wiki/Interval_tree дерево интервалов]? | ||
* Метод полос. | * Метод полос. | ||
| + | *: [http://en.wikipedia.org/wiki/Point_location Wikipedia — Point location] | ||
| + | ::tip: Это имеет отношение к персистентным деревьям. | ||
=== Выпуклые оболочки на плоскости. === | === Выпуклые оболочки на плоскости. === | ||
* Алгоритм Джарвиса. | * Алгоритм Джарвиса. | ||
| − | * Алгоритм Эндрюса- | + | *: [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B6%D0%B0%D1%80%D0%B2%D0%B8%D1%81%D0%B0] |
| + | * Алгоритм Эндрюса-Грэхема. | ||
| + | *: [http://nms.lcs.mit.edu/~aklmiu/6.838/convexhull/] | ||
* Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек). | * Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек). | ||
| + | *: [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B8%D1%80%D0%BA%D0%BF%D0%B0%D1%82%D1%80%D0%B8%D0%BA%D0%B0 этот вроде как раз подойдет] | ||
* Выпуклая оболочка как аналог quick sort (без дополнительной памяти). | * Выпуклая оболочка как аналог quick sort (без дополнительной памяти). | ||
| + | *: [http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/QuickHull.html] | ||
| + | |||
| + | === Типовые задачи === | ||
| + | |||
| + | * Расписать погрешность предиката (например, поворот отрезка и точки пересечения двух отрезков). | ||
| + | * Пересечение множества окружностей разного радиуса. | ||
| + | * Выпуклая оболочка множества окружностей одинакового радиуса. | ||
| + | * Выпуклая оболочка множества окружностей разного радиуса. | ||
| + | |||
| + | [[Категория: Вычислительная геометрия]] | ||
Версия 15:05, 16 июня 2012
Содержание
Устойчивая реализация алгоритмов вычислительной геометрии.
- Как устроены числа с плавающей точкой?
- Расчет погрешности вычисления предиката (на примере вычисления предиката поворота). Обратите внимание, что готовить эту тему следует по моей видеолекции, там я расписал вычисление погрешности гораздо аккуратнее.
- Интервальная арифметика. Длинная арифметика. ESSA.
TODO: по ESSA вообще ничего не нашел
- - пожалуйста: [1]
- Adaptive precision арифметика.
Конфигурации пространства. Определение и построение.
- Предикат пересечения отрезков.
- Пересечение множества отрезков (Bentley-Ottmann).
- Представление конфигураций плоскости (DCEL). Конфигурация множества прямых на плоскости. Конфигурация множества отрезков на плоскости.
Конфигурации пространства. Локализация.
- Локализация в выпуклом многоугольнике. Локализация в многоугольнике общего вида. Геометрический хеш.
- Wikipedia — Geometric hashing — на лекции не был, посмотрите, мало ли это не то.
- Алгоритм Киркпатрика.
Википедия — Алгорити Киркпатика — что это делает здесь, казалось бы, это надо в выпуклые оболочки. кококо, это все-таки то самое, Препарата, Шамос, страница 75. Всем вычгеом.
- Трапецоидная карта.
- Инкрементальная локализация на дереве отрезков.
- Может, тут все-таки имелось в виду дерево интервалов?
- Метод полос.
- tip: Это имеет отношение к персистентным деревьям.
Выпуклые оболочки на плоскости.
- Алгоритм Джарвиса.
- Алгоритм Эндрюса-Грэхема.
- Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).
- Выпуклая оболочка как аналог quick sort (без дополнительной памяти).
Типовые задачи
- Расписать погрешность предиката (например, поворот отрезка и точки пересечения двух отрезков).
- Пересечение множества окружностей разного радиуса.
- Выпуклая оболочка множества окружностей одинакового радиуса.
- Выпуклая оболочка множества окружностей разного радиуса.
