calc
Скелетонизация шрифтов (нахождение центральной линии изображения)
На языке C++ разработаны кроссплатформенные классы для получения средней линии символов (как растровых, так и True Type) шрифтов Unicode (решение т.н. задачи скелетонизации шрифта). Полученная в результате работы алгоритма 
средняя линия символа задается минимальным числом кривых Безье с заданной погрешностью. Подобные алгоритмы применяются при наложении визуальных эффектов на шрифты и при распознавании образов.
Полный демонстрационный пакет доступен здесь (skelet.zip). В этом пакете содержится демо-программа с графическим интерфейсом, основанная на разработанных классах, позволяющая получить среднюю линию для ряда символов различных языков. Программа работает с файлом шрифта напрямую, поэтому, если ей не удастся автоматически определить местонахождение файла ARIALUNI.TTF (unicode, около 23 Мб), этот файл необходмио поместить в каталог программы. Этот шрифт также включен в состав Windows XP, 2000 и новых версий MS Office.
Кроме того, возможно использование разработанных классов для создания приложения, работающего из командной строки, считывающиего данные из файла шрифта, и записывающего характеристики полученных кривых Безье в файл вывода. Такое приложение может быть легко создано как под Windows, так и под Unix.
Краткое описание алгоритма определения центральной линии символа, содержащегося в разработанных кроссплатформенных классах:
- получение статистики о битовом изображении;
- разрезание символа на части (для случаев, когда различные части символа имеют тонкие соединения, которые не должны отражаться на виде центральной линии символа);
- определение "базисных" точек (лежащих приблизительно в середине символа) на основе разновидности клеточного аппарата (с более сложными правилами, чем небезызвестная игра "жизнь" Конвея);
- просеивание "базисных" точек для удаления избыточной информации;
- получение полилинии, состоящей из большого числа коротких прямых диний, приблизительно описывающих центральную линию символа;
- замыкание открытых контуров в полилинии (если это необходимо для корректного построения центральной линии символа);
- удаление артефактных разветвлений на концах и пересечениях полилиний (вмесе с вызвавшими возникновение артефактов "базисными" точками);
- повторное получение полилинии на основе нового набора "базисных" точек;
- замыкание открытых контуров в новой полилинии;
- объединение полилиний в прямые линии в пределах допустимой погрешности (определение "прямых" участков центральной линии символа);
- анализ пересечений центральной в линии символа (для более плавного приближения кривыми Безье);
- удаление остаточных артефактных разветвлеий на концах центральной линии символа (без изменения состава "базисных" точек);
- анализ и корректировка углов поворота центральной линии символа (в случаях поворота линии на углы, отличные от 90 градусов) для получения более естественной и гладкой центральной линии символа;
- разделение точек пересечения центральной линии символа, если этого требует необходимая гладкость центральной линии;
- реструктуризация полученных результатов для ускорения работы аппроксимации центральной линии кривыми Безье 2-го и 3-го порядков;
- вычисление полилинии, состоящей из кривых Безье не выше 3-го порядка, на основе полученной ломаной полилинии и метода наименьших квадратов.
Для использования классов дополнительно должен быть разработан (зависящий от конкретной программной платформы) механизм для ввода стартовой информации и параметров алгоритма, а также для вывода итоговых данных.
Класс С++ для выполнения матрично-векторных операций
На C++ реализован класс Matrix, содержащий основные функции работы с матрицами:
- выделение отдельных строк и столбцов, добавление и удаление блоков, транспонирование, нормирование, изменение размерности;
- умножение, сложение, вычитание, возведение в степень;
- вычиление определителя матрицы, ее нормы;
- получение обратной матрицы;
- преобразование к треугольной форме (с использованием метода элементарных преобразований с выделением ведущего элемента);
- решение систем линейных уравнений с использованием метода Гаусса, метода Зейделя или метода отражений;
- и многое другое.
Исходный код класса Matrix можно скачать здесь (zip-архив).
Реализация прямого симплекс-метода решения задач линейного программирования
Реализован прямой симплекс-метод Дж. Данцига с выбором ведущего элемента. Метод применяется при решения задач линейного программирования (например в нашем программном продукте "Расчет оптимального рациона"). Программная реализация основана на классе Matrix, описанном выше. Исходный код класса Matrix также включен в архив проекта.
- Zip-архив с программой (проект Borland С++ Builder 5.0): WinSMX_for_B5.zip (284 Кб)
Примечание: smx.exe из архива WinSMX_B5.zip требует для запуска наличие библиотек от Borland или установленного "Borland С++ Builder 5.0" (при компиляции использовался режим "Build with runtime packages")
- Zip-архив с программой (проект Borland С++ Builder 6.0): WinSMX_for_B6.zip (652 Кб)
- Zip-архив с программой (только "smx.exe", документация и тестовые примеры): WinSMX_prg.zip (425 Кб)
Примечание: smx.exe из архива WinSMX_B6.zip и из WinSMX_prg.zip
может работать автономно.Примечание: в архивах тестовые примеры в подкаталоге "data", краткое описание - в подкаталоге "doc".