2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Как разделить несколько пересекающихся прямых?
Сообщение10.01.2015, 16:41 
Допустим, есть массив, каждый элемент которого - точка (x, y). Предполагается, что этот массив состоит из нескольких прямых линий + шум. Как выделить эти прямые линии?

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

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

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

 
 
 
 Re: Как разделить несколько пересекающихся прямых?
Сообщение10.01.2015, 17:52 
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-х, и т.д. прямых.

 
 
 
 Re: Как разделить несколько пересекающихся прямых?
Сообщение10.01.2015, 18:22 
Прямые с их координатами записаны в массиве последовательно?
Или есть массив координат точек, и из этого массива надо выделить пересекающиеся прямые?

 
 
 
 Re: Как разделить несколько пересекающихся прямых?
Сообщение10.01.2015, 18:33 
Аватара пользователя
Igor_Dmitriev
Igor_Dmitriev в сообщении #959528 писал(а):
Находит ли этот алгоритм лучшее или одно из лучших решений?

Очевидно что нет. Так как он не ищет решения.
Igor_Dmitriev в сообщении #959528 писал(а):
Есть ли более удачные варианты?

Конечно есть, так как 1 пункт у вас явно не работает. Рассмотрите случай квадрата или решётки.
Igor_Dmitriev в сообщении #959528 писал(а):
Как выделить эти прямые линии?

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

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

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

 
 
 
 Re: Как разделить несколько пересекающихся прямых?
Сообщение10.01.2015, 23:25 
Pavia в сообщении #959558 писал(а):
dsge в сообщении #959542
писал(а):
5. Выбрать $k$ с наименьшей суммой квадратов.
Взять от числа $k$ сумму не возможно в принципе.

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

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

 
 
 
 Re: Как разделить несколько пересекающихся прямых?
Сообщение11.01.2015, 07:12 
Цитата:
Прямые с их координатами записаны в массиве последовательно?

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

Да.

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-х, и т.д. прямых.

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

 
 
 
 Re: Как разделить несколько пересекающихся прямых?
Сообщение11.01.2015, 09:09 
Координаты $x$ у всех прямых совпадают?

 
 
 
 Re: Как разделить несколько пересекающихся прямых?
Сообщение11.01.2015, 11:02 
Могут совпадать, могут не совпадать.

 
 
 
 Re: Как разделить несколько пересекающихся прямых?
Сообщение11.01.2015, 14:33 
Igor_Dmitriev в сообщении #959818 писал(а):
А если часть точек прямой находится в начале массива, другая часть - в конце?

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

 
 
 
 Re: Как разделить несколько пересекающихся прямых?
Сообщение11.01.2015, 14:40 
В задаче нечётко определены прямые.
Например. Даны координаты четырёх точек. Через эти точки можно провести шесть прямых. Какие прямые удовлетворяют условиям задачи?

 
 
 
 Re: Как разделить несколько пересекающихся прямых?
Сообщение11.01.2015, 20:36 
Аватара пользователя
Хотя бы известно, сколько их?

 
 
 
 Re: Как разделить несколько пересекающихся прямых?
Сообщение11.01.2015, 20:50 
dsge в сообщении #959542 писал(а):
4. Повторить 2. и 3. для $k=j, j=1,..., N/2$.

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

 
 
 
 Re: Как разделить несколько пересекающихся прямых?
Сообщение12.01.2015, 09:37 
Сколько их - неизвестно, предположительно, от 5 до 10.
Также неизвестно, какие точки какой прямой принадлежат.

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

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

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

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

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

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group