Войти
ПрограммированиеФорумГрафика

[Геометрия] Структура данных для обработки принадлежности точек секторам (2 стр)

Страницы: 1 2 3 Следующая »
#15
(Правка: 13:26) 13:22, 12 мая 2019

}:+()___ [Smile]
> Но в этом случае ты затираешь данные с прошлой итерации, т. е. все данные тебе одновременно не нужны.
да, именно так

> В общем, стоило бы четко описать, какие данные и в каком порядке тебе нужны.
мне нужно проитерироваться по каждой точке, и чтобы для неё было локально известно пересечение каждого из лучей, из неё выходящих. как только точка обработана, эти данные можно забыть. точки можно обрабатывать в произвольном порядке.

}:+()___ [Smile]
> На мой взгляд, нужен только список интервалов для каждого угла (причем с нахлестом)
здесь вопрос в том, где именно хранить списки. я храню ссылки прямо в самих точках, то есть точки и выступают элементами списков. этот подход подразумевает, что у каждой точки может быть только одна ссылка на следующую (список односвязный).

Aslan
> Распределение по секторам для разных центр точек вообще независимо, считай для
> каждой центр точки отдельно - вот тебе и MN время и N память
ещё как зависимо. если известно пересечение лучей для одной точки, для её непосредственного соседа пересечения найти можно гораздо быстрее. если считать независимо, получится NM^2. если я правильно понял, что имеется в виду.

#16
(Правка: 14:45) 14:41, 12 мая 2019

Suslik
> если считать независимо, получится NM^2
Насколько я понял постановку задачи - фиксируем некоторую центр точку и прочие раскладываем в "карманы" по значению угла за O(N).
Откуда взял множитель M?
Единственное, "карманы" требуют инициализации (присвоение в 0 для случая массива со счетчиками или связ списка), это можно обойти, запоминая в кармане номер итерации по центр точкам

Если следующая центр точка близка к предыдущей, то возможно сократить время, т.к большинство точек попадут в теже карманы.
Я бы рассмотрел задачу с другого конца - фиксируя точку, последовательно перебираем центры, пока не получим смену интервала для фикс точки и этот центр для точки запоминаем, тут можно попробовать серединное деление и "ленивое" вычисление (когда для точки храним инфо, что смена интервала не ранее чем через K центров от нее, при необходимости сравнения K с некоторым L, если K<L - уточняем K дальнейшим перебором).
Тогда точки помещаем в heap (по порядку возрастания K) и проходя по точкам, извлекаем события смены интервала за log(N) - както так

#17
21:31, 12 мая 2019

Suslik
> чтобы для неё было локально известно пересечение каждого из лучей, из неё выходящих
А вторичные лучи нужны? Которые выходят из затеняющих максимумов.
Именно с ними основная проблема.

Кстати, а тебе нужен именно список, или достаточно только окраски точек?

#18
3:16, 13 мая 2019

}:+()___ [Smile]
> А вторичные лучи нужны? Которые выходят из затеняющих максимумов.
нет, но мне кажется, что их необходимо будет строить для оптимальной реализации алгоритма.

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

#19
3:55, 13 мая 2019

Suslik
> в идеале нужно перечислить все точки, попавшие в каждый сектор.
Тогда будет O(NM^2). Раз у тебя O(NM), то значит на каждом шаге тебя интересует не больше O(N) точек.
Соответственно, имеет смысл сконцентрироваться только на них.

