Метод прискореної кругової інтерполяції на гексагональному растрі

Abstract

An alternative to the rectangular raster, which has become the most widely used in information visualization tools, is the hexagonal raster, in which the pixel has the shape of a regular hexagon. The use of such a raster makes it possible to increase the resolution of screens, and, as a result, to increase the realism of the formation of graphic images. The use of a hexagonal raster allows you to tile the screen plane without gaps and overlaps. Important geometrical features of the hexagon are reflection symmetry and hexabond. Circles are among the most common primitives, so the time of formation of graphic scenes largely depends on the time of formation of circle arcs. The paper provides an analysis of circular interpolation methods, which showed the expediency of using the estimation function method. It is proposed to form a step trajectory of a circle in double increments on a hexagonal grid. A computer program was developed to determine the stochastic distribution of double step trajectories for areas whose borders are 150 degrees apart. Through mathematical modeling of the procedure of interpolation of circles with radii from 1 to 4000 points (the interpolation algorithm provided an interpolation error that did not exceed the discretization step), the specific weight of double increments of a certain type in the total number was determined. The above-mentioned studies make it possible to develop a number of high-performance methods of circular interpolation by taking into account the stochastic distribution of step increments. It is shown that the formation of the step trajectory in each section is possible by two types of fixed double increments. At the same time, to predict the position of the next point of the trajectory, a double step is selected, which has a higher probability of occurrence. In case of incorrect forecasting, the estimation function is corrected with the simultaneous forecasting of the next double increment. The formation of a step trajectory of a circle on a hexagonal grid with double increments made it possible to increase the performance of circular interpolation by an average of 1.7 times.

Альтернативою прямокутного растру, який отримав найбільшого поширення в засобах візуалізації інформації, є гексагональний растр, за якого піксел має форму правильного шестикутника. Використання такого растру дає можливість підвищити роздільну здатність екранів, і, в наслідку, підвищити реалістичність формування графічних зображень. Використання гексагонального растру дозволяє замощувати площину екрану без розривів і накладань. Важливими геометричними особливостями гексагона є рефлекційна симетрія та шестизв’язність. Кола відносять до найпоширеніших примітивів, тому час формування графічних сцен значною мірою залежить від часу формування дуг кіл. У роботі наведено аналіз методів колової інтерполяції, який показав доцільність використання методу оцінювальної функції. Запропоновано формувати на гексагональному растрі крокову траєкторію кола подвійними приростами. Розроблено комп’ютерну програму для визначення стохастичного розподілу подвійних крокових траєкторій для ділянок, границі яких віддалені одна від одної на 15°. Шляхом математичного моделювання процедури інтерполювання кіл радіусами від 1 до 4000 точок (алгоритм інтерполяції забезпечував похибку інтерполювання, що не перевищувала кроку дискретизації) визначено питому вагу подвійних приростів певного виду в загальній кількості. Наведені дослідження дають можливість розробки низки високопродуктивних методів кругової інтерполяції шляхом врахування стохастичного розподілу крокових приростів Показано, що формування крокової траєкторії на кожній ділянці можливе двома типами фіксованих подвійних приростів. При цьому для прогнозування позиції наступної точки траєкторії вибирається подвійний крок, який має більшу ймовірність появи. У випадку неправильного прогнозування виконується корекція оцінювальної функції з одночасним прогнозуванням наступного подвійного приросту. Формування крокової траєкторії кола на гексагональному растрі подвійними приростами дало можливість підвищити продуктивність колової інтерполяції в середньому в 1,7 разів