R Как найти и построить пересечение многих полупространств?

Question

Я ищу алгоритм или (предпочтительно) пакет в R, который может найти пересечение многих полупространств и затем построить их пересечение.

Я определю проблему математически.Предположим, у вас есть набор из N полупространств, определенных как S_i = {(x, y) | y> = a_i + b_i * x} для i = 1,2, ..., N, где x и y - действительные числа и a_iи b_i фиксированные действительные числа.Я знаю (a_i, b_i) для i = 1,2, ..., N.Мне нужно найти множество S = S_1 пересечь S_2 пересечь ... пересечь S_N, а затем построить S. Пример того, что я ищу ниже.

тонкийсиняя область с полосками - это пересечение полупространств S, а толстые синие линии - границы полупространства, y = a_i + b_i * x.Я не хочу, чтобы границы за пределами пересечения были построены, они есть, чтобы прояснить этот пример.Пожалуйста, игнорируйте оранжевую стрелку и точки.

Answer 1

Вы не приводите явных примеров нужных вам строк или структуры данных, которые вы используете для хранения строк, поэтому я просто приведу несколько примеров.У меня есть строки как функции.Вы можете выбрать диапазон значений x, который выходит за пределы области, которую вы хотите построить, и найти наибольшее значение L (x) для каждого x.Используйте их, чтобы построить полигон, показывающий желаемую область.Я делаю два графика с линиями границы и без них, чтобы показать, как область соответствует линии.

L1 = function(x) { -0.25 - 1*x }
L2 = function(x) { -0.25 - 0.6*x }
L3 = function(x) { -0.25 - 0.3*x }
L4 = function(x) { -0.3  - 1.5*x }


x=seq(-1,1,0.01)
Y = pmax(L1(x), L2(x), L3(x), L4(x))

par(mfrow=c(1,2))

plot(NULL, xlim=c(-0.5,0.5), ylim=c(-0.5,0.5))
polygon(c(-1,x,1),c(2,Y,2), col="blue", density=10)

plot(NULL, xlim=c(-0.5,0.5), ylim=c(-0.5,0.5))
polygon(c(-1,x,1),c(2,Y,2), col="blue", density=10)

lines(x, L1(x))
lines(x, L2(x))
lines(x, L3(x))
lines(x, L4(x))