Здравствуйте, существует ли машинный способ определения квадранта, в котором находится точка с координатами x и y?
Наивное решение делает простой перебор вариантов:
if (x > 0 && y > 0)
printf("point (%d, %d) lies in the First quandrant
");
else if (x < 0 && y > 0)
printf("point (%d, %d) lies in the Second quandrant
");
else if (x < 0 && y < 0)
printf("point (%d, %d) lies in the Third quandrant
");
else if (x > 0 && y < 0)
printf("point (%d, %d) lies in the Fourth quandrant
");
else if (x == 0 && y == 0)
printf("point (%d, %d) lies at the origin
");
Вот мой более общий вариант (внимание: в моём варианте точка 0,0 координатной плоскости находится на северо-западе и является наименьшей, отсюда и несколько другое распределение номеров квадрантов, но суть та же) для нахождения квадранта распределения точки point от данной точки centerPoint вариант (для пограничных случаев я намеренно помещаю точки, лежащие на границах квадрантов, в один из этих квадрантов):
if (point.x > centerPoint.x) {
if (point.y > centerPoint.y) {
return KPClusterDistributionQuadrantFour;
} else {
return KPClusterDistributionQuadrantOne;
}
} else if (point.x < centerPoint.x) {
if (point.y > centerPoint.y) {
return KPClusterDistributionQuadrantThree;
} else {
return KPClusterDistributionQuadrantTwo;
}
} else {
if (point.y > centerPoint.y) {
return KPClusterDistributionQuadrantThree;
} else if (point.y < centerPoint.y) {
return KPClusterDistributionQuadrantTwo;
}
}
return KPClusterDistributionQuadrantNone;
Под машинным способом я главным образом подразумеваю использование битовых операций: мы видим, что:
квадрант I) x > 0, y > 0 => ++
квадрант II) x < 0, y > 0 => -+
квадрант III) x < 0, y < 0 => --
квадрант IV) x > 0, y < 0 => +-
...откуда, как подсказывает интуиция, можно было бы как-то схитрить, чтобы получилось:
+ ? + = 1
- ? + = 2
- ? - = 3
+ ? - = 4
или в контексте моей координатной системы с иным распределением квадрантов:
+ ? - = 1
- ? - = 2
- ? + = 3
+ ? + = 4
Вопрос в том, что может стоять за этим "?".
Буду рад любым советам. Интересуюсь этим вопросом больше для образования, хотя практика тоже обещает выиграть от этого, если такое решение возможно и существует.
Сам я также собираюсь посмотреть, как конкретно работают тангенсы и арктангенсы в С - возможно то, что они возвращают, мне тоже может как-то подойти.
Спасибо.
ОБНОВЛЕНО ПОЗЖЕ
Только что нашёл решение на SO, только теперь нужно попытаться его, как следует, понять: Optimizing quadrant selection
The fastest way in C/C++ it would be
(((unsigned int)x >> 30) & 2) | ((unsigned int)y >> 31)
(30/31 or 62/63, depending on size of int). This will give the quadrants in order 0, 2, 3, 1.
И решение относительно данного центра:
(((unsigned int)(x - center.x) >> 30) & 2) | ((unsigned int)(y-center.y) >> 31)
Буду признателен, если кто подскажет, что нужно изменить в этом решении, чтобы оно стало работать для точек x, y с типом double.
Комментарий по поводу принятого ответа
Оказалось, что всё-таки обычное решение с двойным if-else ветвлением работает быстрее, чем решение в принятом ответе (соотношение, которое я получаю достаточно стабильно: 160 к 180).
Вот окончательные версии, которые я сравнивал между собой (система координат инвертирована относительно оси y относительно декартовой):
Версия с обычным ветвлением
static inline KPClusterDistributionQuadrant KPClusterDistributionQuadrantForPointInsideMapRectBranching(MKMapRect mapRect, MKMapPoint point) {
MKMapPoint centerPoint = (MKMapPoint){
mapRect.origin.x + mapRect.size.width / 2,
mapRect.origin.y + mapRect.size.height / 2
};
if (point.x >= centerPoint.x) {
if (point.y >= centerPoint.y) {
return KPClusterDistributionQuadrantFour;
} else {
return KPClusterDistributionQuadrantOne;
}
} else {
if (point.y >= centerPoint.y) {
return KPClusterDistributionQuadrantThree;
} else {
return KPClusterDistributionQuadrantTwo;
}
}
}
Вариант @paulgri
NS_INLINE int KPClusterDistributionQuadrantForPointInsideMapRect(MKMapRect mapRect, MKMapPoint point) {
MKMapPoint centerPoint = (MKMapPoint){
mapRect.origin.x + mapRect.size.width / 2,
mapRect.origin.y + mapRect.size.height / 2
};
double dx = point.x - centerPoint.x;
double dy = point.y - centerPoint.y;
return ((*((long long *)&dy) >> 63) & 3) ^ ((*((long long *)&dx) >> 63) & 1);
}
Решение со StackOverflow (адаптировано @avp для работы с double)
NS_INLINE int KPClusterDistributionQuadrantForPointInsideMapRect_avp(MKMapRect mapRect, MKMapPoint point) {
MKMapPoint centerPoint = (MKMapPoint){
mapRect.origin.x + mapRect.size.width / 2,
mapRect.origin.y + mapRect.size.height / 2
};
double dx = point.x - centerPoint.x;
double dy = point.y - centerPoint.y;
return ((*((uint64_t *)&dx) >> 62) & 2) | (*((uint64_t *)&dy) >> 63);
}
Еще одно решение, предложенное моим коллегой - оно более медленное, но все же рабочее, поэтому я добавляю его сюда для коллекции:
uint32_t x = ...;
uint32_t y = ...;
char xsign = x >> 31 & 1;
char ysign = y >> 31 & 1;
int quadrant = 1 + (xsign ^ ysign) + 2 * ysign;
Ответ
Если квадрант отыскивается относительно точки О(0,0), то можно обойтись битовыми операциями и манипулировать знаками чисел, зная, что сдвиг вправо является арифметическим (надеюсь, переменныне типа int?), например так (к размерам типов и пр. прошу не придираться, это набросок кода - только идея): n = ((y>>31)&3 ^ (x>>31)&1) + 1; Здесь +1 надо только для того, чтобы квадратны начинались с 1. Если относительно некоторой точки (x0,y0), то достаточно вместо x и y поставить разности. Как вариант - используйте тернарную операцию и обычные сравнения. UPD: одновременно написали )) Для типов с плавающей запятой битовые операции не применимы, используйте тернарную. UPD2: обратите внимание, это не тот же вариант, в моем варианте квадратны нумеруются правильно, по порядку 1,2,3,4. UPD3: Если x и y переменные типа double, то можно указатели на них привести к указателям на целочисленный тип так, чтобы знаковые разряды мантиссы оказались на месте знаковых разрядов целого и дальше все по той же схеме. Только посмотреть надо, где они у double. Приведение указателей на примитивные типы - фактически фиктивная операция, время не тратится ни на какие преобразования.
Комментариев нет:
Отправить комментарий