Блог

Я хочу вычислить, находится ли точка, (x,y) , внутри прямоугольника, который определяется двумя точками, (a,b) и (c,d) .

Если a<=c и b<=d , то это просто:

 a<=xamp;amp;x<=camp;amp;b<=yamp;amp;y<=d
  

Однако, поскольку неизвестно, является ли a<=c или b<=d , код должен быть

 (a<=xamp;amp;x<=c||c<=xamp;amp;x<=a)amp;amp;(b<=yamp;amp;y<=d||d<=yamp;amp;y<=b)
  

Этот код может работать, но он слишком длинный. Я могу написать функцию и использовать ее, но мне интересно, есть ли более короткий способ (и он должен выполняться очень быстро — код вызывается много) для его написания.

Я могу себе представить:

 ((c-x)*(x-a)>=0)amp;amp;((d-y)*(y-b)>=0)
  

Есть ли более умный способ сделать это?

(И есть ли какой-нибудь хороший способ выполнить итерацию от a до c?)

Меняйте переменные по мере необходимости так, чтобы a = x _min и b = y _min:

 if a > c: swap(a,c)
if b > d: swap(b,d)

a <= x <= c and b <= y <= d
  

Короче, но немного менее эффективен:

 min(a,c) <= x <= max(a,c) and min(b,d) <= y <= max(b,d)
  

Как всегда, при оптимизации вы должны профилировать различные параметры и сравнивать точные цифры. Конвейерная обработка, переупорядочивание инструкций, прогнозирование ветвлений и другие современные методы оптимизации компилятора / процессора делают неочевидным, стоит ли проводить микрооптимизацию на уровне программиста. Например, раньше умножение было значительно дороже, чем ветвление, но это уже не всегда так.

Мне нравится это:

 ((c-x)*(x-a)>=0)amp;amp;((d-y)*(y-b)>=0)
  

но с большим количеством пробелов и большей симметрией:

 (c-x)*(a-x) <= 0 amp;amp; (d-y)*(b-y) <= 0
  

Это математически элегантно и, вероятно, самое быстрое. Вам нужно будет измерить, чтобы действительно определить, какой из них самый быстрый. С современными конвейерными процессорами я ожидаю, что прямой код с минимальным количеством операторов будет выполняться быстрее.

Хотя сортировка (a, b) (c, d) пар and, как предложено в принятом ответе, вероятно, является лучшим решением в этом случае, еще лучшим применением этого метода, вероятно, было бы повысить a < b c < d требование and до уровня общепрограммного инварианта. Т.е. Требовать, чтобы все прямоугольники в вашей программе создавались и поддерживались вэта «нормализованная» форма с самого начала. Таким образом, внутри вашей тестовой функции point-in-rectangle вы должны просто утверждать это a < b и c < d вместо того, чтобы тратить ресурсы процессора на фактическую сортировку их при каждом вызове.

Определите промежуточные переменные i = min(a,b) , j = min(c,d) , k = max(a,b) , l = max(c,d)
Тогда вам нужно только i<=x amp;amp; x<=k amp;amp; j<=y amp;amp; y<=l .

РЕДАКТИРОВАТЬ: Имейте в виду, с точки зрения эффективности, вероятно, лучше использовать ваш «слишком длинный» код в функции.