Pull to refresh

Точное вычисление геометрических предикатов

Programming *Mathematics *
Sandbox
Доброго вам дня, коллеги. Предлагаю вам прочитать статью о базовом аспекте вычислительной геометрии — точном вычислении предикатов.

Возможно, многие из вас сталкивались со «странным» поведением реализаций алгоритмов вычгеома: падениями и некорректными результатами. В общем, ничего удивительного в этих странностях нет — это издержки переноса непрерывной геометрии в суровые дискретные реалии арифметики с плавающей точкой. Рискну предположить, что кто-то из вас, отлаживая свои алгоритмы, решал подобные проблемы, подбирая магические константы. Скорее всего, если этот способ и приводил к результату, то, вероятно, к временному.

В этой статье я расскажу, как избавиться от недостатков вычислений с плавающей точкой практически без ущерба для эффективности. План статьи:
  • геометрический предикат «поворот»;
  • противоречивость «наивной» реализации поворота;
  • применение интервальной арифметики для упрощения расчета предикатов;
  • длинная арифметика и несколько альтернативных способов вычислений предикатов;
  • расчет погрешности вычисления поворота в числах с плавающей точкой.

Итак, если вы хотите знать, почему вычислительная геометрия не является «наукой о подборе эпсилонов» и как можно корректно и эффективно реализовать геометрический алгоритм, жмите
Читать дальше →
Total votes 51: ↑50 and ↓1 +49
Views 8.5K
Comments 14

Локализация точки в выпуклом многоугольнике

Algorithms *Mathematics *
Tutorial
Листая страницы хаба «Алгоритмы», наткнулся на топик, посвященный решению задачи локализации точки в многоугольнике: задан многоугольник (замкнутая ломаная линия без самопересечений), требуется определить — находится ли заданная точка A внутри этого многоугольника или нет. В одном из последних комментариев к топику было высказано недоумение, какое отношение такая чисто математическая задача имеет к теории алгоритмов. Имеет-имеет, причем самое непосредственное. Задача локализации является классической задачей вычислительной геометрии (не путать с компьютерной графикой). В качестве разминки предлагается взглянуть на картинку справа, на которой изображен многоугольник типа кривой Пеано (источник [1]), и попытаться ответить на вопрос — красная точка ты видишь суслика? и я не вижу, а он есть! находится внутри или снаружи многоугольника? А ниже мы (исключительно в образовательных целях) рассмотрим простую вариацию данной задачи, когда заданный многоугольник является выпуклым.
Читать дальше →
Total votes 83: ↑81 and ↓2 +79
Views 42K
Comments 46

Построение минимальных выпуклых оболочек

Algorithms *Mathematics *
Tutorial

Проведя небольшое научное исследование (проще говоря, выполнив поиск на сайте), обнаружил, что на хабре имеется всего две статьи с тегом вычислительная геометрия, причем одна из них оказалась моей. Т.к. в последнее время я несколько заинтересовался этой тематикой, то решил продолжить тему алгоритмической геометрии рассмотрением задачи построения так называемых минимальных выпуклых оболочек. Хотя рисунок справа и дает проницательному хаброчитателю исчерпывающее объяснение того, что это такое, тем не менее под катом будут даны чуть более формальные определения и описаны два классических алгоритма построения минимальных выпуклых оболочек.
Читать дальше →
Total votes 99: ↑94 and ↓5 +89
Views 113K
Comments 56

Анонс летней школы «Алгоритмы анализа, изменения и сравнения 3D полигональных моделей»

Programming *C++ *
3D модели, медицина и будущее: появление доступных цифровых стереокамер и алгоритмов трехмерной реконструкции по стереоснимкам открывают новые возможности применения построения 3D моделирования в медицине.
Цель школы:
  • Исследование и реализовать алгоритмы вычислителньой геометрии для анализа поверхностей и изменения формы 3D моделей
  • Web-based платформа для визуаилазации и хранения 3D моделей
  • Высоконагрузочная система рассчетов для построения 3D модели тела

Инструменты:
  • С++, OpenCV, PCL, WxWidgets, Ogre3d
  • Javascript, HTML 5.0, Chromium, WebGL, Alternativa3d/Away3d
  • Microsoft Azure, Redis, no-SQL db’s

