Максимум коллинеарных точек на плоскости

Question

N баллов приведены в качестве входных данных.

Допустим, (x1,y1), (x2,y2)... (xn,yn).

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

Answer 1

Для каждой точки i найдите наклон к любой другой точке j и искать дубликаты. Дубликаты могут быть найдены путем сортировки склонов и сравнивая смежные значения. Точка I является коллинеарной с точками в каждый набор дубликатов. Следите за максимальным набором на ходу.

Для каждого i у вас есть n-1 наклон для расчета, сортировки и сравнения. Следовательно, используя (n log n) сортировку, сложность алгоритма O (n ^ 2 log n).

Answer 2

Прочитайте обсуждение по этому вопросу здесь на

Answer 3

Следующее может быть одним из способов ее решения: 1) Найти все уклоны, выбрав C (n, 2) пары 2) Сложить эти уклоны в несколько сегментов.3) Внутри этих сегментов найдите независимые линии (так как они могут содержать семейство параллельных линий). 4) Установите самый длинный отрезок линии

Более конкретно: 1) Выполните (n-1) * (n-1) вычисления, чтобынайти так много склонов.Карта может быть использована для сохранения этих точек с уклонами в качестве ключей.Значение на карте может быть представлено с помощью набора.Набор может содержать объект, представляющий две точки.Примерно так: {slope1: [(p1, p2), (p1, p3), (p1, p2), (p4, p5)]} {slope2: ....}

2) Сейчас, внутри каждого набора точек найти независимые линии.Я считаю, что итерации по каждой точке в наборе, мы можем прийти к этому.Например, при посещении (p1, p2), (p1, p3), (p1, p2), (p4, p5) мы можем разделить это на n-множества, которые образуют коллинеарные точки.Набор может начинаться с: [p1, p2], когда мы встречаем следующую пару (p1, p3), мы проверяем, есть ли какие-либо из них уже в текущем наборе.Если хотя бы один из них есть, мы добавляем новые точки в этот набор, в противном случае создаем новый набор.После итерации по всем точкам в этом наборе точек у нас будут два следующих набора, представляющих 2 независимых отрезка линии: [p1, p2, p3] [p4, p5] Размер их теперь можно использовать для определения самого длинного отрезка линиимы находим

Сложность, она должна быть O ((n-1) * (n-1) + n) ~ O (n ^ 2).Предполагается, что поиск объектов в Set равен O (1)