Метка «вычислительная геометрия»

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

Данная задача широко известна в вычислительной геометрии, однако в русскоязычной литературе практически не описана. Чтобы исправить данное недоразумение предлагаю вашему вниманию результаты моего исследования данной темы.
Читать полностью »

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

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

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

Читать полностью »

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

Предыстория

Проект «робот грузчик»: определение собственного местоположенияВ прошлом году мы экспериментировали с платформой самоходного пылесоса 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, т.е. критические куски кода можно зашить непосредственно в робота, а не только командовать им с компа.
Читать полностью »

Вступление

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

Начнем с взаимного расположения точки относительно прямой, луча и отрезка.
Читать полностью »

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

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

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

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

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

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

Я помню, как долго мучился с этими задачами, чтобы они прошли все тесты на сайте informatics.mccme. Зато теперь я очень рад, что прошел через все испытания и знаю, что же такое задачи вычислительной геометрии.
Читать полностью »

3D модели, медицина и будущее: появление доступных цифровых стереокамер и алгоритмов трехмерной реконструкции по стереоснимкам открывают новые возможности применения построения 3D моделирования в медицине.
Цель школы:

  • Исследование и реализовать алгоритмы вычислителньой геометрии для анализа поверхностей и изменения формы 3D моделей
  • Web-based платформа для визуаилазации и хранения 3D моделей
  • Высоконагрузочная система рассчетов для построения 3D модели тела

Инструменты:

  • С++, OpenCV, PCL, WxWidgets
  • Javascript, HTML 5.0, Chromium, WebGL, Alternativa3d/Away3d
  • Microsoft Azure, Redis, no-SQL db’s

Условия школы:

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

Организаторы летней школы:
Читать полностью »

Локализация точки в выпуклом многоугольнике Листая страницы хаба «Алгоритмы», наткнулся на топик, посвященный решению задачи локализации точки в многоугольнике: задан многоугольник (замкнутая ломаная линия без самопересечений), требуется определить — находится ли заданная точка A внутри этого многоугольника или нет. В одном из последних комментариев к топику было высказано недоумение, какое отношение такая чисто математическая задача имеет к теории алгоритмов. Имеет-имеет, причем самое непосредственное. Задача локализации является классической задачей вычислительной геометрии (не путать с компьютерной графикой). В качестве разминки предлагается взглянуть на картинку справа, на которой изображен многоугольник типа кривой Пеано (источник [1]), и попытаться ответить на вопрос — красная точка ты видишь суслика? и я не вижу, а он есть! находится внутри или снаружи многоугольника? А ниже мы (исключительно в образовательных целях) рассмотрим простую вариацию данной задачи, когда заданный многоугольник является выпуклым.
Читать полностью »