2
Я использую этот алгоритм для сортировки списка точки по часовой стрелке:сортировка Vertices по часовой стрелке
private List<Point2D> SortClockWise(List<Point2D> Points) {
// First Calculate Center of Points
double CenterX = 0;
double CenterY = 0;
for (int i = 0; i < Points.size(); i++) {
CenterX += Points.get(i).getX();
CenterY += Points.get(i).getY();
}
Point2D Center = new Point2D(CenterX/Points.size(), CenterY
/Points.size());
int n = Points.size();
int k;
for (int m = n; m >= 0; m--) {
for (int i = 0; i < n - 1; i++) {
k = i + 1;
if (!less(Points.get(i), Points.get(k), Center)) {
Point2D tmp = new Point2D();
tmp = Points.get(i);
Points.set(i, Points.get(k));
Points.set(k, tmp);
}
}
}
for (int i = 0; i < Points.size(); i++) {
mTempShape.add(Points.get(i));
}
return mTempShape;
}
private Boolean less(Point2D a, Point2D b, Point2D center) {
if (a.getX() - center.getX() >= 0 && b.getX() - center.getX() < 0)
return true;
if (a.getX() - center.getX() < 0 && b.getX() - center.getX() >= 0)
return false;
if (a.getX() - center.getX() == 0 && b.getX() - center.getX() == 0) {
if (a.getY() - center.getY() >= 0 || b.getY() - center.getY() >= 0)
return (a.getY() > b.getY());
return b.getY() > a.getY();
}
// compute the cross product of vectors (center -> a) x (center -> b)
double det = (a.getX() - center.getX()) * (b.getY() - center.getY())
- (b.getX() - center.getX()) * (a.getY() - center.getY());
if (det < 0)
return true;
if (det > 0)
return false;
// points a and b are on the same line from the center
// check which point is closer to the center
double d1 = (a.getX() - center.getX()) * (a.getX() - center.getX())
+ (a.getY() - center.getY()) * (a.getY() - center.getY());
double d2 = (b.getX() - center.getX()) * (b.getX() - center.getX())
+ (b.getY() - center.getY()) * (b.getY() - center.getY());
return d1 > d2;
}
проблема в некоторых случаях, как это:
алгоритм дает мне BlackLine Нарисовано на картинке, Но то, что я хочу получить, - это нумерованные вершины на картинке.
Черная линия выглядит как правильное ожидаемое поведение для меня. Точки были расположены по часовой стрелке по кругу (или, по крайней мере, как можно ближе к этому). Единственный способ, которым я вижу, что он способен получить то, что вы хотите, - это то, что «Центр» был точкой где-то посреди треугольника 7-3-6. Но это только в этом случае - я думаю, что для некоторых других форм никакой «Центр» не сработает. Таким образом, вам, вероятно, нужен совершенно другой, более сложный алгоритм, который осознает роль точек как вершин формы, а не как местоположения. Как отображается форма в настоящее время? –
Ваш центр расположен где-то выше точки 3 (такая же координата x). Это делает правильную сортировку для этого центра. – fabian
да сортировка правильная для этого алгоритма, но я хочу знать, как я могу получить результат, который я хочу –