Самый большой четырехугольник из множества точек

Question

Самый большой четырехугольник из множества точек

Я ищу способ найти четырехугольник с самой большой площадью. Я уже вычислил точки выпуклой оболочки и отсортировал их по часовой стрелке. Я попробовал грубую силу, но, конечно, это слишком медленно. Итак, я нашел вот этот алгоритм для наибольшего треугольника:

Как найти самый большой треугольник в выпуклой оболочке, кроме поиска грубой силы

Это выглядит действительно красиво, поэтому я попытался переделать его. У меня есть функция, которая вычисляет площадь любого четырехугольника, деля его на два треугольника (в этой функции я сортирую входные точки, чтобы убедиться, что я вычисляю прямоугольные треугольники). Вот:

int n = convexHull.size();
int A = 0; int B = 1; int C = 2; int D = 3;
int bestA = A; int bestB = B; int bestC = C; int bestD = D;
while(true) { // loop A
while(true) { // loop B
while(true) { // loop C
while(quadrangleArea(A, B, C, D) <=  quadrangleArea(A, B, C, (D+1)%n) ) { // loop D
D = (D+1)%n;
}
if(quadrangleArea(A, B, C, D) <=  quadrangleArea(A, B, (C+1)%n, D) ) {
C = (C+1)%n;
continue;
}
else break;
}
if(quadrangleArea(A, B, C, D) <=  quadrangleArea(A, (B+1)%n, C, D) ) {
B = (B+1)%n;
continue;
}
else break;
}
if(quadrangleArea(A, B, C, D) >  quadrangleArea(bestA, bestB, bestC, bestD) ) {
bestA = A; bestB = B; bestC = C; bestD = D;
}
A = (A+1)%n;
if (A==B) B = (B+1)%n;
if (B==C) C = (C+1)%n;
if (C==D) D = (D+1)%n;
if (A==0) break;
}

Это выглядит хорошо и дает хорошие результаты для моих простых тестов, но я боюсь, что-то не так. Идя дальше с этим рассуждением, я мог бы создать алгоритм для каждого многоугольника с n вершинами — но, на мой взгляд, это невозможно. Я прав?

Я пытаюсь решить «ШАМАН» проблема со спой, и у меня неправильный ответ. Я на 99% уверен, что остальная часть моей программы в порядке, поэтому что-то не так с кодом выше. Не могли бы вы помочь мне улучшить это? Может быть, у вас есть несколько хитрых тестов, которые могут доказать, что этот алгоритм не работает должным образом? Буду благодарен за любые советы!

4

algorithm c++computational-geometry geometry

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я разделил бы выпуклую оболочку на две половины, нашел бы наибольший треугольник в каждой половине, вычислил сумму — и затем вращал бы «делитель» поперек выпуклой оболочки. Как это:

size_t n = convexHull.size();
size_t A = 0;
size_t B = n/2;
size_t C, D;
size_t maxarea = 0;
size_t area;
size_t maxQuad[4];

// size_t findLargestTriangle(convHullType c, int& tip);
//    make this search the hull "c" with the assumption
//    that the first and last point in it form the longest
//    possible side, and therefore will be base of the
//    triangle with the largest area. The "other" point
//    will be returned, as will be the size.
while (A < n/2 && B < n) {
// this is partially pseudocode, as you need to treat
// the container as "circular list", where indices wrap
// around at container.size() - i.e. would have
// to be container[n + x] == container[n]. No ordinary
// C++ std:: container type behaves like this but it's
// not too hard to code this.
// This simply says, "two sub-ranges".
area =
findLargestTriangle(convexHull[A..B], C) +
findLargestTriangle(convexHull[B..A], D);
if (area > maxarea) {
maxarea = area;
maxQuad = { A, B, A + C, B + D };
}
A++; B++;
}

Я не большой математик, и поэтому не совсем уверен (не могу доказать), вы можете повернуть A а также B все вместе как это. Надеюсь, что кто-то может восполнить этот пробел … всегда готов учиться сам 😉

0