Учитывая общую полилинию и ортогональную сетку, я хотел бы вычислить более простую полилинию, вершины которой лежат на ребрах / вершинах сетки. Это может выглядеть так:
Слева: плотная полилиния в качестве входных данных, справа: более грубая полилиния, вершины которой лежат на пересечении входной полилинии с ребрами / вершинами сетки
(извините за ссылку на изображение, но переполнение стека, по-видимому, не позволяет мне вставлять картинки до получения 10 кредитных баллов).
Сетка всегда ортогональна, но ее вершины не обязательно имеют целочисленные координаты, поскольку некоторые линии x или y могут иметь координаты, определенные в предыдущем вычислении геометрического пересечения. Начальная кривая может быть представлена в виде ломаной линии (хотя было бы неплохо также иметь поддержку кривой Безье), необязательно x-монотонной, и она могла бы пересекать сетку также вдоль целых ребер.
Моей первой мыслью было вызвать CGAL :: compute_subcurves (..) с линиями сетки и кривой, которую я добавляю. Я надеялся получить список полилиний, каждая из которых состоит из максимально нескольких сегментов внутри грани исходной сетки. На практике, даже если входные данные состоят из полилиний и выходные данные из монотонных полилиний, я получаю список разделенных сегментов. К ним относятся также сегменты сетки, а также сегменты полилинии, и они не упорядочиваются путем «обхода сегментов кривой», как это необходимо для вычисления упорядоченных точек пересечения. Если бы они были упорядочены, решением было бы итеративно пройти по ним и проверить, какой из них пересекает исходную сетку, а затем сохранить точки.
Другой вариант, о котором я подумал, - это начать с расположения линий сетки, постепенно добавлять сегменты ломаной линии и иметь механизм уведомления, уведомляющий меня о новых ребрах, которые попарно не пересекаются внутри, но в случае ребра пересеченного Полилинии - это оригинальный край сетки, я не получу уведомление, и я буду скучать по нему. Поэтапное добавление сегментов и проверка на наличие коллизий также не кажутся простыми, так как API компоновки do_intersect (..), кажется, возвращает не более одной точки, в то время как данный сегмент входной полилинии может легко пересекать две линии сетки рядом с угол или даже полностью лежать на сегменте сетки.
Возможно, мне не хватает простого решения. Может кто-нибудь дать мне указатель или какой-нибудь вызов API, который может помочь здесь?
Редактировать: Возможно, произошла путаница. Сетка является ортогональной, но не обязательно регулярной и может иметь координаты, которые не могут масштабироваться глобально до целых чисел, таких как здесь .