| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 7 | nor | 155 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
Всем привет. Есть какое-то состояние фигур на плоскости. Надо определить пересекаются ли они, ну и где пересекаются.
Что надо хранить, как описывать фигуры и соответственно как сравнивать? Заранее спасибо за любую информацию.
Насколько помню методом вертикальной декомпозиции можно решить оба варианта, ею достаточно легко искать объединение, а вот пересечение там немножко нужно проапдейтить алгоритм считая кол-во открытых сегментов на текущем участке.
Артур, ты не ту задачу решаешь. Для построения вертикальной декомпозиции нужно найти точки пересечения фигур. А тут задача определить пересекаются ли фигуры вообще.
Решить данную задачу можно так: разбить каждый многоугольник на отрезки, захранив какой отрезок какому многоугольнику принадлежит(круги не трогаем). Далее решаем три бояна: пересечение двух отрезков, пересечение отрезка и круга, пересечение двух кругов.
А теперь многоугольник целиком лежит внутри другого. Или мы считаем что многоугольник это только граница?
А эту задачу уже можно решать с помощью вертикальной декомпозиции. После того, как получили решение предыдущей.
Это лол.
Если многоугольники не пересекаются, то они вкладываются тогда и только тогда, когда любая(произвольная) точка одного лежит внутри другого.
Да, спасибо, вы правы, железяка ищет ненужных извращений на свою голову:)
Кстати, вкралось подозрение: откуда задача? Случайно не с идущего сейчас контеста?
Задача из пробы написать программу на cocos2d-x, в которой в зависимости от положения устройства будут "падать" фигуры. У меня было свое сложное решение, решил спросить у сообщества про более простое решение.
А, тогда фигур у вас, наверное, сильно меньше 105. Если их порядка сотни, то можно просто перебрать все пары объектов и для каждой пары проверить, не пересекаются ли они из соображений "многоугольник — это множество отрезков".
Если написание велосипеда не цель, попробуй Box2D для физики.