Условия школы:
  • Школа длится с 1 июля и до 10го августа в помещении БИ «Ингрия», г.Санкт-Петербург
  • Стипендия 5 000 руб участникам школы и до 10 000 руб отличившимся студентам
  • Производится конкурсный отбор в июне: опыт программирования на С++, Javascript, знание вычислительной геометрии и численных методов.

Организаторы летней школы:
Читать дальше →
Total votes 20: ↑18 and ↓2 +16
Views 2K
Comments 8

Вычислительная геометрия, или как я стал заниматься олимпиадным программированием.Часть 1

Algorithms *Mathematics *
Здравствуйте, уважаемые хабравчане! Это моя вторая статья, и мне хотелось бы поговорить о вычислительной геометрии.

Немного истории


Я являюсь студентом уже 4 курса математического факультета, и до того как я начал заниматься программированием, я считал себя математиком на 100 процентов.

В конце первого курса мой преподаватель по информатике, который занимается олимпиадным программированием, обратил на меня внимание. Им как раз не хватало одного математика в команду. Так потихоньку меня начали приучать к олимпиадному программированию. Скажу честно, для меня это было очень сложно: для человека, который узнал слово Delphi на первом курсе. Однако мой преподаватель оказался очень грамотным специалистом и нашел хороший подход ко мне. Он начал давать мне математические задачи, который я сначала решал чисто математически, а уже потом писал код (с грехом пополам).

Мне очень нравится подход моего преподавателя: «разберись с этой темой, а потом расскажи нам, да так чтоб мы все поняли».

Итак, первой на самом деле важной задачей, с которой мне поручили разобраться, было именно вычислительная геометрия, необходимо было разобраться в типичных задач этого раздела информатики. И я решил подойти к этой задаче со всей ответственностью.

Я помню, как долго мучился с этими задачами, чтобы они прошли все тесты на сайте informatics.mccme. Зато теперь я очень рад, что прошел через все испытания и знаю, что же такое задачи вычислительной геометрии.
Читать дальше →
Total votes 83: ↑72 and ↓11 +61
Views 116K
Comments 40

Вычислительная геометрия, или как я стал заниматься олимпиадным программированием. Часть 2

Algorithms *Mathematics *

Вступление


Это вторая часть моей статьи посвящена вычислительной геометрии. Думаю, эта статья будет интереснее предыдущей, поскольку задачки будут чуть сложнее.

Начнем с взаимного расположения точки относительно прямой, луча и отрезка.
Читать дальше →
Total votes 39: ↑31 and ↓8 +23
Views 125K
Comments 27

Проект «робот-грузчик»: определение собственного местоположения

Programming *Algorithms *
Tutorial
У моего давнего британского партнёра (именно для него два года назад писалось «Распознавание почтовых адресов») появилась новая идея по оптимизации бизнес-процессов: коробки по складу должны возить роботы, а грузчики — только перекладывать товары с робота на полку и обратно. Смысл, естественно, не в том, чтобы за каждым роботом по пятам шёл грузчик, и принимался за погрузку-разгрузку, как только робот остановится — а чтобы роботов было намного больше, чем грузчиков, и чтобы роботы большую часть времени стояли в конечной точке своего маршрута, ожидая погрузки. Тогда грузчик будет лишь переходить от одного робота к следующему, нагружая каждый, и не будет тратить рабочее время на переноску товаров.

Предыстория


В прошлом году мы экспериментировали с платформой самоходного пылесоса Roomba. Новенький пылесос обошёлся нам около £300 (подержанный можно найти за £100 и даже дешевле), и в его состав входят два электропривода на колёса, два датчика касания спереди, инфракрасный датчик снизу (для обнаружения ступенек) и сверху (для поиска зарадной станции). Точный перечень датчиков зависит от модели: в протоколе предусмотрено до четырёх инфракрасных датчиков снизу, каждый из которых возвращает один бит («пол виден/не виден»). В любом случае, никаких дальномеров: все имеющиеся датчики однобитные. Кроме того, никаких «программируемых ардуин» в Roomba нет, и чтобы им управлять, нужно установить сверху лаптоп (или ардуину) и общаться с роботом по RS-232. Поигравшись с пылесосом вдоволь, мы так и оставили его пылиться на одной из полок склада.