Но, вообще, похоже, что должно хватать O(M) памяти для построения списка. Соображения:

  • Стоит сразу разделить восходящие и нисходящие отрезки.
  • Хранить указатель надо только в первой точке отрезка, иначе будет O(NM^2).
  • В восходящих отрезках надо хранить указатель на следующий восходящий отрезок.
  • В нисходящих указатель на восходящее продолжение предыдущего отрезка.

  • И все равно, я подозреваю, алгоритм будет вырождаться в O(NM^2) на каких-то патологических случаях.

    #20
    4:41, 13 мая 2019

    }:+()___ [Smile]
    > Тогда будет O(NM^2)
    про "перечислить" я загнул. на самом деле в идеале мне достаточно знать для сектора среднее значение цвета, ассоциированного с каждой точкой. но в простом случае пусть это будет одна(любая) точка на сектор, если это возможно сделать эффективно.


    > Стоит сразу разделить восходящие и нисходящие отрезки.
    учти, что восходящие и нисходящие отрезки зависят от угла. для угла, например, в pi/4, отрезки, восходящие с производной меньше tg(pi/4) будут нисходящими.

    > И все равно, я подозреваю, алгоритм будет вырождаться в O(NM^2) на каких-то патологических случаях.
    на самом деле я более-менее реализовал алгоритм за O(NM) по времени и за O(M) по памяти, но он немного приближённый:
    для каждой точки хранится указатель на следующую, которая находится не ниже угла [cht]\alpha_i[/cht]. если указатель на следующую для точки j равен j+1, это значит, что для всех углов < i (то есть для углов, идущих ниже), гарантированно это будет так же, поэтому хранить смысла в явном виде нет. если же указатель для j не равен j + 1, это значит, что для угла i здесь будет скачок (то есть "тень" точки j), а в точке j + 1 хранятся данные для угла i - 1. то есть односвязный список, в котором для каждой точки хранится указатель в том секторе, которому она принадлежит, но делается допущение, что каждая точка принадлежит только одному сектору. то есть несколько секторов не могут выходит из одной точки — это приближение, на которое я пошёл.

    но мне мне кажется, что даже O(NM) по времени — это слишком медленно и на самом деле я могу обойтись без точных данных о принадлежности всех точек каждому сектору. можно ли ускорить алгоритм, если искать только по одной(любой) точке на сектор?

    #21
    6:04, 13 мая 2019

    Suslik
    > на самом деле в идеале мне достаточно знать для сектора среднее значение цвета
    Т. е. тебе нужны суммы неких величин [cht]F_m[/cht] для точек каждого сектора.
    Это можно обновлять инкрементально — находить точки, для которых сменился номер сектора.

    > учти, что восходящие и нисходящие отрезки зависят от угла.
    Восходящие/нисходящие в комбинаторном смысле.
    Если предыдущий интервал имеет номер сектора меньше — то это восходящий отрезок, иначе нисходящий.

    > можно ли ускорить алгоритм, если искать только по одной(любой) точке на сектор?
    Это ж трассировка лучей получается. Мне кажется, сложность инкрементальной трассировки от инкрементального нахождения среднего особо отличаться не будет.

    #22
    (Правка: 6:08) 6:08, 13 мая 2019

    }:+()___ [Smile]
    > Это можно обновлять инкрементально — находить точки, для которых сменился номер
    > сектора.
    да. из суммы вычитаются точки, которые выпали из сектора и добавляются к тому сектору, куда прибыли. это не проблема. но если можно забить на точное усреднение и вместо этого считать по одной точке на сектор, но быстрее, то я бы выбрал этот вариант.

    > Это ж трассировка лучей получается. Мне кажется, сложность инкрементальной трассировки от инкрементального нахождения среднего особо отличаться не будет.
    вот и я к такому выводу пришёл. казалось бы, работы делается больше, но на самом деле нет. по идее вся затея и делается для инкрементального трассировщика лучей/конусов.

    #23
    19:16, 14 мая 2019

    Suslik
    И как это обобщишь на 3D?

    #24
    (Правка: 23:07) 20:55, 14 мая 2019

    Suslik
    Чтото много лишнего накрутили
    Если граница между секторами - луч и он при смене центра параллельно переносится, то при движении центра слева-направо надо лишь определить - если луч, смотрящий вправо, стал вышше, то правая граница сектора сдвинулась вправо итд, получается инкрементальный алгоритм за MN

    #25
    4:26, 15 мая 2019

    Aslan
    > Если граница между секторами - луч и он при смене центра параллельно
    > переносится, то при движении центра слева-направо надо лишь определить - если
    > луч, смотрящий вправо, стал вышше, то правая граница сектора сдвинулась вправо
    > итд, получается инкрементальный алгоритм за MN
    с этого я как бы начал. следующий вопрос в том, как уложить это в O(M) памяти.

    #26
    11:32, 15 мая 2019

    Suslik
    > с этого я как бы начал. следующий вопрос в том, как уложить это
    > в O(M) памяти
    M границ - в чем проблема?

    #27
    11:44, 15 мая 2019

    Aslan
    > M границ - в чем проблема?
    >
    >
    проблема в том, как луч сдвинуть при смене центра с учётом затенения. естественный способ это сделать — на каждый луч хранить стек точек, которые находятся "не в тени" этого луча, то есть которые могут использоваться при перемещении центра. но в таком случае получается, что на каждую из M точек хранится N ссылок, что не влезает по памяти.

    #28
    14:03, 15 мая 2019

    Понимание что требуется сделать уже выработалось какое то?
    Чем больше смотрю на описание вместе с анимацией, тем меньше понятно.

    #29
    14:04, 15 мая 2019

    }:+()___ [Smile]
    > Тогда мне непонятна твоя идея, что можно хранить меньше O(M*N).

    Вот мне тоже - если для каждой точки нужно хранить какие видны из неё под какими углами, то даже M*N кажется мало.

    Страницы: 1 2 3 Следующая »
    ПрограммированиеФорумГрафика