|
Вычислительная геометрия
Реализация основных алгоритмов по планиметрии.
Все реализации протестированы (большинство было отлажено на сайте http://informatics.mccme.ru/moodle/).
Полная реализация на C++
Структуры данных
Точки
Расстояние между двумя точками
Принадлежность точки прямоугольнику
Взаимное расположение двух точек
Полярный угол точки
Полярное расстояние
Деление отрезка заданном отношении
Поворот точки против часовой стрелки вокруг оси
Поворот точки против часовой стрелки вокруг другой точки
Добавление вектора к точке
Прямые
Уравнение прямой, проходящей через две точки
Ориентация точки относительно прямой
Взаимное расположение двух прямых
Перпендикуляр к прямой
Пересечение прямых
Взаимное расположение прямых и точек (проекция, расстояния)
Отрезки
Принадлежность точки отрезку
Пересекаются ли отрезки
Точка пересечения отрезков
Расстояние от точки до отрезка
Пересечение отрезка с прямой
Треугольники
Ориентированная площадь треугольника
Угол между тремя точками - через произведение векторов
Положение точки относительно вектора в обходе против часовой стрелки
Высота, медиана и биссектриса угла
Вписанная в треугольник окружность
Описанная около треугольника окружность
Окружности
Положение точки относительно окружности
Минимальная окружность, покрывающая множество точек O(N4)
Минимальная окружность, покрывающая множество точек O(NlogN)
Пересечение прямой с окружностью
Пересечение окружностей
Касательная (решение 1 :: поворот точек)
Касательная (решение 2 :: пересечение окружностей)
Касательные к двум окружностям
Лучи
Принадлежность точки лучу
Расстояние от точки до луча
Пересечение луча с окружностью
Луч, не пересекающий ни одну из заданных окружностей
Выпуклая оболочка
Алгоритм Джарвиса O(nk)
Алгоритм Грэхема O(nlogn)
Триангуляция
Алгоритм Ван Гога
Рекурсивный алгоритм
Триангуляция с минимальной суммой длин проведённых хорд
Триангуляция многоугольника на минимальное количество треугольников
Многоугольники
Принадлежность точки многоугольнику
Ориентированная площадь многоугольника
Периметр многоугольника
Количество точек на границе многоугольника
Количество точек внутри многоугольника
Проверка выпуклости многоугольника
Является ли отрезок внутренней диагональю многоугольника
Разрезание многоугольника внутренней диагональю
Расположение многоугольника относительно прямой
Разрезание выпуклого многоугольника прямой
Разрезание выпуклого многоугольника в отношении площадей m:n
Разрезание выпуклого многоугольника на k равных частей
23.06.2007, 15:25
По всем вопросам обращаться: rumterg@gmail.com