74
правки
Изменения
→Объединение двух выпуклых оболочек
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Case_a.png|thumb|300px320px|center|a. Касательная найдена]]|[[Файл: Case_b.png|thumb|300px320px|center|b. Может быть отброшена часть C после q, а также часть A перед p]]|[[Файл: Case_c.png|thumb|300px320px|center|c. Может быть отброшена часть C перед q, а также часть A перед p]]
|
|}
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Case_d.png|thumb|300px320px|center|d. По аналогии со случаем b]]|[[Файл: Case_e.png|thumb|300px320px|center|e. По аналогии со случаем c]]|[[Файл: Case_f.png|thumb|300px320px|center|f. Может быть отброшена часть C после q, а также часть A перед p]]
|
|}
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Case_g.png|thumb|300px320px|center|g. Только часть C после q может быть отброшена]]|[[Файл: Case_h.png|thumb|300px320px|center|h. По аналогии со случаем h]]|[[Файл: Case_i.png|thumb|300px320px|center|i. В этом случае нельзя сразу сказать, какие части A и C могут быть отброшены. Случай дробится на два]]
|
|}
Рассмотрим подробно случай i. Пусть <tex>m</tex> {{---}} прямая, разбивающая <tex>P</tex> на <tex>A</tex> и <tex>C</tex>. Пусть также <tex>l_p</tex> и <tex>l_q</tex> {{---}} касательные к выпуклым оболочкам в точках <tex>p</tex> и <tex>q</tex> соответственно. Если <tex>s</tex> {{---}} точка пересечения <tex>l_p</tex> и <tex>l_q</tex> лежит ниже прямой <tex>m</tex>, то точка пересечения моста и выпуклой оболочки <tex>A</tex> может лежать в треугольнике, образованном прямыми <tex>l_p</tex>, <tex>l</tex> и <tex>m</tex>, или выше <tex>p</tex>. Тогда можем удалить часть <tex>C</tex> ниже <tex>q</tex>. Случай, когда <tex>s</tex> лежит выше <tex>m</tex>, аналогичен (см. рис.).
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Case_i1.png|thumb|300px320px|center|i1. Точка пересечения лежит ниже прямой m]]|[[Файл: Case_i2.png|thumb|300px320px|center|i2. Точка пересечения лежит выше прямой m]]
|
|}
