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

Это вопрос : "Найти все коллинеарные точки в заданном наборе".

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

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

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

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

Ответ 1

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

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

// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// 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); 
  }
}

Ответ 2

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

Вы уверены, что ваш анализ среды выполнения верен? Вы говорите, чтобы перебрать все пары точек, из которых 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) вообще. Однако полное доказательство этого факта может быть нетривиальным.

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