Найти все коллинеарные точки в данном наборе

Question

Это вопрос для интервью : «Найти все коллинеарные точки в данном наборе».

Как я понимаю, они просят распечатать точки, которые лежат в одной строке(и каждые две точки всегда коллинеарны).Я бы предложил следующее.

1. Давайте введем два типа Line (пара чисел) и Point (пара целых чисел).
2. Создание мультикарты: HashMap<Line, List<Point>)
3. Обведите все пары точек и для каждой пары: вычислите Line, соединяющий точки, и добавьте линию с этими точками в мультикарту.

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

Сложность O (N ^ 2).Имеет ли это смысл ?Есть ли лучшие решения?

Answer 1

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

Может быть, лучший вопрос, каково максимальное количество коллинеарных точек в данном наборе?В этом случае вы можете зафиксировать 2 точки (просто используйте 2 контура), затем зациклить другие точки и убедиться, что наклон совпадает между фиксированными точками и другими точками.Вы можете использовать что-то подобное для этой проверки, предполагая, что координаты целочисленные (в противном случае вы можете изменить типы параметров на удвоенные).

// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Returns whether 3 points are collinear
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
bool collinear(int x1, int y1, int x2, int y2, int x3, int y3) {
  return (y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2);
}

Таким образом, логика становится такой:

int best = 2;
for (int i = 0; i < number of points; ++i) {
  for (int j = i+1, j < number of points; j++) {
    int count = 2;
    for (int k = 0; i < number of points; ++k) {
      if (k==i || k==j)
        continue;

      check that points i, j and k are collinear (use function above), if so, increment count.
    }
    best = max(best,count); 
  }
}

Answer 2

решить задачу в двухплоскостной плоскости, преобразовать все точки в отрезки.А затем запустите самолет, чтобы доложить обо всех перекрестках.Линии в двойной плоскости будут проходить через одну и ту же точку, представляющую коллинеарные точки.И зачистка самолета может быть выполнена за O (nlogn) время.

Answer 3

Взгляните на два метода, описанных в http://www.cs.princeton.edu/courses/archive/spring03/cs226/assignments/lines.html.

Чтобы найти 4 или более коллинеарных точек по данным N точкам, метод грубой силы имеет временную сложность O (N ^ 4), но лучший метод делает это в O (N ^ 2 log N).

Answer 4

Вы уверены, что ваш анализ времени выполнения правильный? Вы говорите, чтобы перебрать все пары точек, из которых есть n * (n-1) / 2, то есть O (n ^ 2). Затем вы добавляете линию и пару точек на карту. Однако я не думаю, что время для добавления такой комбинации линия + точка является постоянным. Это означает, что в целом ваше время равно O (n ^ 2 log n), а не постоянному времени n ^ 2, что означает значение O (n ^ 2).

Таким образом, реальный вопрос заключается в том, что это можно сделать за время O (n ^ 2 log n), можно ли это сделать за время O (n ^ 2). Ясно, что O (n ^ 2) дает нижнюю границу, так как вы должны как минимум распечатать каждую пару точек, из которых есть O (n ^ 2). У меня такое чувство, что это совершенно общая проблема сортировки, которую нельзя ожидать лучше, чем O (n ^ 2 log n) в целом. Однако полное доказательство этого факта может быть нетривиальным.

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

Answer 5

Я думаю, что цель состоит в том, чтобы найти линию, которая проходит через максимальное количество точек или идентифицировать этот набор коллинеарных точек.Эта ссылка дает N ^ 2 (logN) решение этой проблемы