Обнаружение столкновений (collision detection) виртуальных объектов является довольно значимой частью для задач визуализации.

Не знаю, как вы, уважаемый читатель, а я всегда поражался контрасту между изяществом базовой идеи, заложенной в концепцию двоичных деревьев поиска, и сложностью реализации сбалансированных двоичных деревьев поиска (красно-черные деревья, АВЛ-деревья, декартовы деревья). Недавно, перелистывая в очередной раз Седжвика [1], нашел описание рандомизированных деревьев поиска (нашлась и оригинальная работа [2]) — настолько простое, что занимает оно всего треть страницы (вставка узлов, еще страница — удаление узлов). Кроме того, при ближайшем рассмотрении обнаружился дополнительный бонус в виде очень красивой реализации операции удаления узлов из дерева поиска. Далее вы найдете описание (с цветными картинками) рандомизированных деревьев поиска, реализация на С++, а также результаты небольшого авторского исследования сбалансированности описываемых деревьев.

Была цель создать приложение на mac, которое может распознавать текст кода с изображений и видео.

Хотелось сделать так, чтобы даже при большом объеме кода, текст распознавался менее, чем за секунду.

Проблема облегчается тем, что язык на котором пишут код всегда английский и ширина между всеми буквами одинаковая (моноширинный шрифт) — такие используются для программирования, и в этих шрифтах легко увидеть разницу между 1 и I, 0 и O и тд.

Если вкратце, то задача сводится к двум частям:

1. Нахождению самой буквы с ее границами

И с этим шикарно справился Vision, новый framework от Apple.

2. Распознавание буквы в заданных границах

Я решил пойти не хитрым способом и проверять определенные пиксели квадрата, в границах которого находится буквы (допустим: центр, углы, бока) и отталкиваясь от наличия или отсутствия там буквы, классифицировать что за буква.

Наглядный пример:




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