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

#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.



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

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

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

Работа с DXF. Python (Сортировка координат от точки отсчета)

#python #сортировка #координаты #autocad

Есть файл DXF, написал функцию, которая получает координаты каждой точки в таком формате:

[
     [0.0, 0.0, 0.0, 0.0, 10.0, 0.0],
     [0.0, 10.0, 0.0, 15.0, 10.0, 0.0],
     [15.0, 10.0, 0.0, 15.0, 10.0, 5.0],
     [15.0, 10.0, 5.0, 15.0, 13.0, 5.0]
]


Код:

def getCoordinates(key):
    # Функция получает координаты XYZ, по ключу # "AcDbLine\n" - линия, "AcDbPoint\n"
- точка
    ind = []
    CoordList = []
    for n, e in enumerate(ll):
        if key in e:
            ind.append(n)
    for sp in ind:
        a = ll[sp + 2:sp + 13]
        try:  # Если это линия, то взять координаты начальной и конечно точек
            CoordList.append([float(a[0]), float(a[2]), float(a[4]), float(a[6]),
float(a[8]), float(a[10])])
        except:  # Если это точка, то взять координаты точки
            CoordList.append([float(a[0]), float(a[2]), float(a[4])])
    return CoordList


Также в этом файле указана точка, это точка, с которой необходимо начинать отсчет.
Координаты точки тоже получил [15.0, 13.0, 5.0]

Попытался создать словарь типа 1:[координаты линии] но удалось только получить линию,
на которой стоит точка и то не корректно работает.

Вот код:

for num, el in enumerate(getCoordinates("AcDbLine\n")):
    try:
        point = getCoordinates("AcDbPoint\n")[0]  # Получает координаты точки для
сравнения

    except IndexError:  # Если точка не найдена, прекратить дальнейшие действия
        print ("Точка отсчета не найдена")
        break

    if point == el[:3] or point == el[4:]:  #Если координаты точки совпадают с линией
        D[1] = [el, GetLength("AcDbLine\n", num)]  # Первая линия, которая совпадает
с точкой имеет индекс 1


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

Для большей наглядности нарисовал  рисунок. Красными цифрами указан порядок, который
необходимо получить.

Может я все не правильно делаю и кто предложит решение более лучшее?


Так в DXF выглядит точка

AcDbPoint
 10
15.0
 20
13.0
 30
5.0
  0


а так линия

AcDbLine
 10
15.0
 20
10.0
 30
5.0
 11
15.0
 21
13.0
 31
5.0
  0


Точка как отдельный элемент и ставится вручную точно также как рисуется линия
    

Ответы

Ответ 1

Попробуйте так:

def to_my_dict():
    prev_point = getCoordinates("AcDbPoint\n")
    if prev_point:
        point = prev_point[0]
    else:
        return "Точка отсчета не найдена"
    my_dict = {}
    all_lines = getCoordinates("AcDbLine\n")
    count = 1
    line_count = len(all_lines)
    while line_count:
        for el in all_lines:
            if point == el[:3] or point == el[3:]:
                my_dict[count] = el  # линия, в которой есть точка 
                count += 1
                line_count -= 1

                if point == el[:3]:
                    point = el[3:]
                else:
                    point = el[:3]
    return my_dict

print(to_my_dict())


Возможно я не совсем правильно Вас понял, если это не то, что нужно - оставьте коментарий
и поясните вопрос более детально

Как получить координаты видимой части элемента относительно окна?

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

Получаю координаты элемента способом getBoundingClientRect() rect.top, rect.right,
rect.bottom, rect.left, но как на JS получить координаты видимой части элемента? Когда
часть элемента находится за пределами экрана.


    

Ответы

Ответ 1

Как говорил Эйнштейн: "Всё относительно"

Вам нужно получить координаты видимой части элемента только с учетом того, что элемент
может не помещаться в родителя?

Тогда допустим ваш элемент "хранится" в переменной e1. Берем e1.getBoundingClientRect(),
потом берем e1.parentNode.getBoundingClientRect() и находим максимальные значения left
и top, а также минимальные у right и bottom. Это и есть видимая часть относительно
непосредственного родителя.

Дальше хуже. Непосредственный родитель вашего элемента может не помещаться в своего
родителя или может быть смещен так, что его часть (и, может быть, часть вашего элемента)
не видна. Это не страшно, берем всех родителей вплоть до document.documentElement и
среди них находим максимальные и минимальные значения соответствующих параметров. Но
бывают еще абсолютно позиционированные элементы и элементы с фиксированным положением
относительно окна браузера. Они могут находиться в иерархии документа где угодно. Часть
из них может быть скрыта или прозрачна и это нужно учитывать при обнаружении "окна
видимости". С этим придется бороться только путем перебора всех элементов (ну пожалуй
кроме дочерних, хотя нет, есть же z-index)

Наконец ваш элемент может сидеть в