В этом году мы решили попробовать Microsoft Robotics Development Studio (MRDS), для продвижения которого Microsoft сформулировала спецификацию «MRDS Reference Platform» — набор оборудования и протокол управления «стандартным» роботом. Эта спецификация позволила бы роботолюбам создавать совместимых роботов и переносить между ними программы. По сравнению с аппаратным оснащением пылесоса, Reference Platform намного сложнее и мощнее: в спецификацию включён Kinect, три ИК-дальномера и два ультразвуковых, а также датчики вращения колёс (encoders). Реализацию MRDS RP пока что предлагает только фирма Parallax под названием Eddie (порядка £1000, не включая Kinect). Необычайное сходство Eddie с фотографиями робота-прототипа в спецификации MRDS RP наводит на мысли, что спецификация создавалась в тесном сотрудничестве с Parallax, иначе говоря — Parallax удалось добиться, что Microsoft приняли их платформу за эталонную.

Кроме разнообразия датчиков, Eddie обладает механически впечатляющей платформой (заявленная грузоподъёмность 20кг, а мощности моторов достаточно, чтобы толкать впереди себя складской погрузчик) и программируемым контроллером Parallax Propeller, т.е. критические куски кода можно зашить непосредственно в робота, а не только командовать им с компа.
Читать дальше →
Total votes 12: ↑10 and ↓2 +8
Views 17K
Comments 23

Проект «робот-грузчик»: определение ориентации

Algorithms *Image processing *
Месяц назад я писал об определении моим роботом-грузчиком собственного положения. (Жаль, ту статью я запостил в неудачное время в ночь на субботу, так что её мало кто увидел.) Как я отметил, показания колёсных датчиков позволяют роботу определять своё положение достаточно точно — медленно накапливающаяся ошибка корректируется, как только робот сканирует баркод на любой из полок склада. С другой стороны, накапливающуюся ошибку направления корректировать было нечем.

Я обсудил свои затруднения с девушкой-гуманитарием, и спросил, какие ей известны способы ориентации в пространстве. По её словам, в Лондонском музее науки она застала экспозицию, посвящённую ориентации муравьёв по виду вертикально вверх над головой. Посетителям предлагалось взять зеркало и идти по комнате, разглядывая в это зеркало узоры на потолке и ориентируясь лишь по ним. (Карта потолка прилагалась.)

Я решил проверить: что видит на потолке склада мой робот?

Читать дальше →
Total votes 51: ↑47 and ↓4 +43
Views 17K
Comments 26

Задача об определении принадлежности точки многоугольнику

Lumber room
Sandbox
Здравствуйте, уважаемые хабравчане!
В процессе разработки приложения под Android, которое предполагает взаимодействие пользователя с графическими примитивами (точками, линиями, эллипсами, прямоугольниками и т.д.), возникла довольно неприятная ситуация: пользователь может задать произвольный многоугольник и сделать его неактивным, однако чтобы в будущем была возможность активировать данный многоугольник и продолжить с ним работь (например, переместить в другое место или добавить/удалить вершины) необходимо для неактивного объекта определить, коснулся ли пользователь данного объекта, т.е. потребовалось решить вопрос о принадлежности точки многоугольнику.

Данная задача широко известна в вычислительной геометриии и я предлагаю вашему вниманию результаты моего исследования данной темы.
Читать дальше →
Total votes 42: ↑35 and ↓7 +28
Views 8.4K
Comments 13

Motion planning: граф видимости, дорожные карты

Game development *Algorithms *Mathematics *
Sandbox

Всем добрый день. В этой статье я бы хотел рассказать про пару алгоритмов, относящихся к вычислительной геометрии, которые, в настоящее время, широко применяются при разработке игр. Если Вы хотя бы раз программировали игру, в которой есть передвигающийся по локации персонаж(и), Вам приходилось решать задачу поиска пути. Об одном из подходов к решению этой задачи и я хочу рассказать.
Читать дальше
Total votes 55: ↑55 and ↓0 +55
Views 25K
Comments 15

Ошибка в формуле проверки условия Делоне

Programming *Image processing *Mathematics *
Sandbox

Введение


Ранним воскресным утром я уже третий день сидел за отладкой программы для триангуляции результата лазерного сканирования. Лазерный скан представляет из себя набор трехмерных точек. В результате работы программы нужно объединить точки в непересекающиеся полигоны, таким образом создав модель поверхности. Функцию за функцией я пересчитывал на листочке и, наконец, добрался до функции проверки выполнения условия Делоне. По всей видимости, ошибка затаилась где-то в ней. При детальном разборе оказалось, что формула, указанная в огромном количестве книг про триангуляцию Делоне, не всегда дает верный результат. Подробности под катом.


