Как разделить несколько пересекающихся прямых?

[Igor_Dmitriev]

Допустим, есть массив, каждый элемент которого - точка (x, y). Предполагается, что этот массив состоит из нескольких прямых линий + шум. Как выделить эти прямые линии?

Первое, что приходит в голову:

1. Построить МНК, взять среднюю прямую, отбросить сильно далёкие от неё точки
2. То же самое проделать с оставшимися точками.
3. Повторять (2), пока не получим устраивающую прямую.
4. Полученную прямую убрать из массива, вернуться к (1).

Есть ли более удачные варианты?
Находит ли этот алгоритм лучшее или одно из лучших решений?

[dsge]

1. Упорядочить $x_i$ по возрастанию.
2. Построить 2 прямые с помощью МНК для точек $(x_i,y_i), i=1,...,k$ и $(x_i,y_i), i=k+1,...,N$, соответственно, $k=N/4$.
3. Подсчитать сумму квадратов ошибок для всех точек $(x_i,y_i), i=1,...,N$.
4. Повторить 2. и 3. для $k=j, j=1,..., N/2$.
5. Выбрать $k$ с наименьшей суммой квадратов.

6. Повторить 1.- 5. для 3-х, 4-х, и т.д. прямых.

[Skeptic]

Прямые с их координатами записаны в массиве последовательно?
Или есть массив координат точек, и из этого массива надо выделить пересекающиеся прямые?

[Pavia]

Igor_Dmitriev

Igor_Dmitriev в сообщении #959528 писал(а):

Находит ли этот алгоритм лучшее или одно из лучших решений?

Очевидно что нет. Так как он не ищет решения.

Igor_Dmitriev в сообщении #959528 писал(а):

Есть ли более удачные варианты?

Конечно есть, так как 1 пункт у вас явно не работает. Рассмотрите случай квадрата или решётки.

Igor_Dmitriev в сообщении #959528 писал(а):

Как выделить эти прямые линии?

Читать про методы векторизации.
Достаточно построить скелет. Далее найти в нём узлы, которые имеют более 2-х соседей.

dsge

dsge в сообщении #959542 писал(а):

5. Выбрать $k$ с наименьшей суммой квадратов.

Взять от числа $k$ сумму не возможно в принципе.
И тоже самое не понятно как ваш алгоритм пройдет тест с квадратом или решёткой.

[dsge]

Pavia в сообщении #959558 писал(а):

dsge в сообщении #959542
писал(а):
5. Выбрать $k$ с наименьшей суммой квадратов.
Взять от числа $k$ сумму не возможно в принципе.

Следует понимать как:
Выбрать (а не взять от числа $k$) $k$, соответствующий наименьшей сумме квадратов ошибок. Другими словами, найти такое $k$ перебором, что сумма квадратов ошибок будет минимальна.

Pavia в сообщении #959558 писал(а):

И тоже самое не понятно как ваш алгоритм пройдет тест с квадратом или решёткой.

Какие решетки? ТС надо построить прямые.

[Igor_Dmitriev]

Цитата:

Прямые с их координатами записаны в массиве последовательно?

Нет.

Цитата:

Или есть массив координат точек, и из этого массива надо выделить пересекающиеся прямые?

Да.

dsge в сообщении #959542 писал(а):

1. Упорядочить $x_i$ по возрастанию.
2. Построить 2 прямые с помощью МНК для точек $(x_i,y_i), i=1,...,k$ и $(x_i,y_i), i=k+1,...,N$, соответственно, $k=N/4$.
3. Подсчитать сумму квадратов ошибок для всех точек $(x_i,y_i), i=1,...,N$.
4. Повторить 2. и 3. для $k=j, j=1,..., N/2$.
5. Выбрать $k$ с наименьшей суммой квадратов.

6. Повторить 1.- 5. для 3-х, 4-х, и т.д. прямых.

А если часть точек прямой находится в начале массива, другая часть - в конце?

[Skeptic]

Координаты $x$ у всех прямых совпадают?

[Igor_Dmitriev]

Могут совпадать, могут не совпадать.

[dsge]

Igor_Dmitriev в сообщении #959818 писал(а):

А если часть точек прямой находится в начале массива, другая часть - в конце?

В смысле, что на концах данные описываются одной прямой, а посередине другой?

[Skeptic]

В задаче нечётко определены прямые.
Например. Даны координаты четырёх точек. Через эти точки можно провести шесть прямых. Какие прямые удовлетворяют условиям задачи?

[provincialka]

Хотя бы известно, сколько их?

[dsge]

dsge в сообщении #959542 писал(а):

4. Повторить 2. и 3. для $k=j, j=1,..., N/2$.

Отпечатка. Следует читать: Повторить 2. и 3. для $k=N/4+j$, $j=1,..., N/2$.

[Igor_Dmitriev]

Сколько их - неизвестно, предположительно, от 5 до 10.
Также неизвестно, какие точки какой прямой принадлежат.

Выбирая решение при числе прямых, равном 5, 6, 7, 8, 9, 10, собираюсь найти наилучшее.

[provincialka]

Igor_Dmitriev
Можно попробовать для каждой пары точек найти параметры проходящей через них прямой (особенно угол наклона, раз речь идет о пересечении). И сгруппировать их в 5 (6, 7, ...10) "похожих".

Если учитывать один параметр - $k_{ij}$, то просто разбить все множество значений на промежутки.
Но лучше учитывать оба и применить какой-нибудь алгоритм кластеризации.

[Skeptic]

Не пойдёт, т.к. координаты заданы с погрешностью. На содедних участках, принадлежащих одной прямой, наклоны пары точек могут иметь разные знаки. Например, имеются три экспериментальные точки, не лежащие на одной прямой. Соединим каждую пару точек прямыми. По наклону этих прямых нельзя сказать, какой наклон имеет искомая прямая.

Надо задать какой-то признак принадлежности точек к прямым. Без этого задача бессмыслена.