Алгоритм поиска наилучшей линии для набора точек с использованием алгоритма выпуклой оболочки

Линия лучше всего подходит для множества точек S на плоскости, если она минимизирует сумму расстояний между точками в S и линией. Предполагая, что доступен алгоритм выпуклой оболочки, найдите линию наилучшего соответствия для заданного набора точек S на плоскости. Это упражнение из книги Дискретная и вычислительная геометрия. Я пытаюсь решить эту проблему в течение нескольких месяцев. Я знаю, как решить ее с помощью исчисления и умного перебора. Аналитический способ решения этой проблемы: http://mathworld.wolfram.com/LeastSquaresFittingPerpendicularOffsets.html. . Меня не интересует быстрое или оптимальное решение.


algorithm geometry computational-geometry convex-polygon
person Vnyemets    schedule 17.01.2019    source источник
comment
Здравствуйте, добро пожаловать в StackOverflow! Не могли бы вы показать, какой код вы уже пробовали?   -  person uv_    schedule 17.01.2019
comment
Я хочу понять алгоритм или идею   -  person Vnyemets    schedule 17.01.2019
comment
Трудно понять - как выпуклая оболочка связана с оптимальной линией...   -  person MBo    schedule 17.01.2019
comment
Я думаю, что этот алгоритм не является оптимальным и быстрым, но проблема для меня очень интересна   -  person Vnyemets    schedule 17.01.2019
comment
Пример: найдите кратчайшую ширину CH и проведите линию перпендикулярно этой ширине. Будет аппроксимацией для равномерного распределения, но не работает во многих случаях (т. е. несколько точек образуют CH, но многие другие находятся внутри и сгруппированы)   -  person MBo    schedule 17.01.2019
comment
проверьте это Для n точек на 2D-плоскости найдите максимальное количество точек, лежащих на одной прямой out   -  person Spektre    schedule 18.01.2019
comment
@Spektre, как эта задача связана с этим?   -  person Vnyemets    schedule 18.01.2019
comment
@Vnyemets Это быстрая линейная регрессия из 2D-облака точек ... вероятно, это не совсем ваша задача, поскольку у вас есть ограничение выпуклой оболочки (трудно сказать, что вы имеете в виду, поскольку вы не показывали входные и выходные данные / изображение / эскиз или что-то еще ), но вы можете использовать идеи из него, чтобы ускорить свой метод грубой силы.   -  person Spektre    schedule 18.01.2019
comment
@Vnyemets после вашего последнего редактирования вопрос неясен ... что вы просите? Я вижу, вы знаете, как решить это с помощью исчисления, грубой силы и связали аналитический способ сделать это, и вас не интересует ни быстрое, ни оптимальное решение ... это сокращает возможные ответы до нуля ... если вы не хотите другого способ решения, такой как использование нейронной сети, ИИ, ...... в таком случае, что делает ваш вопрос слишком широким без спецификаций ...   -  person Spektre    schedule 22.01.2019

Ответы (1)


arrow_upward
2
arrow_downward

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

image
Скачать лекцию в формате PDF от Ион Петре.

person Joseph O'Rourke    schedule 18.01.2019
comment
Спасибо за Ваш ответ! Но я не понимаю твоей идеи. Я очень удивлен, что вы написали эту интересную книгу. - person Vnyemets; 18.01.2019
comment
@Vnyemets: было ошибкой просить линию наилучшего соответствия, не объясняя, в каком смысле. Для метода наименьших квадратов я не верю, что выпуклая оболочка может помочь. - person Joseph O'Rourke; 18.01.2019
comment
Да, эту проблему можно решить с помощью линейного программирования. Но где применяется алгоритм выпуклой оболочки? - person Vnyemets; 18.01.2019
comment
Метод наименьших квадратов предназначен только для поиска наилучшей линии аналитическим способом. Я неправильно понял акциз? - person Vnyemets; 18.01.2019