Линия Erase Scene: задача пересечения окружности и кривой в двумерном пространстве

Question

В настоящее время я сталкиваюсь со сценарием удаления линии в моем проекте. Я надеюсь получить некоторые предложения оттуда. Далее следует абстрагироваться от конкретной проблемы:

Двумерная область m * n с множеством неправильных кривых, каждая из которых записана во многих точках: [(x1, y1), (x2, y2), (x3, y3) ...], хранится в виде массивов: array1, array2 ..., теперь есть окружность (x, y) с радиусом r, мне нужно подтвердить, есть ли пересечение окружности и этих линий,и выберите линии с пересечениями. Кроме того, координаты и радиус круга постоянно меняются, а нерегулярная кривая меняется, но изменение происходит не очень быстро, поэтому мне нужно рассмотреть возможность использования кэша для повышения производительности.

Рис. случай:

Некоторые из моих мыслей: На самом деле, даже если Он пересекает все точки один раз, сложность O (N), но здесь N немного велико, и потому что круг меняется в реальном времени, поэтому производительность все еще относительно низкая. Я могу выбрать использование квадродерева, но это не типичный сценарий двухмерного столкновения, и я должен также учитывать, что текущий метод хранения не выполняется, поэтому мне нужно выполнить синхронное обновление в реальном времени двух структур данных, ноОбщий вид должен быть лучше, чем первый метод, но я не знаю, если это правильный путь. Кроме того, я думаю, что здесь должно быть лучшее решение.

Есть ли какие-нибудь хорошие идеи или соответствующий опыт, которым можно поделиться? Большое спасибо

Answer 1

Из личного опыта создания нетрадиционных 2D-сред все, что я могу сказать, это попробовать разные вещи и посмотреть, что работает. Я не могу понять из вашего описания, сможете ли вы просто перебрать обнаружение столкновений или вам понадобится квадри;Есть вероятность, что вам может понадобиться многопоточность, если у вас необычайное количество кривых.

Я думаю, что для этого нужно создать класс Segment для каждой из ваших полилиний (потому что онипо сути, это набор сегментов, а не кривой), и используйте квадродерево, чтобы определить, какие сегменты находятся ближе всего к кругу, которые также будут помещены в квадродерево. Таким образом, всякий раз, когда вы запускаете столкновение, вы можете пометить каждый перекрывающийся сегмент как «выбранный» и делать все, что вам нужно. Я думаю, что только наличие их в виде множества точек усложняет жизнь, и это действительно то, что графический конвейер счел бы полезным.

Если вы обнаружите, что ваши линии слишком плотные с точками, я бы посоветовал взглянуть на алгоритмы прореживания полилиний, чтобы уменьшить их сложность;конечно, если это все еще будет соответствовать вашим целям.