второй выстрел
подстановка: (основы аналитической геометрии, пропустите, если вы знакомы с этим), нахождение точки противоположной полуплоскости
Пример: Давайте получимдве точки: A = [a, b] = [2,3] и B = [c, d] = [4,1].Найти вектор u = AB = (2-4,3-1) = (-2,2).Этот вектор параллелен линии AB , как и вектор (-1,1).Уравнение для этой линии определяется вектором u и точкой в AB (т.е. A ):
X = 2 -1*t
Y = 3 +1*t
Где t - любое действительное число.Избавьтесь от t :
t = 2 - X
Y = 3 + t = 3 + (2 - X) = 5 - X
X + Y - 5 = 0
Любая точка, которая вписывается в это уравнение, находится на линии.
Теперь давайте создадим другую точку для определения полуплоскости,то есть C = [1,1], мы получаем:
X + Y - 5 = 1 + 1 - 5 < 0
Любая точка с противоположным знаком неравенства находится в другой полуплоскости, а именно эти точки:
X + Y - 5 > 0
решение: найти минимальный треугольник, который соответствует точке S
- Найти ближайшую точку P какмин (sqrt (( Xp - Xs ) ^ 2 + ( Yp - Ys ) ^ 2))
- Найти перпендикулярный вектор к SP как u = (-Yp + Ys, Xp-Xs)
- Найти две ближайшие точки A , B от противоположной полуплоскости до сигма = pP где p = Su (см. Подкатегорию), напримерпоскольку A находится на другом сайте строки q = SP (см. заключительную часть подстановки)
- Теперь у нас есть треугольник ABP, охватывающий S : вычислить сумму расстояний | SP | + | SA | + | SB |
- Найдите вторую ближайшую точку к S и продолжайте от 1. Если сумма расстояний меньше, чем в предыдущих шагах, запомните ее.Остановитесь, если | SP | больше, чем наименьшая сумма расстояний или больше нет доступных точек.
Надеюсь, эта диаграмма прояснит ситуацию.