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

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 9 промежуточных версий 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]
  
 
=== Типовые задачи ===
 
=== Типовые задачи ===
Строка 32: Строка 53:
 
* Выпуклая оболочка множества окружностей одинакового радиуса.
 
* Выпуклая оболочка множества окружностей одинакового радиуса.
 
* Выпуклая оболочка множества окружностей разного радиуса.
 
* Выпуклая оболочка множества окружностей разного радиуса.
 +
 +
[[Категория: Вычислительная геометрия]]

Текущая версия на 15:05, 16 июня 2012

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

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

- пожалуйста: [1]

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

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

  • Локализация в выпуклом многоугольнике. Локализация в многоугольнике общего вида. Геометрический хеш.
    Wikipedia — Geometric hashing — на лекции не был, посмотрите, мало ли это не то.
  • Алгоритм Киркпатрика.

Википедия — Алгорити Киркпатика — что это делает здесь, казалось бы, это надо в выпуклые оболочки. кококо, это все-таки то самое, Препарата, Шамос, страница 75. Всем вычгеом.

  • Трапецоидная карта.
    [2]
  • Инкрементальная локализация на дереве отрезков.
tip: Это имеет отношение к персистентным деревьям.

Выпуклые оболочки на плоскости.[править]

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

Типовые задачи[править]

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