Список тем — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
===Устойчивая реализация алгоритмов вычислительной геометрии.===
 
===Устойчивая реализация алгоритмов вычислительной геометрии.===
 
* Как устроены числа с плавающей точкой?
 
* Как устроены числа с плавающей точкой?
* Расчет погрешности вычисления предиката (на примере вычисления предиката поворота).  
+
*: [[Представление_вещественных_чисел]]
Обратите внимание, что готовить эту тему следует по моей видеолекции, там я расписал вычисление погрешности гораздо аккуратнее.
+
*: [[Представление_чисел_с_плавающей_точкой]]
* Интервальная арифметика.Длинная арифметика. ESSA.
+
* Расчет погрешности вычисления предиката (на примере вычисления предиката поворота). Обратите внимание, что готовить эту тему следует по моей видеолекции, там я расписал вычисление погрешности гораздо аккуратнее.
 +
*: [http://compsciclub.ru/node/1563 презентация в csклубе]
 +
* Интервальная арифметика. Длинная арифметика. ESSA.
 +
*: [[Интервальная_арифметика]]
 +
*: {{TODO |t=по ESSA вообще ничего не нашел}}
 
* Adaptive precision арифметика.
 
* Adaptive precision арифметика.
 +
*: [[Adaptive_precision_arithmetic]]
 +
*: [http://www.cs.cmu.edu/~quake/robust.html статья Шевчука]
  
 
===Конфигурации пространства. Определение и построение.===
 
===Конфигурации пространства. Определение и построение.===

Версия 04:02, 25 января 2012

Устойчивая реализация алгоритмов вычислительной геометрии.

TODO: по ESSA вообще ничего не нашел

Конфигурации пространства. Определение и построение.

  • Предикат пересечения отрезков.
  • Пересечение множества отрезков (Bentley-Ottmann).
  • Представление конфигураций плоскости (DCEL). Конфигурация множества прямых на плоскости. Конфигурация множества отрезков на плоскости.

Конфигурации пространства. Локализация.

  • Локализация в выпуклом многоугольнике. Локализация в многоугольнике общего вида. Геометрический хеш.
  • Алгоритм Киркпатрика.
  • Трапецоидная карта.
  • Инкрементальная локализация на дереве отрезков.
  • Метод полос.

Выпуклые оболочки на плоскости.

  • Алгоритм Джарвиса.
  • Алгоритм Эндрюса-Грэма.
  • Выпуклая оболочка как аналог merge sort (слияние двух непересекающихся оболочек).
  • Выпуклая оболочка как аналог quick sort (без дополнительной памяти).

Типовые задачи

  • Расписать погрешность предиката (например, поворот отрезка и точки пересечения двух отрезков).
  • Пересечение множества окружностей разного радиуса.
  • Выпуклая оболочка множества окружностей одинакового радиуса.
  • Выпуклая оболочка множества окружностей разного радиуса.