Аннотация. В статье рассмотрены новые и уже известные методы для обнаружения особых точек на плоской кривой и подтверждения гладкости этой кривой. Наш подход основан на построении касательных прямых к данной кривой, проходящих через выделенные точки вне кривой. В особой точке кривой пересекается много таких прямых, что позволяет быстро определить особую точку на выпуклой кривой. В общем случае число вещественных касательных зависит от выделенной точки на плоскости. Однако существование хотя бы одной особой точки у алгебраической кривой накладывает ограничение на алгебраическое уравнение, определяющее совокупность касательных, проходящих через выделенную точку плоскости. Так проверка гладкости плоской алгебраической кривой сводится к проверке несовместности системы линейных уравнений. С другой стороны, эти касательные можно строить графически. Так построение вещественных касательных позволяет доказать отсутствие не только вещественных, но и комплексных особых точек на проективной кривой, которые в любом случае не принадлежали бы вещественной плоскости. Это показывает эффективность графических методов для решения задач комплексной геометрии. Метод допускает непосредственное обобщение на многомерный случай, важный для решения комбинаторных задач. В этом случае надо рассматривать не отдельные касательные прямые, а конусы с вершинами в различных точках пространства. Поиск особых точек важен и для решения задач машинного зрения, в том числе для обнаружения угла у препятствия по последовательности кадров с одной камеры на движущемся транспортном средстве.
плоская кривая, особая точка, касательная, выпуклая область, распознавание образов, машинное зрение.
Введение
Если плоская кривая C задана известным алгебраическим уравнением, то поиск особой точки сводится к решению системы алгебраических уравнений от двух переменных. Исключение одной переменной сводит решение этой системы к поиску корней многочлена от одной переменной. Для аппроксимации корней известны эффективные алгоритмы [14]. Исключение одной из двух переменных легко выполняется алгоритмами, основанными на вычислении базиса Гребнера [25] и реализованными во многих пакетах программ для символьных вычислений [13], например, можно использовать облачный сервис MathPartner [10]. Также известны другие методы, обзор которых сделан в работе [27].
1. Гирш А.Г. Мнимости в геометрии [Текст] / А.Г. Гирш // Геометрия и графика. - 2014. - Т. 2. - № 2. - C. 3-8. - DOI:https://doi.org/10.12737/5583.
2. Гирш А.Г. Огибающая семейства линий [Текст] / А.Г. Гирш // Геометрия и графика. - 2016. - Т. 4. - № 4. - C. 14-18. - DOI:https://doi.org/10.12737/22839.
3. Гирш А.Г. Фокусы алгебраических кривых [Текст] / А.Г. Гирш // Геометрия и графика. - 2015. - Т. 3. - № 3. - C. 4-17. - DOI:https://doi.org/10.12737/14415.
4. Джанабаев Ж.Ж. Об алгоритме графического построения геодезической линии на линейчатой поверхности [Текст] / Ж.Ж. Джанабаев, Н.С. Умбетов // Геометрия и графика. - 2015. - Т. 3. - № 4. - C. 15-18. - DOI:https://doi.org/10.12737/17346.
5. Ершов Е.И. Алгоритмы стереозрения на основе параллакса движения монокулярной камеры бокового обзора [Текст] / Е.И. Ершов, В.Н. Карнаухов, М.Г. Мозеров // Информационные процессы. - 2015. - Т. 15. - № 4. - С. 414-427.
6. Заева К.А. Метод маршрутизации с препятствиями на основе параллельных вычислений [Текст] / К.А. Заева, А.Б. Семенов // Вестник Тверского государственного университета. Серия «Прикладная математика». - 2016. - № 3. - С. 85-95.
7. Иванов Г.С. О задачах начертательной геометрии с мнимыми решениями [Текст] / Г.С. Иванов, И.М. Дмитриева // Геометрия и графика. - 2015. - Т. 3. - № 2. - C. 3-8. - DOI:https://doi.org/10.12737/12163.
8. Иванов Г.С. Принцип двойственности - теоретическая база взаимосвязи синтетических и аналитических способов решения геометрических задач [Текст] / Г.С. Иванов, И.М. Дмитриева // Геометрия и графика. - 2016. - Т. 4. - № 3. - C. 3-10. - DOI:https://doi.org/10.12737/21528.
9. Ивашов Д.С. Об алгоритме факторизации полиномов многих переменных [Текст] / Д.С. Ивашов // Вестник Тамбовского университета. Серия: Естественные и технические науки. - 2012. - Т. 17. - № 2. - С. 591-597.
10. Ильченко Е.А. Инструменты математического сервиса MathPartner для выполнения параллельных вычислений на кластере [Текст] / Е.А. Ильченко // Труды Института системного программирования РАН. - 2016. - Т. 28 - № 3. - С. 173-188. - DOI: 10.15514/ ISPRAS-2016-28(3)-11.
11. Короткий В.А. Графические алгоритмы реконструкции кривой второго порядка, заданной мнимыми элементами [Текст] / В.А. Короткий, А.Г. Гирш // Геометрия и графика. - 2016. - Т. 4. - № 4. - C. 19-30. - DOI:https://doi.org/10.12737/22840.
12. Латкин И.В. Вычислительная сложность фрагментов теории поля комплексных чисел [Текст] / И.В. Латкин, А.В. Селиверстов // Вестник Карагандинского университета. Серия «Математика». - 2015. - № 1. - C. 47-55.
13. Малашонок Г.И. Новое поколение систем символьных вычислений [Текст] / Г.И. Малашонок // Вестник Тамбовского университета. Серия «Естественные и технические науки». - 2016. - Т. 21. - № 6. - С. 2026-2041. - DOI:https://doi.org/10.20310/1810-0198-2016-21-6-2026-2041.
14. Мёллер Х. Алгоритм Лагерра сумм степеней для эффективной и надежной аппроксимации всех корней многочлена [Текст] / Х. Мёллер // Проблемы передачи информации. - 2015. - Т. 51. - № 4. - C. 47-59.
15. Милосердов Е.П. Расчет параметров конструкции и разработка алгоритмов реализации аналемматических солнечных часов [Текст] / Е.П. Милосердов, М.А. Глебов // Геометрия и графика. - 2014. - Т. 2. - № 3. - C. 14-16. - DOI:https://doi.org/10.12737/6520.
16. Прасолов В.В. Эллиптические функции и алгебраические уравнения [Текст] / В.В. Прасолов, Ю.П. Соловьев. - М.: Факториал, 1997.
17. Прун В.Е. Вычислительно эффективный вариант алгебраического метода компьютерной томографии [Текст] / В.Е. Прун [и др.] // Автоматика и телемеханика. - 2013. - № 10. - С. 86-97.
18. Рубанов Л.И. Параллельное моделирование Монте- Карло на системах с распределённой памятью [Текст] / Л.И. Рубанов // International Journal of Open Information Technologies. - 2014. - Т. 2. - № 2. - С. 12-20.
19. Рубанов Л.И. Проективно-инвариантное описание излучины реки [Текст] / Л.И. Рубанов, А.В. Селиверстов // Информационные процессы. - 2016. - Т. 16. - № 3. - С. 281-290.
20. Сальков Н.А. Графо-аналитическое решение некоторых частных задач квадратичного программирования [Текст] / Н.А. Сальков // Геометрия и графика. - 2014. - Т. 2. - № 1. - C. 3-8. - DOI:https://doi.org/10.12737/3842
21. Селиверстов А.В. Кубические формы без мономов от двух переменных [Текст] / А.В. Селиверстов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. - 2015. - Т. 25. - № 1. - С. 71-77.
22. Селиверстов А.В. О симметрии проективных кривых [Текст] / А.В. Селиверстов // Вестник Тверского государственного университета. Серия: Прикладная математика. - 2016. - № 3. - С. 59-66.
23. Хейфец А.Л. Сравнение методов начертательной геометрии и 3D-компьютерного геометрического моделирования по точности, сложности и эффективности [Текст] / А.Л. Хейфец // Вестник Южно-Уральского государственного университета. Серия «Строительство и архитектура». - 2015. - Т. 15. - № 4. - С. 49-63. - DOI:https://doi.org/10.14529/build150408.
24. Юрков В.Ю. Формальное представление условий инцидентности в многомерных проективных пространствах [Текст] / В.Ю. Юрков // Геометрия и графика. - 2016. - Т. 4. - № 4. - C. 3-13. - DOI:https://doi.org/10.12737/22838.
25. Eder C. A survey on signature-based algorithms for computing Gröbner bases [Текст] / C. Eder, J.-C. Faugère // Journal of Symbolic Computation. 2017. V. 80. № 3. P. 719-784. - DOI:https://doi.org/10.1016/j.jsc.2016.07.031.
26. Harrell E.M. A direct proof of a theorem of Blaschke and Lebesgue [Текст] / E.M. Harrell // The Journal of Geometric Analysis. 2002. V. 12. No. 1. P. 81-88. DOI: 10.1007/ BF02930861.
27. Herrero M.I. Affine solution sets of sparse polynomial systems [Текст] / M.I. Herrero, G. Jeronimo, J. Sabia // Journal of Symbolic Computation. 2013. V. 51. P. 34-54. DOI:https://doi.org/10.1016/j.jsc.2012.03.006.
28. Mishkin D. MODS: Fast and robust method for two-view matching [Текст] / D. Mishkin, J. Matas, M. Perdoch // Computer Vision and Image Understanding. 2015. V. 141. P. 81-93. DOI:https://doi.org/10.1016/j.cviu.2015.08.005.
29. Seliverstov A.V. On cubic hypersurfaces with involutions [Текст] / A.V. Seliverstov // International Conference Polynomial Computer Algebra'2016, Russian Academy of Sciences, St.Petersburg Department of Steklov Mathematical Institute, Euler International Mathematical Institute / Ed. by N.N. Vassiliev. - СПб.: Изд-во ВВМ, 2016. - С. 74- 77. URL: http://elibrary.ru/item.asp?id=26437524/
