Реализация внутренней точки

Question

Помимо выпуклой книги Бойда по программированию,

Какой ресурс лучше для:

анализ + практическая реализация алгоритмов внутренних точек?

Answer 1

Если у вас есть книга Бойда, вы знаете о CVXOPT . Загляни внутрь. Если вы заинтересованы в деталях реализации, посмотреть на реализацию бесценно. Как и в случае большинства сложных численных алгоритмов, вам будет гораздо выгоднее использовать ранее написанный код, чем писать собственный, но вы, вероятно, знаете это. Есть много других внутренних реализаций, доступных онлайн для линейного программирования, SOCP, квадратичного программирования, выпуклого программирования и т. Д. Я также использовал OOQP и немного посмотрел на внутренности. Это казалось достаточно простым.

Мне также понравилось первое издание Числовая оптимизация . У меня был хороший, довольно практичный обзор методов предиктор-корректор во второй половине. Второе издание, несомненно, аналогичного качества.

Answer 2

Вы можете реализовать его двумя способами:

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

Если у вас много точек (скажем, M точек), и вы должны определить, находится ли она внутри, вы найдете точку внутри многоугольника, иразбить многоугольник на n треугольников с вертикалью в этой точке и двумя другими в двух последовательных точках на многоугольнике (которые образуют ребро).У вас будет n линий, с вертикалью в выбранной ранее точке и точкой в ​​каждой точке многоугольника.Вы отсортируете их по углу по часовой стрелке.Затем у вас будет M строк с вертикалью в выбранной точке, а другая - в одной из M точек.Вы отсортируете их как первый N. Затем вы можете найти в o (N + M), для каждой точки в M, ближайшую левую и правую линии от N (скажем, линии CenterAx и CenterAy. Далее, вам нужно выяснить, находится ли точка в треугольнике CenterAxAy. Это можно сделать в o (1), проверяя, равны ли треугольники CenterAxAy с площадью (CenterAxP) + площадь (CenterAyP) + область (AxAyP)).

Надеюсь, вы поймете, что я здесь написал.