Я адаптировал монотонный цепной алгоритм Андерсона для поиска выпуклой оболочки, но после этого обнаружил, что результирующие точки расположены в порядке x, а не в порядке карусели. Существует ли алгоритм выпуклой оболочки, который генерирует точки в порядке карусели, то есть по порядку по периметру оболочки?
Это моя реализация монотонной цепочки, которая не удовлетворяет мою проблему:
// monotone chain
public static ComparablePoint[] convex_hull( ComparablePoint[] points ){
if( points.length > 1 ){
int ctPoints = points.length;
int k = 0;
ComparablePoint[] hull = new ComparablePoint[ 2 * ctPoints ];
java.util.Arrays.sort( points );
// Build lower hull
for (int i = 0; i < ctPoints; ++i) {
while (k >= 2 && crossProduct(hull[k - 2], hull[k - 1], points[i]) <= 0)
k--;
hull[k++] = points[i];
}
// Build upper hull
for (int i = ctPoints - 2, t = k + 1; i >= 0; i--) {
while (k >= t && crossProduct(hull[k - 2], hull[k - 1], points[i]) <= 0)
k--;
hull[k++] = points[i];
}
if (k > 1) {
hull = java.util.Arrays.copyOfRange(hull, 0, k - 1); // remove non-hull vertices after k; remove k - 1 which is a duplicate
}
return hull;
} else if( points.length <= 1 ){
return points;
} else{
return null;
}
}
Чтобы было ясно, что я имею в виду под порядком карусели: точки на выпуклой оболочке находятся в периметре, который является выпуклым многоугольником. Мне нужно, чтобы эти точки были в порядке, когда вы идете по периметру многоугольника.
Алгоритм монотонной цепочки, показанный выше, этого не делает, он возвращает точки в порядке их координаты x. Точка с самой низкой координатой x является первой, затем точка со второй самой низкой координатой x и так далее.
