| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Видимость дороги в профиле |
| Автор: Breed 18.4.2006, 10:16 |
| Кто-нибудь знает алгоритм расчета видимости трассы в профиле? Очень желательно, чтобы работал быстро(в идеале - линейно). Суть задачи... Есть набор Z-отметок высот трассы. Необходимо найти в каждой точке максимальное расстояние видимости вдоль трассы. |
| Автор: nostromo 18.4.2006, 11:02 |
| (Предполагаю что трасса конечная, если не так, то несложно доработать.) 1. Строим выпуклую оболочку отметок высот (сложность ~n log[2](n), строится через сортировку). Получаем точки B[1], ... B[k]. 2. Последовательно, начиная с ближайших, проводим прямые от наблюдателя A к точкам B[i]. Последняя точка B[s], для которой все предыдущие B[i] лежат ниже прямой (A; B[s]) и есть самая дальняя видимая точка. |
| Автор: Breed 18.4.2006, 11:33 |
| Хммм... Кажется не совсем так... Во первых я не совсем корректно сформулировал задачу. Видимой из точки А считается точка Б, если из точки А+1.2м (в высоту) видно точку Б+0.2м (в высоту). Это первая проблема... Второе, предложенный алгоритм кажется не работает... Напимер: А1 - (0,0) А2 - (2, 10) А3 - (4, 0) А4 - (6, -20) А5 - (8, 0) А6 - (10, 10). Для этих 6ти точек, например, по алгоритму из А2 будет видно А4, а на самом деле - нет... Или я что-то недопонял?  |
| Автор: maxim1000 18.4.2006, 11:45 |
| тут, ИМХО, на углы надо смотреть начать с ближайшей точки и двигаться вперед, пока не получим невидимую точку а невидимость - когда угол на какую-нибудь из предыдущих больше, чем на проверяемую (+0.2) для каждой точки определение видимости занимает линейное время для всех - квадратичное оптимизации пока в голову не приходит P.S. конечно же, для реализации сравнение углов стоит заменить на сравнение их тангенсов - их проще вычислить... |
| Автор: nostromo 18.4.2006, 11:56 |
| Уточнения. 1. При построении выпуклой оболочки, область под профилем считается внутренней. 2. Пусть нас интересует видимость вправо, тогда при построении выпуклой оболочки все отметки слева от наблюдателя не рассматриваем. 3. Выпуклую оболочку нужно проводить через "поднятые" (+0,2м) точки. 4. Положение наблюдателя вообще не важно, лишь бы не ниже профиля. В Вашем примере выпуклая оболочка будет проходить только через точки А2 и А6, поэтому первой и последней перебираемой точкой будет А6. Она же и есть последняя видимая точка. Добавлено @ 12:02 maxim1000, Вы не правы. Требуется найти не максимальную область видимости, а максимальное расстояние видимости, т.е. какие-то точки до последней видимой могут оказаться невидны. |
| Автор: Breed 18.4.2006, 12:04 | ||||
| Полагаю, все точки, не попадающие на выпуклую оболочку, до последней видимой, считаются видимыми, но в примере так не выходит - из А2 не видно А4. Для наглядности можно опустить А4 еще на 100, будет такая яма, которую с А2 не видно(А3 заслоняет). Хотя она вып. об. не принадлежит, и посему по алгоритму выходит видимой. Добавлено @ 12:08
:-) как раз наоборот... именно область мне и нужна. Добавлено @ 12:10
Именно это и огорчает...  |
| Автор: nostromo 18.4.2006, 12:10 |
| Тогда я неправильно понял задачу и Вам следует воспользоваться предложением maxim1000. |
| Автор: nostromo 18.4.2006, 12:26 |
| Можно модифицировать алгоритм maxim1000 и получить линейную сложность. Дело в том, что на каждом шаге нужно проверять не все предыдущие, а только предпоследнюю (одну предыдущую). Добавлено @ 12:32 Доказательство: Если из А были видны B[1], ..., B[i], а B[i+1] не видна, то B[i] обязана ее закрывать. Это следует из того, что с ростом i угол HAB[i] монотонно возрастает, где H --- любая фиксированная точка, такая, что для всех B[i] указанный угол меньше развернутого. |
| Автор: maxim1000 18.4.2006, 13:43 | ||
тут вся фишка в том, от кого закрывать... представим себе впадину между двумя возвышенностями если внизу будет холмик небольшой, то он будет закрывать часть дороги вверх для нижних точек, но не для верхних т.е. сиз начала дороги (на возвышенности) будет видно весь участок когда мы будет потихоньку спускаться в один прекрасный момент маленький холмик начнет перекрывать то, что за ним и снова тот участок мы увидим только, когда на него заберемся... пример в точках: (0,10)-(1,5)-(2,0)-(3,0)-(4,1)(холмик)-(5,0)-(6,0)-(7,5)-(8,10) но все это неважно, т.к. есть еще одно условие, которое убивает немало путей для рассуждений (возожно, не все): те самые 1.2 и 0.2 метра когда точка проверяется на видимость, у нее одна высота (+0.2) когда она проверяется на "мешание" видимости другой у нее другая (без всяких добавок) и когда проверяется видимость из нее, у нее вообще третья высота (+1.2) из этого, например, следует, что любая кривая с перепадом высот не более, например 0.01м будет видна вся |
| Автор: Breed 18.4.2006, 13:44 | ||
Насколько я понял, Вы предлагаете следующее: Если имеет место видимость А-В[i], и не имеет место А-В[i+1], то для точки А+1(следующей после А) можно проверять видимость сразу до точки B[i]. и не надо проверять видимость для точек [2..i-1] Если эта видимость есть для В[i], то она есть и для предыдущих... Так? Но если ее нет, то получается, что нужно все равно проверять все точки начиная со следующей после наблюдателя... Так алгоритм все равно не линейный, хотя улучшение налицо... :-) |
| Автор: nostromo 18.4.2006, 13:58 |
| To Breed. Алгоритм соевршенно линейный, проверяем последовательно точки, начиная от наблюдателя, пока не найдем точку, которая конфликтует с предыдущей. |
| Автор: Breed 18.4.2006, 14:08 | ||
Линейный для одной точки. А для каждой - соответственно квадрат. |
| Автор: nostromo 18.4.2006, 14:23 | ||||
Нет, при фиксированном положении наблюдателя алгоритм линейный. Проверка для одной точки заключается в проверке того, что угол, под которым она видна из точки наблюдения не меньше угла, под которым видна предыдущая точка! Добавлено @ 14:35 maxim1000
На картинке отмеченные углы последовательно возрастают, а вот для следующей точки соответствующий угол будет меньше предыдущего. Где проблема? |
| Автор: nostromo 18.4.2006, 14:43 |
| Видимость через добавочные 0,2 м --- это действительно особенность. Для ее учета предлагаю сначала найти максимальную область видимости отметок высот (без учета добавки к высоте), а затем попытаться ее расширить за счет этого смягчающего обстоятельства. |
| Автор: maxim1000 18.4.2006, 23:16 | ||
проблема в том, что с точки 1 вообще все видно, значит, последняя точка 8 а когда мы спускаемся в точку 2, недостаточно проверить точку 9 (если бы такая была) чтобы понять, что видимость из точки 2 будет именно до точки 4 нужно пройтись между точками 2 и 8, чтобы найти этот холмик или понять, что его нету если проверять только точки, соседние с 8, то холмик, который находится значительно раньше, поймать не получится... |
| Автор: Breed 19.4.2006, 07:21 |
| Можно в принципе искать участки выпуклости(вниз) ломаной, тогда из всех точек такого участка будет гарантированная видимость до его конца. Потом можно соседние участки(конечная точка первого участка это есть первая точка второго) объединять: если из какой - либо точки первого участка выпуклости видно вторую точку следующего участка, то из нее видно весь следующий участок, в противном случае область видимости ограничивается концом первого участка... Для остальных точек(не входящих в участки) можно обычным образом(углами) проверять видимость до ближайшего участка выпуклости, а дальше так же как и описано выше... Только вот будут ли полезны подобные ухищрения?... |
| Автор: nostromo 19.4.2006, 08:50 |
| То maxim1000: Насколько я понимаю, задача состоит в нахождении максимальной области видимости при фиксированном положении наблюдателя. При этом Ваш первоначальный алгоритм имел квадратичную сложность, а я предложил модификацию линейной сложности. Как понимать выражение: "когда мы спускаемся в точку 2"? Если наблюдатель находится в точке 2, то, согласно моему алгоритму нужно последовательно проверять точки 3, 4, 5, ..., следя лишь за тем, чтобы угол не именьшался. |
| Автор: Breed 19.4.2006, 09:30 | ||
Задача состоит в нахождении области видимости в КАЖДОЙ ТОЧКЕ разбиения трассы. |
| Автор: nostromo 19.4.2006, 09:42 | ||
Что-то мне опять неповезло  -----------------------------------------------
Мне кажется, что вполне нормальный алгоритм. |
| Автор: maxim1000 19.4.2006, 10:41 | ||||
нет-нет-нет для фиксированного наблюдателя мой алгоритм имеет линейную сложность - это же простой перебор точек после него и проверка какого-то условия (которая требует постоянное количество операций) а вот алгоритм вычисления этого значения для всех возможных позиций наблюдателя уже получается квадратичным...
ну порядок сложности в общем случае они не сократят, но могут сократить его на некоторы участках плюс выпуклых участков - углы там изменяются монотонно, т.е. не может быть холмиков посередине, а всякий поиск в массивах упорядоченных уже значительно быстрее можно сделать (вместо линейного, логарифмический) |
| Автор: Breed 19.4.2006, 12:23 |
| Вообще, если имеется вогнутая ломаная (вверх) А[i..k], то найдя область видимости для А[i](например она есть до точки А[l], l<k), можно для точки A[i+1] начинать поиск с l-той точки, так как все точки до l будут гарантированно видны из А[i+1], так что в принципе видимость находится за линейное время. при переходе от вогнутой области к выпуклой, если из точки вогнутой области видна вторая точка выпуклой области, то вся выпуклая область видна из нее. Здесь вроде тоже линейно. Осталось придумать, что делать с переходами от выпуклой области к вогнутой. И с ломаными типа /\/\/\/\/\/\... хы... :-) |
