Как я могу отсортировать массив точек/векторов, увеличивая угол против часовой стрелки от данного вектора оси?
Например:
Если 0 - вектор оси, я бы ожидал, что отсортированный массив будет в порядке 2, 3, 1.
Я уверен, что это можно сделать с помощью перекрестных продуктов, специализированного компаратора и std::sort().
Да, вы можете сделать это с помощью специализированного компаратора на основе перекрестного продукта. Единственная проблема заключается в том, что наивный компаратор не будет иметь свойство транзитивности. Таким образом, необходим дополнительный шаг, чтобы не допустить, чтобы углы каждой стороны ссылки считались закрытыми.
Это будет намного быстрее, чем что-либо, связанное с триггером. Там даже не нужно сначала нормализовать.
Здесь компаратор:
class angle_sort
{
point m_origin;
point m_dreference;
// z-coordinate of cross-product, aka determinant
static double xp(point a, point b) { return a.x * b.y - a.y * b.x; }
public:
angle_sort(const point origin, const point reference) : m_origin(origin), m_dreference(reference - origin) {}
bool operator()(const point a, const point b) const
{
const point da = a - m_origin, db = b - m_origin;
const double detb = xp(m_dreference, db);
// nothing is less than zero degrees
if (detb == 0 && db.x * m_dreference.x + db.y * m_dreference.y >= 0) return false;
const double deta = xp(m_dreference, da);
// zero degrees is less than anything else
if (deta == 0 && da.x * m_dreference.x + da.y * m_dreference.y >= 0) return true;
if (deta * detb >= 0) {
// both on same side of reference, compare to each other
return xp(da, db) > 0;
}
// vectors "less than" zero degrees are actually large, near 2 pi
return deta > 0;
}
};
Демо: http://ideone.com/YjmaN
Самый простой, но, возможно, не оптимальный способ - сдвиг декартовых координат относительно центральной точки, а затем преобразовать их в полярные координаты, Затем просто вычтите угол "стартового вектора" по модулю 360 и, наконец, отсортируйте по углу.
Или вы могли бы создать собственный компаратор для обработки всех возможных наклонов и конфигураций, но я думаю, что полярные координаты немного более прозрачны.
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
struct Point {
static double base_angle;
static void set_base_angle(double angle){
base_angle = angle;
}
double x;
double y;
Point(double x, double y):x(x),y(y){}
double Angle(Point o = Point(0.0, 0.0)){
double dx = x - o.x;
double dy = y - o.y;
double r = sqrt(dx * dx + dy * dy);
double angle = atan2(dy , dx);
angle -= base_angle;
if(angle < 0) angle += M_PI * 2;
return angle;
}
};
double Point::base_angle = 0;
ostream& operator<<(ostream& os, Point& p){
return os << "Point(" << p.x << "," << p.y << ")";
}
bool comp(Point a, Point b){
return a.Angle() < b.Angle();
}
int main(){
Point p[] = { Point(-4., -4.), Point(-6., 3.), Point(2., -4.), Point(1., 5.) };
Point::set_base_angle(p[0].Angle());
sort(p, p + 4, comp);
Point::set_base_angle(0.0);
for(int i = 0;i< 4;++i){
cout << p[i] << " angle:" << p[i].Angle() << endl;
}
}
DEMO
Point(-4,-4) angle:3.92699
Point(2,-4) angle:5.17604
Point(1,5) angle:1.3734
Point(-6,3) angle:2.67795
Предполагая, что они имеют одинаковую длину и имеют одинаковое происхождение, вы можете сортировать по
struct sorter {
operator()(point a, point b) const {
if (a.y > 0) { //a between 0 and 180
if (b.y < 0) //b between 180 and 360
return false;
return a.x < b.x;
} else { // a between 180 and 360
if (b.y > 0) //b between 0 and 180
return true;
return a.x > b.x;
}
}
//for comparison you don't need exact angles, simply relative.
}
Это быстро отсортирует их с 0- > 360 degress. Затем вы найдете свой вектор 0 (в позиции N), а std::rotate результаты оставят N элементов. (Спасибо TomSirgedas!)
Сначала вы должны нормализовать каждый вектор, поэтому каждая точка находится в формате (cos (t_n), sin (t_n)). Затем вычисляем cos и sin углы между каждой точкой и точкой отсчета. Конечно:
cos(t_n-t_0)=cos(t_n)cos(t_0)+sin(t_n)sin(t_0) (this is equivalent to dot product)
sin(t_n-t_0)=sin(t_n)cos(t_0)-cos(t_n)sin(t_0)
Только на основе обоих значений, вы можете определить точные углы (-pi пи) между точками и точкой отсчета. Если использовать только точечный продукт, то по часовой стрелке и против часовой стрелки одинакового угла имеют одинаковые значения. Вы определяете угол, сортируете их.
Это пример того, как я решил это решить. Он преобразуется в полярный, чтобы получить угол, а затем используется для их сравнения. Вы должны использовать это в сортировке, например:
std::sort(vectors.begin(), vectors.end(), VectorComp(centerPoint));
Ниже приведен код для сравнения
struct VectorComp : std::binary_function<sf::Vector2f, sf::Vector2f, bool>
{
sf::Vector2f M;
IntersectComp(sf::Vector2f v) : M(v) {}
bool operator() ( sf::Vector2f o1, sf::Vector2f o2)
{
float ang1 = atan( ((o1.y - M.y)/(o1.x - M.x) ) * M_PI / 180);
float ang2 = atan( (o2.y - M.y)/(o2.x - M.x) * M_PI / 180);
if(ang1 < ang2) return true;
else if (ang1 > ang2) return false;
return true;
}
};
Он использует sfml-библиотеку, но вы можете переключить любой векторный/точечный класс вместо sf:: Vector2f. M будет центральной точкой. Он отлично работает, если вы хотите каким-то образом нарисовать поклонник треугольника.
Я знаю, что этот вопрос довольно старый, и принятый ответ помог мне дойти до этого, но я думаю, что у меня есть более элегантное решение, которое также охватывает равенство (так что возвращает -1 для lowerThan, 0 для equals и 1 для moreThan).
Он основан на делении плоскости на две половинки, одну от положительной оси ref (включительно) до отрицательной оси рефлекса (исключая), а другая - ее дополнение.
Внутри каждой половины сравнение может выполняться по правилу правой руки (знак перекрестного произведения), или, другими словами, знак синуса угла между двумя векторами. Если 2 точки приходят из разных половинок, то сравнение тривиально и выполняется между половинами.
Для адекватно равномерного распределения этот тест должен выполнять в среднем 4 сравнения, 1 вычитание и 1 умножение, кроме 4 вычитаний, сделанных с помощью ref, что, на мой взгляд, должно быть предварительно рассчитано.
int compareAngles(Point const & A, Point const & B, Point const & ref = Point(0,0)) {
typedef decltype(Point::x) T; // for generality. this would not appear in real code.
const T sinA = A.y - ref.y; // |A-ref|.sin(angle between A and positive ref-axis)
const T sinB = B.y - ref.y; // |B-ref|.sin(angle between B and positive ref-axis)
const T cosA = A.x - ref.x; // |A-ref|.cos(angle between A and positive ref-axis)
const T cosB = B.x - ref.x; // |B-ref|.cos(angle between B and positive ref-axis)
bool hA = ( (sinA < 0) || ((sinA == 0) && (cosA < 0)) ); // 0 for [0,180). 1 for [180,360).
bool hB = ( (sinB < 0) || ((sinB == 0) && (cosB < 0)) ); // 0 for [0,180). 1 for [180,360).
if (hA == hB) {
// |A-ref|.|B-ref|.sin(angle going from (B-ref) to (A-ref))
T sinBA = sinA * cosB - sinB * cosA;
// if T is int, or return value is changed to T, it can be just "return sinBA;"
return ((sinBA > 0) ? 1 : ((sinBA < 0) ? (-1) : 0));
}
return (hA - hB);
}
Если S - это массив PointF, а mid - это PointF в центре:
S = S.OrderBy(s => -Math.Atan2((s.Y - mid.Y), (s.X - mid.X))).ToArray();
отсортирует список в порядке поворота вокруг середины, начиная с точки, ближайшей к (-inf, 0), и перейдет по часовой стрелке (по часовой стрелке, если вы опустите отрицательный знак перед математикой).