Нахождение площади четырехугольников по координатам

#c #координаты

На плоскости задано n точек с координатами x[n], y[n]. Нужно найти четверки точек,
составляющие четырехугольник наибольшей площади. 

Я написал такой код, который проверяет все возможные комбинации точек, считает площадь
по формуле Гаусса и находит максимальную площадь. Естественно, точек должно быть не
меньше 4. 

for (i = 0; i < n - 3; i++)
            for (j = 1; j < n - 2; j++)
                for (k = 2; k < n - 1; k++)
                    for (l = 3; l < n; l++)
                    {
                        s = fabs(((x[i] * y[j] - y[i] * x[j]) + (x[j] * y[k] - y[j]
* x[k]) + (x[k] * y[l] - y[k] * x[l]) + (x[l] * y[i] - y[l] * x[i])) / 2.0);
                        if (s > max) max = s;
                    }


И всё бы хорошо, но площадь упорно равна нулю. Подскажите, что я делаю не так. Может
проблема в последовательности ввода координат точек? Есть ли другой способ вычисления
площади по координатам?
    

Ответы

Ответ 1

Площадь по данным четырем точкам у вас вычисляется правильно. 

Если уж вы взялись решать задачу полным перебором, то вам нужно перебирать все возможные
комбинации из четырех различных точек во всех относительных порядках. То есть в самом
"брутальном" варианте циклы должны выглядеть примерно так

for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
    if (j != i)
      for (k = 0; k < n; k++)
        if (k != i && k != j)
          for (l = 0; l < n; l++)
            if (l != i && l != j && l != k)
              /* Проверяем площадь */;


У вас же наблюдается какое-то странное неоправданное исключение некоторых вариантов,
но при этом нет никакой защиты от того, что одна и та же точка может быть взята несколько
раз. Например, в вашем наборе ( i, j, k, l ) точка 0 может быть только первой, а точка
n-1 - только последней. То есть вариант ( 0, j, n-1, l ) вы никогда не рассмотрите.
На каком основании вы исключили такие четырехугольники из рассмотрения?

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

Для исключения из рассмотрения циклических сдвигов достаточно обеспечить, чтобы каждый
рассматриваемый набор начинался со своего минимального элемента. Для исключения из
рассмотрения зеркальных отражений достаточно обеспечить, чтобы в перестановке (j, k,
l) содержалось не более одной инверсии 

for (i = 0; i < n - 3; i++)
  for (j = i + 1; j < n; j++)
    for (k = i + 1; k < n; k++)
      if (k != j)
        for (l = i + 1; l < n; l++)
          if (l != j && l != k)
            if ((j > k) + (k > l) + (j > l) <= 1)
              /* Проверяем площадь */;


Например, на наборе из 5 точек такой перебор проверит только 15 вариантов, в то время
как полный перебор проверит 5! = 120 вариантов. На наборе из 6 точек - 45 вместо 720.



Однако эта задача имеет и эффективное решение. Оно начинается из построения выпуклой
оболочки для вашего набора точек. 

Если выпуклая оболочка имеет четыре или более вершин, то точки, не лежащие на выпуклой
оболочке исключаются из дальнейшего рассмотрения. А дальше несложный "поворотный" алгоритм
найдет четырехугольник максимальной площади без полного перебора.

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