Читать дальше →
Total votes 36: ↑31 and ↓5 +26
Views 23K
Comments 23

Диаграмма Вороного и её применения

C++ *Algorithms *
Sandbox
Доброго всем времени суток, уважаемые посетители сайта Хабрахабр. В данной статье я бы хотел рассказать вам о том, что такое диаграмма Вороного (изображена на картинке ниже), о различных алгоритмах её построения (за , — пересечение полуплоскостей, — алгоритм Форчуна) и некоторых тонкостях реализации (на языке C++).



Также будет рассмотрено много интересных применений диаграммы и несколько любопытных фактов о ней. Будет интересно!
Читать дальше →
Total votes 92: ↑89 and ↓3 +86
Views 97K
Comments 49

10 лет Computer Science клубу

Образовательные проекты JetBrains corporate blog C++ *Algorithms *Mathematics *Kotlin *


В этом году Computer Science клубу в Санкт-Петербурге исполняется 10 лет. С 2007 года в клубе проходят открытые лекции и курсы, где любой желающий может познакомиться с классическими результатами, современным положением дел и открытыми задачами в различных областях computer science. Вход на все лекции свободный, регистрация не требуется. Слайды и видеозаписи всех прошедших лекций доступны с сайта клуба.


Поздравить клуб с юбилеем приедут сотрудники следующих организаций: Академический университет, Математический институт Стеклова в Санкт-Петербурге, Санкт-Петербургский государственный университет, Яндекс, JetBrains, Montpellier University, Northwestern University, Toyota Technological Institute at Chicago, University of Bergen, University of California at San Diego, Yahoo Research. Они прочитают мини-курсы по следующим темам.


Читать дальше →
Total votes 16: ↑16 and ↓0 +16
Views 4K
Comments 2

Использование библиотеки OpenCV для распознавания эллиптических дуг на 2D сечениях 3D облаков точек

Image processing *
Sandbox
Tutorial

В связи с все более широким распространением доступных лазерных сканеров (лидаров), способных получать 3D облака точек (3dОТ) и все более широким применением этой технологии в различных областях (от машиностроения до безопасности, от нефтяной промышленности до архитектуры), оживился интерес к алгоритмам обработки облаков точек.

Одно из востребованных применений 3dОТ в промышленности — это создание конструкторской документации на только возводимое, старое или переделанное оборудование, которое обычно представляет из себя трубопроводы и другие конструкции цилиндрической геометрии.

Для детектирования геометрических примитивов в 3dОТ обычно применяются специализированные 3D библиотеки, например Microsoft PCL. У подхода с использованием готовых библиотек наряду с достоинствами есть и недостатки. Например, трудно включить их в уже существующие кадовские схемы обработки, которые обычно имеют 2D размерность.

Рассмотрим, как можно было бы обрабатывать 3dОТ, например насосной станции, начав с 2D сечений и используя весь арсенал 2D обработки, который есть в надежных и оптимизированных библиотеках обработки изображений, например OpenCV.


Рисунок 1. 3D ОТ модель насосной станции

Читать дальше →
Total votes 8: ↑8 and ↓0 +8
Views 2.4K
Comments 0

Обнаружение столкновений и теорема о разделяющей оси

Programming *Game development *Mathematics *
Sandbox
Tutorial
В наше время компьютеры представляют собой мощные вычислительные машины,
способные выполнять миллионы операций в секунду. И естественно не обойтись без симуляции реального или игрового мира. Одна из задач компьютерного моделирования и симуляции состоит в определении столкновения двух объектов, одно из решений которой реализуется теоремой о разделяющей оси.


Читать дальше →
Total votes 11: ↑11 and ↓0 +11
Views 6.7K
Comments 18

Построение выпуклой 3D оболочки

Programming *C++ *Algorithms *
Tutorial

Что? Зачем?


Всем привет!


Я хотел бы рассмотреть задачу вычислительной геометрии, а именно построение выпуклой 3D оболочки. Как мне кажется, это и не самый сложный, и не самый простой алгоритм, который было бы очень интересно и полезно разобрать.


Если Вы никогда не сталкивались с такой задачей, думаю, Вам будет интересно узнать о ней, посмотреть что это такое.


Если Вы только что-то слышали о выпуклых оболочках, Вы сможете поподробнее разузнать о них.


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


Читать дальше →
Total votes 14: ↑14 and ↓0 +14
Views 5.9K
Comments 14