Programming of the search algorithm for point belonging to the polygon and the mutual non-intersection of the figures
DOI:
https://doi.org/10.15587/2312-8372.2017.105505Keywords:
ray tracing method, Graham method, nesting pattern, adding and exclusion of the parts from the patternAbstract
The object of research is shoe parts of various configurations. At the enterprises of the footwear industry, there is a problem of densely stacking shoe parts in the nesting pattern. To solve this problem, the hodograph of the vector function of the dense distribution of geometric figures is applied. Ray tracing method is used for the formation of rational nesting patterns. These methods are introduced into the developed software package for computer-aided design of nesting patterns. Three main algorithms for finding the point belonging to the polygon are analyzed. There are much more algorithms that solve this problem, but these algorithms have optimal complexity parameters: O(2*N) against O(N^2) in other algorithms.
Based on the analysis of the three main algorithms, an algorithm for exclusion of the part from the nesting pattern is created. This algorithm is modified and adjusted to the requirements of the task – leaving 4–6 parts of one configuration in the nesting pattern. A characteristic feature of the algorithm is that instead of constructing a single point for the ray, the pole of the part is used.
References
- Haines, E. (1994). Point in Polygon Strategies. Graphics Gems. Elsevier, 24–46. doi:10.1016/b978-0-12-336156-1.50013-6
- Weiler, K. (1994). An Incremental Angle Point in Polygon Test. Graphics Gems. Elsevier, 16–23. doi:10.1016/b978-0-12-336156-1.50012-4
- Foley, J. D., Feiner, S. K., Hughes, J. F., Van Dam, A. (1990). Computer Graphics: Principles and Practice. Ed. 2. Addison-Wesley, 1200.
- Har-Peled, S., Roy, S. (2016). Approximating the Maximum Overlap of Polygons under Translation. Algorithmica, 78 (1), 147–165. doi:10.1007/s00453-016-0152-9
- Landier, S. (2017). Boolean operations on arbitrary polygonal and polyhedral meshes. Computer-Aided Design, 85, 138–153. doi:10.1016/j.cad.2016.07.013
- Wang, Z.-J., Lin, X., Fang, M.-E., Yao, B., Peng, Y., Guan, H., Guo, M. (2017). Re2l: An efficient output-sensitive algorithm for computing Boolean operations on circular-arc polygons and its applications. Computer-Aided Design, 83, 1–14. doi:10.1016/j.cad.2016.07.004
- Chen, D. Z., Wang, H. (2015). Computing the Visibility Polygon of an Island in a Polygonal Domain. Algorithmica, 77 (1), 40–64. doi:10.1007/s00453-015-0058-y
- Chertenko, L. P., Konoval, V. P. (2002). Matematychne zadannia konturiv vnutrishnoi formy vzuttia. Visnyk KNUTD, 1, 15–19.
- Zalgaller, V. A. (1953). Ob odnom neobhodimom priznake plotneishego raspolozheniia figur. UMN, 8(4(56)), 153–162.
- Gavrilov, Т. M. (2011). Tekhnolohiia pidrakhunku kompleksnoho pokaznyka yakosti materialiv dlia vzuttia za dopomohoiu ekspertnykh otsinok. Lehka promyslovist, 1, 27–29.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2017 Taras Gavrilov
This work is licensed under a Creative Commons Attribution 4.0 International License.
The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.
