Проверьте, находится ли точка в пределах m-мерного прямоугольника

Question

Я пытаюсь придумать обобщенный алгоритм для определения того, находится ли точка внутри или на границе m-мерного гиперреугольника, определенного с использованием интервалов.

Для 2D-случая это прямолинейно, и можно, если точка лежит внутри многоугольника, используя такие методы, как приведение лучей. Однако, как можно было бы проверить m-мерный гиперреугольник? Есть ли способ сказать уравнение таким гиперугольником и проверить, находится ли точка внутри или на границе?

Я пытаюсь реализовать это в C ++, есть ли какие-нибудь известные библиотеки, которые могут помочь?

Спасибо! Помощь очень ценится!

Answer 1

Если у вас есть гиперугол (HR), сохраненный как комбинация интервалов (то есть, центральная координата + экстент или начало + конец) и вращений, вы можете преобразовать точку запроса в систему координат HR (с помощью соответствующего поворота, перевода и масштабирование). Тогда вам нужно только сделать 2*m привязанные проверки.

Предлагаемая вами альтернатива использования многогранника - это потенциальная проблема с производительностью, потому что у m-мерного HR есть 2^m угловых точек.

(Это, конечно, при условии, что вы не ограничиваетесь прямоугольниками, выровненными по оси, и в этом случае ответ, конечно, тривиален)

Answer 2

Что не так с простым подходом?

if ((Point.x[0]>= Rect.min[0]) && (Point.x[0] <= Rect.max[0]) && 
 ...
   (Point.x[m-1]>= Rect.min[m-1]) && (Point.x[m-1] <= Rect.max[m-1])) 

в петле по размерам, конечно же