У меня есть массив с координатами центра небольших кругов, имеющих одинаковый радиус. Я знаю, как найти, когда мышь находится над кругом, но мой массив большой, и мне нужен самый быстрый способ вычислить эту операцию.Проверьте, находится ли мышь над кругом - Java
Есть ли способ найти, находится ли мышь над кругом, не зацикливая весь массив для каждого движения мыши?
Что делать, если вы проверяете координаты, которые являются расстоянием r (радиус) от мыши? Затем вы можете сузить свой поиск в массиве, если он упорядочен.
Первоначально создан некоторая «зона» для более быстрой справки:
Каждый раз, когда вы хотите проверить, находится ли мышь над кругом, вам не придется проходить через весь массив кругов. Вместо этого:
Это похоже на проблему оптимизации пограничной проверки для большого количества предметов. Подход линейности не слишком хорошо масштабируется для тысяч кругов.
Это хорошая тема для чтения в сети. Но сначала, не дойдя туда, я попытаюсь объяснить (как упражнение) то, что я буду исследовать. Я бы создал двоичное дерево и разделил пространство, вместо этого вместо массива я бы поставил точки окружности в такое дерево. Глядя на элементы дерева, которые ближе к фактическому местоположению X, Y, становится предметом двоичного поиска на дереве. В результате этого поиска у вас есть самая близкая точка, и вы можете проверить на нее конфликт. Для алгоритма еще нужно сделать, и необходимы дальнейшие оптимизации. Например, как проверить больше очков, а не только окончательный? Потенциально мне нужно дерево для координаты X, другое для координаты Y и т. Д. Но я бы изучил эти идеи. Я вернусь к этому сообщению и расширю свой ответ с помощью фактического примера и более конкретного решения.