Programming of the search algorithm for point belonging to the polygon and the mutual non-intersection of the figures - Gavrilov, Taras (Technology audit and production reserves, 2017)
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.