Programming of the search algorithm for point belonging to the polygon and the mutual non-intersection of the figures

Authors

DOI:

https://doi.org/10.15587/2312-8372.2017.105505

Keywords:

ray tracing method, Graham method, nesting pattern, adding and exclusion of the parts from the pattern

Abstract

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.

Author Biography

Taras Gavrilov, Open International University of Human Development «Ukraine», 23, Lvivska str., Kyiv, Ukraine, 03115

Assistant

Department of Computer Engineering

References

  1. Haines, E. (1994). Point in Polygon Strategies. Graphics Gems. Elsevier, 24–46. doi:10.1016/b978-0-12-336156-1.50013-6
  2. 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
  3. Foley, J. D., Feiner, S. K., Hughes, J. F., Van Dam, A. (1990). Computer Graphics: Principles and Practice. Ed. 2. Addison-Wesley, 1200.
  4. 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
  5. 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
  6. 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
  7. 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
  8. Chertenko, L. P., Konoval, V. P. (2002). Matematychne zadannia konturiv vnutrishnoi formy vzuttia. Visnyk KNUTD, 1, 15–19.
  9. Zalgaller, V. A. (1953). Ob odnom neobhodimom priznake plotneishego raspolozheniia figur. UMN, 8(4(56)), 153–162.
  10. Gavrilov, Т. M. (2011). Tekhnolohiia pidrakhunku kompleksnoho pokaznyka yakosti materialiv dlia vzuttia za dopomohoiu ekspertnykh otsinok. Lehka promyslovist, 1, 27–29.

Published

2017-05-30

How to Cite

Gavrilov, T. (2017). Programming of the search algorithm for point belonging to the polygon and the mutual non-intersection of the figures. Technology Audit and Production Reserves, 3(3(35), 29–32. https://doi.org/10.15587/2312-8372.2017.105505

Issue

Section

Measuring Methods in Chemical Industry: Original Research