Кто-нибудь знает алгоритм расчета видимости трассы в профиле? 
Очень желательно, чтобы работал быстро(в идеале - линейно).

Суть задачи...

Есть набор Z-отметок высот трассы. 
Необходимо найти в каждой точке максимальное расстояние видимости вдоль трассы.
 

(Предполагаю что трасса конечная, если не так, то несложно доработать.)

1. Строим выпуклую оболочку отметок высот (сложность ~n log[2](n), строится через сортировку). Получаем точки B[1], ... B[k].
2. Последовательно, начиная с ближайших, проводим прямые от наблюдателя A к точкам B[i]. Последняя точка B[s], для которой все предыдущие B[i] лежат ниже прямой (A; B[s]) и есть самая дальняя видимая точка. 

Хммм... Кажется не совсем так...
Во первых я не совсем корректно сформулировал задачу. Видимой из точки А считается точка Б,
если из точки А+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, а на самом деле - нет...

Или я что-то недопонял?    

тут, ИМХО, на углы надо смотреть
начать с ближайшей точки и двигаться вперед, пока не получим невидимую точку
а невидимость - когда угол на какую-нибудь из предыдущих больше, чем на проверяемую (+0.2)
для каждой точки определение видимости занимает линейное время
для всех - квадратичное
оптимизации пока в голову не приходит
P.S.
конечно же, для реализации сравнение углов стоит заменить на сравнение их тангенсов - их проще вычислить... 

Уточнения.
1. При построении выпуклой оболочки, область под профилем считается внутренней.
2. Пусть нас интересует видимость вправо, тогда при построении 
выпуклой оболочки все отметки слева от наблюдателя не рассматриваем.
3. Выпуклую оболочку нужно проводить через "поднятые" (+0,2м) точки. 
4. Положение наблюдателя вообще не важно, лишь бы не ниже профиля.

В Вашем примере выпуклая оболочка будет проходить только через точки А2 и А6, поэтому первой и последней перебираемой точкой будет А6. Она же и есть последняя видимая точка.

Добавлено @ 12:02 
maxim1000, Вы не правы. Требуется найти не максимальную область видимости, а максимальное расстояние видимости, т.е. какие-то точки до последней видимой могут оказаться невидны. 

Это сообщение отредактировал(а) nostromo - 18.4.2006, 11:57

Полагаю, все точки, не попадающие на выпуклую оболочку, до последней видимой, считаются видимыми, но в примере так не выходит - из А2 не видно А4. Для наглядности можно опустить А4 еще на 100, будет такая яма, которую с А2 не видно(А3 заслоняет). Хотя она вып. об. не принадлежит, и посему по алгоритму выходит видимой.

Добавлено @ 12:08 


:-) как раз наоборот... именно область мне и нужна.

Добавлено @ 12:10 

Именно это и огорчает...    

Тогда я неправильно понял задачу и Вам следует воспользоваться предложением maxim1000.

 

Можно модифицировать алгоритм maxim1000 и получить линейную сложность. 
Дело в том, что на каждом шаге нужно проверять не все предыдущие, а только
предпоследнюю (одну предыдущую).

Добавлено @ 12:32 
Доказательство: Если из А  были видны B[1], ..., B[i], а B[i+1] не видна, то B[i] обязана ее закрывать. Это следует из того, что с ростом i угол HAB[i] монотонно возрастает, где H --- любая фиксированная точка, такая, что для всех B[i] указанный угол меньше развернутого. 

тут вся фишка в том, от кого закрывать...
представим себе впадину между двумя возвышенностями
если внизу будет холмик небольшой, то он будет закрывать часть дороги вверх для нижних точек, но не для верхних
т.е. сиз начала дороги (на возвышенности) будет видно весь участок
когда мы будет потихоньку спускаться в один прекрасный момент маленький холмик начнет перекрывать то, что за ним
и снова тот участок мы увидим только, когда на него заберемся...
пример в точках:
(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м будет видна вся 

Насколько я понял, Вы предлагаете следующее: Если имеет место видимость А-В[i], и не имеет место А-В[i+1], то для точки А+1(следующей после А) можно проверять видимость сразу до точки B[i]. и не надо проверять видимость для точек [2..i-1] 
Если эта видимость есть для В[i], то она есть и для предыдущих... 

Так?

Но если ее нет, то получается, что нужно все равно проверять все точки начиная со следующей после наблюдателя...

Так алгоритм все равно не линейный, хотя улучшение налицо... :-)
 

To Breed.
Алгоритм соевршенно линейный, проверяем последовательно точки, начиная от наблюдателя, пока не найдем точку, которая конфликтует с предыдущей. 

Линейный для одной точки. А для каждой - соответственно квадрат. 

Нет, при фиксированном положении наблюдателя алгоритм линейный. Проверка для одной точки заключается в проверке того, что угол, под которым она видна из точки наблюдения не меньше угла, под которым видна предыдущая точка!

Добавлено @ 14:35 
maxim1000


На картинке отмеченные углы последовательно возрастают, а вот для следующей точки соответствующий угол будет меньше предыдущего. Где проблема? 

Присоединённый файл ( Кол-во скачиваний: 8 )
 q1.png 9,25 Kb

Видимость через добавочные 0,2 м --- это действительно особенность. Для ее учета предлагаю сначала найти максимальную область видимости отметок высот (без учета добавки к высоте), а затем попытаться ее расширить за счет этого смягчающего обстоятельства. 

проблема в том, что с точки 1 вообще все видно, значит, последняя точка 8
а когда мы спускаемся в точку 2, недостаточно проверить точку 9 (если бы такая была)
чтобы понять, что видимость из точки 2 будет именно до точки 4 нужно пройтись между точками 2 и 8, чтобы найти этот холмик или понять, что его нету
если проверять только точки, соседние с 8, то холмик, который находится значительно раньше, поймать не получится...