Создание октодерева.

Создание октантного дерева. Диалоговое окно должно обеспечивать ввод уровня разбиения и возможность выбора многоугольника, для которого будет строиться октантное дерево. Октантное дерево – это структура данных, которая представляет собой плоское тело в виде рекурсивного подразделения двухмерного пространства на прямоугольные блоки (в нашей задаче квадраты).

Процедура построения октантного дерева. Сначала создаётся квадрат, в который многоугольник помещается целиком. Для этого находится максимальные и минимальные координаты по Х и по Y. Далее находится сторона квадрата и его центр. Этот квадрат называется корневым октантом. Затем корневой октант делится на 4 октанта, после чего анализируется их положение по отношению к многоугольнику. Если октант находится полностью внутри многоугольника, он считается «чёрным»; если снаружи – «белым». Если же октант частично лежит внутри многоугольника, а частично – снаружи, то он считается «серым» и делится на четыре октанта меньшего размера. Чёрные и белые октанты дальше не делятся. Процедура продолжается до тех пор, пока не будет достигнут заданный уровень разбиения. «Цвет» определяется следующим образом: проверяется, пересекаются ли стороны октанта со сторонами многоугольника (с помощью функции AutoLisp inters). Если стороны октанта пересекаются со сторонами многоугольника, то октант считается «серым». Иначе октант лежит внутри либо снаружи многоугольника. Чтобы определить его «цвет» подсчитывается количество пересечений отрезка лежащего между центром октанта и одной из вершин корневого октанта со сторонами многоугольника. Если количество пересечений чётное или ноль, то квадрат лежит снаружи многоугольника и считается «белым». Иначе если количество пересечений нечётное, то он лежит внутри многоугольника и считается «чёрным». На чертеже рисуются только октанты внутри треугольника