Сортировка точек по их полярному углу в Java

Я использую алгоритм сканирования Грэма для поиска выпуклой оболочки множества точек Я пытаюсь сортировать точки по их полярному углу, но я понятия не имею, как это сделать (Я уже отсортировал набор точек по их координатам Y).Сортировка точек по их полярному углу в Java

То, что я уже писал, как это:

public double angle(Coord o, Coord a) 
{ 
    return Math.atan((double)(a.y - o.y)/(double)(a.x - o.x)); 
}

где Coord класс, где у меня есть X и Y координаты в double.

Я также посмотрел на одну из подобных записей в Stack Overflow, где кто-то пытался реализовать этот угол с C++, но я не понимаю qsqrt. У нас есть что-то подобное на Java?

qreal Interpolation::dp(QPointF pt1, QPointF pt2) 
{ 
    return (pt2.x()-pt1.x())/qSqrt((pt2.x()-pt1.x())*(pt2.x()-pt1.x()) + (pt2.y()-pt1.y())*(pt2.y()-pt1.y())); 
}

Буду рад, если кто-нибудь сможет мне помочь.

источник

2013-05-12 Navid Koochooloo

Вам не нужно рассчитать полярный угол для сортировки по нему. Поскольку триг-функции монотонны (всегда увеличиваются или всегда уменьшаются) внутри квадранта, просто сортируйте по самой функции, например. загар в вашем случае. Если вы выполняете сканирование Graham, начиная с самой нижней точки, вам нужно всего лишь посмотреть на первые два квадранта, поэтому было бы проще отсортировать по котану, так как он монотонен для обоих квадрантов.

Другими словами, вы можете просто сортировать по - (x - x1)/(y - y1) (где (x1, y1) - координаты начальной точки), которые будут быстрее вычисляться. Сначала вам нужно будет выделить точки, где y == y1, конечно, и добавить их в верхнюю или нижнюю часть списка в зависимости от знака (x - x1) `, но их легко идентифицировать, поскольку вы уже отсортировано по y, чтобы найти отправную точку.

источник

2013-05-12 16:36:53 maybeWeCouldStealAVan

и что я должен использовать в java, чтобы найти формулу для котана? просто замените мой код на: открытый двойной угол (координата o, координата a) { return 1.0/Math.tan ((double) (a.y - o.y)/(double) (a.x - o.x)); } –

для начала, каждый, где написано другое. имеет значение, с чего начать? –

'(x - x1)/(y - y1)' - это формула для cotan (1/tan) - смежная над противоположной. Я сделал только отрицательный, чтобы он увеличивался с углом. Я не слышал о сканировании Грэма, поэтому я основывал свой ответ на статье в Википедии, в которой предлагается начать с самой нижней точки. Идея не изменилась бы, если бы вы начали, скажем, с самой левой точки. В этом случае было бы проще использовать касательную: '(y - y1)/(x - x1)' – maybeWeCouldStealAVan

Math.atan() возвращает угол между -pi/2 до pi/2. Вам нужно будет скорректировать результаты для двух других координат.

Если вам нужен угол от центра выпуклого корпуса, вам нужно сначала перевести координаты так, чтобы centroid был источником.

источник

2013-05-12 15:58:45

Как уже упоминалось выше, вычисление самого полярного угла является довольно неряшливым способом перемещения вещей. Вы можете определить простой компаратор и использовать кросс-продукты для сортировки по полярному углу. Вот код в C++ (который я использую для моего Graham сканирования):

struct Point { 
    int x, y; 
} 

int operator^(Point p1, Point p2) { 
    return p1.x * p2.y - p1.y * p2.x; 
} 

bool operator<(Point p1, Point p2) 
{ 
    if(p1.y == 0 && p1.x > 0) 
     return true; //angle of p1 is 0, thus p2 > p1 

    if(p2.y == 0 && p2.x > 0) 
     return false; //angle of p2 is 0 , thus p1 > p2 

    if(p1.y > 0 && p2.y < 0) 
     return true; //p1 is between 0 and 180, p2 between 180 and 360 

    if(p1.y <0 && p2.y > 0) 
     return false; 

    return (p1^p2) > 0; //return true if p1 is clockwise from p2 
}

Вы можете реализовать то же самое в Java, определив Point класс. В основном я перегрузил оператора ^, чтобы вернуть крест продукта. Остальное очевидно, надеюсь, что это поможет!

источник

2013-06-11 16:29:30 akshat

Сортировка точек по их полярному углу в Java

ответ

Смежные вопросы