В наборе n точек есть (n выберите 3) треугольников, и использование грубой силы, чтобы проверить для каждой точки, содержится ли она в каждом треугольнике, действительно имеет O(n 4 ) сложность.Чтобы привести практический пример нескольких наборов размеров:
points: 100 1,000 10,000
triangles: 161,700 166,167,000 166,616,670,000
checks: 15,684,900 165,668,499,000 1,665,666,849,990,000
Ниже приведены несколько геометрических идей;они не ведут прямо к решению, но они могут уменьшить количество треугольников, которые должны быть проверены.
Контрпример для выпуклой оболочки
Прежде всего, использование только точек на выпуклой оболочке не гарантирует оптимального решения.Рассмотрим этот контрпример:
Выпуклая оболочка - красный прямоугольник.Однако, если мы используем две его стороны и диагональ для формирования треугольника, диагональ прорежет кластер центральной точки и пропустит некоторые из точек.И даже если мы используем только 1 или 2 угла прямоугольника в сочетании с точкой в центре, он всегда будет прорезать синий треугольник и пропустить некоторые точки.Синий треугольник, у которого нет точек на выпуклой оболочке, фактически является оптимальным решением.
Треугольник, содержащийся в треугольнике
Если рассматривать треугольник abc и три точки d , e и f , содержащиеся в нем, тогда треугольник def не может быть треугольником, который содержит наибольшее количество точек, поскольку треугольник abc содержит как минимум еще три точки,Треугольники, сделанные из комбинации точек из abc и def , как abd , также содержат меньше точек, чем abc .
Это означает, что обнаружение треугольника и некоторых точек, содержащихся в нем, позволяет отбросить количество треугольников.В следующих параграфах мы будем использовать эту идею, чтобы отбросить как можно больше треугольников от необходимости проверять.
Расширение треугольника
Если мы рассмотрим треугольник, состоящий из трех случайно выбранных точек a , b и c (названный по часовой стрелке), а затем проверьте, все ли остальные точки находятся слева от правой стороны линий | ab | , | bc | и | ca | , точки разбиты на 7 зон:
Если мы заменим угловую точку треугольника точкойв смежной цветной зоне, например, зоне LRL для точки a , мы получаем больший треугольник, который содержит треугольник abc .Если мы случайным образом выберем три точки из зон LRL, LLR и RLL, мы можем расширить треугольник следующим образом:
Затем мы можем снова разделить точкииспользуя этот новый треугольник a'b'c ' (точки, уже находящиеся в зоне RRR, можно добавить в новую зону RRR без проверки) и снова разверните треугольник, если в зонах есть хотя бы одна точкаLRL, LLR или RLL.
Если мы поймали достаточно точек внутри расширенного треугольника, мы можем теперь использовать алгоритм грубой силы, но пропустить любой треугольник, который не имеетточка за пределами расширенного треугольника a'b "c '.
Если мы не поймали достаточно точек, чтобы сделать это возможным, мы можем повторить попытку с другими тремя случайными точками. Примечаниеоднако вам не следует использовать объединение точек, содержащихся в нескольких треугольниках: три точки, каждая из которых содержится в другом треугольнике, но не в одном и том же, могут быть треугольником, содержащим наибольшее количество точек.
Исключая треугольники в несколько шагов
Мы могли бы многократно выбрать случайный треугольник, максимально расширить его, а затем отметить треугольники, сделанные из трех точек на или внутри треугольника, чтобы затем исключить их изпроверка. Это потребует сохранения логического значения для всех возможных треугольников, например, в трехмерном битовом массиве, так что это возможно только для наборов донесколько тысяч баллов.
Чтобы упростить вещи, вместо расширения случайных треугольников, мы могли бы сделать это с помощью ряда случайно выбранных треугольников, или треугольников, составленных из точек на выпуклой оболочке, или точек, расположенных далеко друг от друга при сортировке в направлении x или y, или ... Но любой из этих методов только поможет нам найти треугольники, которые могут быть исключены, они не дадут нам оптимальные (или даже достаточно хорошие) треугольники сами по себе.