228
правок
Изменения
м
→Поиск трапецоидов которых пересек отрезок
Пусть якобы есть множество трапецоидов <tex>\Delta_0, \Delta_1, \Delta_2 ... \Delta_k</tex> упорядоченное по <tex>s_i</tex>
Пусть <tex>\Delta_({j+1)}</tex> один из правых соседей <tex>\Delta_j</tex> Так же при этом не сложно понять каким соседом он является.
Если rightp(<tex>\Delta_j</tex>) лежит выше <tex>s_i</tex>, то сосед нижний и наоборот.
Чтобы найти первый трапецоид нужно просто локализоваться правому концу в текущей карте.
===update===
