New as well as already known methods for detection of singular points on a plane curve and for this curve’s smoothness confirmation have been considered in the present paper. Our approach based on the plotting of tangent straight lines to the curve, which pass through distinguished points out of the curve. At the singular point of the curve many such lines intersect each other, because of this it is possible quickly identify the singular point on the convex curve. In general, the number of real tangent lines depends on the distinguished point on the plane. However, the existence of at least one singular point in the algebraic curve imposes a restriction on the algebraic equation determining the set of tangent lines passing through the distinguished point of the plane. So a plane algebraic curve’s smoothness checking reduces to checking the incompatibility of a linear equation system. On the other hand, it’s possible to generate the tangent lines graphically. So generation of real tangent lines allows prove the absence of not only real but also complex singular points on the projective curve, which in any case would not belonged to the real plane. This demonstrates the effectiveness of graphical methods for complex geometry’s tasks solution. The method allows the direct generalization to the multidimensional case, which is important for combinatorial problems solution. In the case, it is necessary to consider not separate tangent lines, but cones with vertices at different points in space. Search for singular points is also important for solution the problems of machine vision, including detection of an obstacle’s corner by means of the frame sequence obtained with one camera on a moving vehicle.
plane curve, singular point, tangent line, convex domain, pattern recognition, machine vision.
Введение
Если плоская кривая C задана известным алгебраическим уравнением, то поиск особой точки сводится к решению системы алгебраических уравнений от двух переменных. Исключение одной переменной сводит решение этой системы к поиску корней многочлена от одной переменной. Для аппроксимации корней известны эффективные алгоритмы [14]. Исключение одной из двух переменных легко выполняется алгоритмами, основанными на вычислении базиса Гребнера [25] и реализованными во многих пакетах программ для символьных вычислений [13], например, можно использовать облачный сервис MathPartner [10]. Также известны другие методы, обзор которых сделан в работе [27].
1. Girsh A.G. Mnimosti v geometrii [Ostensibilities in geometry]. Geometriya i grafika [Geometry and Graphics]. 2014, v. 2, i. 2, pp. 3-8 (in Russian). DOI:https://doi.org/10.12737/5583.
2. Girsh A.G. Ogibayushchaya semeystva liniy [Envelope of a family of curves]. Geometriya i grafika [Geometry and Graphics]. 2016, v. 4, i. 4, pp. 14-18 (in Russian). DOI:https://doi.org/10.12737/22839.
3. Girsh A.G. Fokusy algebraicheskikh krivykh [Foci of algebraic curves]. Geometriya i grafika [Geometry and Graphics]. 2015, v. 3, i. 3, pp. 4-17 (in Russian). DOI:https://doi.org/10.12737/14415.
4. Dzhanabaev Z.Z., Umbetov N.S. Ob algoritme graficheskogo postroeniya geodezicheskoy linii na lineychatoy poverkhnosti [On algorithms of graphical plotting of geodesic line on a ruled surface]. Geometriya i grafika [Geometry and Graphics]. 2015, v. 3, i. 4, pp. 15-18 (in Russian). DOI:https://doi.org/10.12737/17346.
5. Ershov E.I., Karnaukhov V.N., Mozerov M.G. Algoritmy stereozreniya na osnove parallaksa dvizheniya monokulyarnoy kamery bokovogo obzora [Stereovision algorithms applicability investigation for motion parallax of monocular camera case]. Informatsionnye protsessy [Iformation Process]. 2016, v. 61, i. 6, pp. 695-704. DOI:https://doi.org/10.1134/S1064226916060073.
6. Zaeva K.A., Semenov A.B. Metod marshrutizatsii s prepyatstviyami na osnove parallel'nykh vychisleniy [Method of routing with obstacles based on parallel computing]. Vestnik TvGU. Seriya: Prikladnaya Matematika [Herald of Tver State University. Series: Applied Mathematics]. 2016, i. 3, pp. 85-95 (in Russian).
7. Ivanov G.S., Dmitrieva I.M. O zadachakh nachertatel'noy geometrii s mnimymi resheniyami [About the tasks of descriptive geometry with imaginary solutions]. Geometriya i grafika [Geometry and Graphics]. 2015, v. 3, i. 2, pp. 3-8 (in Russian). DOI:https://doi.org/10.12737/12163.
8. Ivanov G.S., Dmitrieva I.M. Printsip dvoystvennosti - teoreticheskaya baza vzaimosvyazi sinteticheskikh i analiticheskikh sposobov resheniya geometricheskikh zadach [The duality principle is the theoretical basis of interrelation of synthetic and analytical methods of solving geometric problems]. Geometriya i grafika [Geometry and Graphics]. 2016, v. 4, i. 3, pp. 3-10 (in Russian). DOI:https://doi.org/10.12737/21528.
9. Ivashov D.S. Ob algoritme faktorizatsii polinomov mnogikh peremennykh [An algorithm of factorization of multivariate polynomials]. Vestnik Tambovskogo universiteta. Seriya: Estestvennye i tekhnicheskie nauki [Tambov University Reports. Series: Natural and Technical Sciences]. 2012, v. 17, i. 2, pp. 591-597 (in Russian).
10. Ilchenko E.A. Instrumenty matematicheskogo servisa MathPartner dlya vypolneniya parallel'nykh vychisleniy na klastere [Tools of mathematical service MathPartner for parallel computations on a cluster]. Trudy ISP RAN [Proc. ISP RAS]. 2016, vol. 28, no. 3, pp. 173-188 (in Russian). DOI:https://doi.org/10.15514/ISPRAS-2016-28(3)-11.
11. Korotkiy V.A., Girsh A.G. Graficheskie algoritmy rekonstruktsii krivoy vtorogo poryadka, zadannoy mnimymi elementami [Graphic reconstruction algorithms of the secondorder curve, given by the imaginary elements]. Geometriya i grafika [Geometry and Graphics]. 2016, v. 4, i. 4, pp. 19-30 (in Russian). DOI:https://doi.org/10.12737/22840.
12. Latkin I.V. Vychislitel'naya slozhnost' fragmentov teorii polya kompleksnyh chisel [Tekst] / I.V. Latkin, A.V. Seliverstov // Vestnik Karagandinskogo universiteta. Seriya «Matematika». - 2015. - № 1. - C. 47-55.
13. Malashonok G.I. Novoe pokolenie sistem simvol'nyh vychisleniy [Tekst] / G.I. Malashonok // Vestnik Tambovskogo universiteta. Seriya «Estestvennye i tehnicheskie nauki». - 2016. - T. 21. - № 6. - S. 2026-2041. - DOI:https://doi.org/10.20310/1810-0198-2016-21-6-2026-2041.
14. Meller H. Algoritm Lagerra summ stepeney dlya effektivnoy i nadezhnoy approksimacii vseh korney mnogochlena [Tekst] / H. Meller // Problemy peredachi informacii. - 2015. - T. 51. - № 4. - C. 47-59.
15. Miloserdov E.P. Raschet parametrov konstrukcii i razrabotka algoritmov realizacii analemmaticheskih solnechnyh chasov [Tekst] / E.P. Miloserdov, M.A. Glebov // Geometriya i grafika. - 2014. - T. 2. - № 3. - C. 14-16. - DOI:https://doi.org/10.12737/6520.
16. Prasolov V.V. Ellipticheskie funkcii i algebraicheskie uravneniya [Tekst] / V.V. Prasolov, Yu.P. Solov'ev. - M.: Faktorial, 1997.
17. Prun V.E. Vychislitel'no effektivnyy variant algebraicheskogo metoda komp'yuternoy tomografii [Tekst] / V.E. Prun [i dr.] // Avtomatika i telemehanika. - 2013. - № 10. - S. 86-97.
18. Rubanov L.I. Parallel'noe modelirovanie Monte- Karlo na sistemah s raspredelennoy pamyat'yu [Tekst] / L.I. Rubanov // International Journal of Open Information Technologies. - 2014. - T. 2. - № 2. - S. 12-20.
19. Rubanov L.I. Proektivno-invariantnoe opisanie izluchiny reki [Tekst] / L.I. Rubanov, A.V. Seliverstov // Informacionnye processy. - 2016. - T. 16. - № 3. - S. 281-290.
20. Sal'kov N.A. Grafo-analiticheskoe reshenie nekotoryh chastnyh zadach kvadratichnogo programmirovaniya [Tekst] / N.A. Sal'kov // Geometriya i grafika. - 2014. - T. 2. - № 1. - C. 3-8. - DOI:https://doi.org/10.12737/3842
21. Seliverstov A.V. Kubicheskie formy bez monomov ot dvuh peremennyh [Tekst] / A.V. Seliverstov // Vestnik Udmurtskogo universiteta. Matematika. Mehanika. Komp'yuternye nauki. - 2015. - T. 25. - № 1. - S. 71-77.
22. Seliverstov A.V. O simmetrii proektivnyh krivyh [Tekst] / A.V. Seliverstov // Vestnik Tverskogo gosudarstvennogo universiteta. Seriya: Prikladnaya matematika. - 2016. - № 3. - S. 59-66.
23. Heyfec A.L. Sravnenie metodov nachertatel'noy geometrii i 3D-komp'yuternogo geometricheskogo modelirovaniya po tochnosti, slozhnosti i effektivnosti [Tekst] / A.L. Heyfec // Vestnik Yuzhno-Ural'skogo gosudarstvennogo universiteta. Seriya «Stroitel'stvo i arhitektura». - 2015. - T. 15. - № 4. - S. 49-63. - DOI:https://doi.org/10.14529/build150408.
24. Yurkov V.Yu. Formal'noe predstavlenie usloviy incidentnosti v mnogomernyh proektivnyh prostranstvah [Tekst] / V.Yu. Yurkov // Geometriya i grafika. - 2016. - T. 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 [Tekst] / 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 [Tekst] / 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 [Tekst] / 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 [Tekst] / 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 [Tekst] / 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. - SPb.: Izd-vo VVM, 2016. - S. 74- 77. URL: http://elibrary.ru/item.asp?id=26437524/
