кластеризация плоскости прямыми. Опции

[cradle1]

Есть у меня задача - я ее решаю, вполне возможно, что у кого то есть опыт, и ему не трудно поделиться.
Нужно написать прогу, которая на плоскости, с данными точками ищет прямые (отбрасывая шум) , близкие к данным точкам.
Я это делаю полным перебором типа этого.
class line{k,b,khi2}
class palte{z,pointsN,point[pointsN]}// плоскость XZ разбивается на проекции Z, в каждой проекции добавляется массив points, с количеством точек, лежащих на прямой z
class ploskost{platesN,plate[platesN],linesN,line[linesN]}

ploskost.AddPoint(x,z) - добавляет точку(если надо plate) x,z
findlines(minpointsonline,maxkhi2,samepointsincluster)
далее заводится счетчик counter[platesN], где counter[i] лежит от 0 до plate[i].pointsN // 0 - не берем точку в прямую, j - берем j ую точку plate[i].point[j]
перебираем счетчик c minpointsonline ненулевыми значениями.
findline (counter,&k,&b,&khi2) - все довольно тупо.
Если khi2<maxkhi2 сравниваем счетсик с уже найденными прямыми по другим счетчикам, отличие больше samepointsoncluter, заводит новую прямую line[i]. иначе сравнивает полученные khi2 и замещает наименьшим.

Думаю смысл ясен.


Вообще на моем детекторе сейчас 10 plates, по 16,16,16,16,32,32,32,44,44,44 возможных точек.

[nik_vic]

А какова исходная "околофизика"?
Эти точки - на редкой прямоугольной сетке и "активируются" при прохождении некоего объекта?
Вариант - объекты двигаются по прямым и случайно оставляют следы с некоторой ошибкой...

[UNDEFEAT]

Я вот прочитал пару раз, и даже не понял, что нужно сделать...

[cradle1]

А какова исходная "околофизика"?
Эти точки - на редкой прямоугольной сетке и "активируются" при прохождении некоего объекта?
Вариант - объекты двигаются по прямым и случайно оставляют следы с некоторой ошибкой...

Почти, точки - сработавшая проволока дрейфовой камеры или сработавшая трубка дрейфовой станции.

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

Каждая дрейфовая камера состоит из двух плоскостей по 16 проволочек с зазором между ними 32мм, где вторая плоскость сдвинута на половину зазора.

Каждая дрейфовая станция это 3 плоскости касающихся трубочек d=30мм, средняя плоскость стоит так, что трубочки в ней касаются трубочек соседних плоскостей.

При работе ускорителя, заряженная частица вылетает из магнита и летит по прямой через координатные детекторы. Нужно найти уравнение прямой. На моем рисунке по горизонтали (Z) координата плоскости прохождения, по вертикали - координата сработавшей проволочки или трубки( слева 2 камеры) (справа - цветные 2дрейфовые станции). проекция XZ, есть еще и - YZ, я ее просто не прикрепил.

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

[telepnev]

Вопрос по картинке, если отбросить вашу "околофизику".

Есть градация по цветам. Множество Red, Blue и Green, это по сути входные данные. Для каждого из них необходимо выделить подмножество максимальной мощности такое, что все его элементы лежат в "эпсилон окрестности" некой прямой?

[cradle1]

Вопрос по картинке, если отбросить вашу "околофизику".

Есть градация по цветам. Множество Red, Blue и Green, это по сути входные данные. Для каждого из них необходимо выделить подмножество максимальной мощности такое, что все его элементы лежат в "эпсилон окрестности" некой прямой?

Точно. Нужно выделить прямые на полученных данных. Есть плоскость с точками. Нужно найти прямые. Которые ближе всего на данных

[telepnev]

Тогда может проще оперировать прямыми вместо точек, и искать точку внутри замкнутой области вместо прямой?
Ссылка для ознакомления. Могу скинуть какие то *.pdf, *.ppt. Может появиться разумная идея.
Еще в вычислительной геометрии есть понятие "заметающей прямой". Она полезна, много чего умеет. Есть всяки разные алгоритмы для анализа множества прямых на наличие пересечений и прочего.
Честно говоря, я уже почти все успел позабыть с института, могу только наводками оперировать.

[WildKOT]

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

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

Если шум имеет ненормальное распределение, то может иметь смысл изменить функцию ошибки, которая минимизируется при переборе.