У меня есть список двумерных точек, и я хочу получить, какие из них попадают в полукруг.
Изначально целевой формой был прямоугольник, выровненный по осям x и y. Таким образом, текущий алгоритм сортирует пары по их координатам X и двоичному поиску по первому, который может попасть в прямоугольник. Затем он проходит по каждой точке последовательно. Он останавливается, когда попадает в точку, которая находится за пределами верхней границы X и Y целевого прямоугольника.
Это не работает для полукруга, так как вы не можете определить эффективные верхние / нижние границы x и y для него. Полукруг может иметь любую ориентацию.
В худшем случае, я найду наименьшее значение измерения (скажем, х) в полукруге, бинарный поиск до первой точки, которая находится за ней, а затем последовательно проверю точки, пока не выйду за верхнюю границу этого измерение. В основном, тестирование очков всей группы на сетке. Проблема заключается в том, что в результате будет проверено множество точек, которые находятся за пределами границ.