Найти треугольники с максимальной площадью

[timaslov]

Задача: Дано 3n точек на плоскости, причем никакие три из них не лежат на одной прямой. Построить множество n треугольников с вершинами в этих точках так, чтобы никакие два треугольника не пересекались и не содержали друг друга, а суммарная площадь этих треугольников была максимальной.
Пытаюсь найти правильный подход к задачке.
Я начал решать в лоб: сначала прохожусь по всем точкам и записываю в двумерный массив все возможные треугольники.
То есть если дано 6 точек, то начало массива будет выглядеть так: [[0,1,2], [0,1,3], [0,1,4], [0,1,5], [0,2,3], [0,2,4], и т.д., где цифры в массиве - это индексы известных нам точек. Для 6 точек получается 20 разных треугольников. Для 9 точек - 84 треугольника и т.д.
Далее нужно, насколько я понимаю, сравнить каждый треугольник с каждым, чтобы выявить, какие 2 треугольника (в случае 6 точек) имеют наибольшую площадь и при этом не пересекаются. (в случае 9и точек нужно сравнить все тройки треугольников и т.д.) Я это реализую с помощью рекурсивной функции и получается, что для 20 треугольников будет 190 итераций (комбинаторика, сочетания из двадцати по два).
Но проблема в том, что если точек будет 9, то будет 84 возможных треугольника и уже 95284 итераций (84 по 3) и для 12 точек будет 220 треугольников и 94.966.795 итераций (220 по 4). А 15 точек программа уже вовсе не посчитает за адекватное время.
И вот проблема в том, что программа не должна крашиться уже на 15ти точках.
Я понимаю, что такой подход, по всей видимости, неправильный, но иного решения пока в голову не пришло
Не кидаю код, потому что прошу подсказать именно подход к задаче

[сфинкс]

Программа рассчитывает площади N 3-угольников
причём в автокад autocad совместимой программе проверил: правильно

N = 5: DIM x(N,4),y(N,4),d(N,4),s(N): RANDOMIZE TIMER '3ki.bas
FOR i = 1 TO N: FOR j = 1 TO 3
        x(i,j) = INT(RND * 9)+1: y(i,j) = INT(RND * 9)+1
NEXT: x(i,4) = x(i,1): y(i,4) = y(i,1): NEXT

FOR i = 1 TO N: FOR j = 1 TO 3: ' PRINT i,j
        d(i,j) = SQR((x(i,j+1)-x(i,j))^2+(y(i,j+1)-y(i,j))^2) ': PRINT d(i,j)
NEXT: NEXT

FOR i = 1 TO N
    p = (d(i,1)+d(i,2)+d(i,3))/2
    s(i) = SQR(p*(p-d(i,1))*(p-d(i,2))*(p-d(i,3)))
    PRINT x(i,1); y(i,1),x(i,2); y(i,2),x(i,3); y(i,3),s(i)
NEXT

из qb64 qbasic на другие языки переводим сами

чтобы перейти от N 3-угольников ко всем 3-кам из N точек
видимо нужно поменять циклы наверняка оставив принцип
x(т.1,т.2,т.3), y(т.1,т.2,т.3) d(т.1,т.2,т.3) и массив площадей

формула подсчёта 3-ков из N точек: K=N*(N-1)*(N-2)/(3*2*1)
Значит для 15: K=15*(15-1)*(15-2)/(3*2*1) =455 вариантов

[BDA]

Выскажу свои мысли (правильного решения не знаю). Предположу, что треугольники не могут иметь общих вершин, иначе они считаются пересекающимися. Также предлагаю сразу строить список из N треугольников, при этом каждый следующий треугольник строится только из еще незадействованных вершин (рекурсивно брать вершину с наименьшим номером и еще две других в порядке возрастания). Тогда (если верно посчитал):

N - кол-во вариантов наборов треугольников
2 - 10
3 - 280
4 - 15400
5 - 1401400

Например, для N = 2:
(0, 1, 2), (3, 4, 5)
(0, 1, 3), (2, 4, 5)
(0, 1, 4), (2, 3, 5)
(0, 1, 5), (2, 3, 4)
(0, 2, 3), (1, 4, 5)
(0, 2, 4), (1, 3, 5)
(0, 2, 5), (1, 3, 4)
(0, 3, 4), (1, 2, 5)
(0, 3, 5), (1, 2, 4)
(0, 4, 5), (1, 2, 3)

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

[сфинкс]

3-угольники визуально из здешней моей темы 3-летней давности



найти 3-угольник наибольший за 1 проход:
сравнивать с отрицательной площадью

пересечение 3-ков небось из пересечения рёбер линий
у меня бэйсик qb64 qbasic код давно есть
на основе интернет подсказок но лучше ищите на форуме
ведь внизу похожие темы

[ViktorR]

... Построить множество n треугольников с вершинами в этих точках так, чтобы никакие два треугольника не пересекались и не содержали друг друга, ...

У меня возник вопрос к определению понятия "Пересечение".
С одной стороны поиск говорит о том, что фигуры пересекаются, если у них есть одна или более общих точек. С другой стороны утверждается, что фигуры могут соприкасаться, т.е. могут иметь одну и более общих точек, но не пересекаться.
В моём понимании, пересекающиеся фигуры должны иметь хота бы одну общую "внутреннюю" точку.
Иначе: два треугольника с общей вершиной или два треугольника с общей стороной. Это соприкасающиеся или пересекающиеся фигуры?
Принадлежать ли точки границы самой фигуре?
Во многих случаях это оговаривается отдельно или используются разные слова, например, круг и окружность.

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

PS: Осталось разобраться в том, насколько независимыми должны быть треугольники.

[сфинкс]

3-угольник 1-й: 3 стороны
3-угольник 2-й: 3 стороны
Проверить массивами пересечение всех сторон между собою =3*3 =9-жды

Подняв алгоритм пересечения прямых: там 3 результата

отрезки: пересекаются \ непересекаются \ совпадают
и когда точка на отрезке или в вершине другого отрезка: пересекаются

Однако возникнет новая головоломка: 3-ки вложенные 1 внутри другого

[ViktorR]

ViktorR

PS: Осталось разобраться в том, насколько независимыми должны быть треугольники.

Так понимаю, что ТС дал дёру.
Вопрос о том что треугольники могут соприкасаться по границе остался.
Можно ли считать пересечением соприкосновение?

чтобы никакие два треугольника не пересекались и не содержали друг друга

Что-то Сеть мне не помогла. Есть ли тот, кто может определить понятие "пересечение треугольников"?
Для себя понимаю так, что соприкасающиеся, т.е. имеющие общую границу или точку (вершину) объекты не пересекаются.
Пересечение, на мой взгляд, когда есть общие внутренние точки. Как довод - окрасьте треугольники.
Точки, принадлежащие границам треугольника не входят в его площадь.

[BDA]

ViktorR, не готов вести рассуждения о терминологии. Но если смотреть только на эту задачу, то при разрешённых соприкосновениях не было бы смысла давать 3N точек для построения N треугольников.

[evg_m]

1. не пересекались => не имеют НИ одной общей точки; ни общей вершины, ни единой точки(вершины) на стороне.
1.1. 3N точек --> N треугольников
1.2. никакие три точки не лежат на одной прямой => общих сторон (хотя бы частично) быть не может. и НИКАКАЯ вершина другого треугольника не лежит на стороне другого)

=> возможно только пересечение НЕ параллельных отрезков (сторон).

[digitalis]

Вообще задача, несмотря на простоту постановки, не проста. Хоть ТС и испарился, но вопрос заинтересовал и бывалых форумцев. Я так толкового алгоритма, кроме полного перебора, не вижу.