Как быстро отрисовать большое количество точек/линий?

Question

[VjacheslavP]

Меня по сути интересует, как работает www.mapshaper.org (https://www.dropbox.com/s/5c3j42u2srmjsoq/ne_50m_a... данные для возможности посмотреть функционал mapshaper). Код открытый, но его слишком много.

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

Answer 1

[Сергей Протько]

втупую перебором и отрисовкой каждого элемента. В качестве оптимизации можно попробовать сразу отрендрить каждый объект на отдельном канвасе и потом скейлить, но мне что-то подсказывает что там при каждом изменении идет перерисовка всего холста. И да, на десктопах это очень быстро.

Comments

[VjacheslavP]

При большом количестве данных отрисовка происходит очень долго. Mapshaper же делает непонятные мне махинации с данными, что позволяет ему намного быстрее рисовать.

[Сергей Протько]

@VjacheslavP да, глянул код. Там очень много оптимизаций за счет пересекающихся линий идет. За счет этого сильно уменьшается количество точек, которые необходимо отрисовать. То есть оно формирует из этих простых фигур новые, оптимизированные, объедененные в общие шейпы и т.д. За счет этого отрисовка и выходит быстрее.

Посмотрите код.

[VjacheslavP]

Методы симплификации и поиска пересечений - это дополнительные функции приложения, просто для отрисовки данных они не используются. Если достаточно близко приблизить картинку, то можно заметить, что точки не теряются.

[Сергей Протько]

@VjacheslavP я не про симплификацию, я про объеденение фигур, что бы вместо того что бы отрисовать 100 фигур можно было отрисовать 10 больших и пару линий. Таким образом можно значительно уменьшить количество точек.

Answer 2

[lookid]

> как работает www.mapshaper.org
> Код открытый, но его слишком много
Классная у вас логика. Идите асфальт кладите. Там не нужно разбираться в чужом коде.
R-дерево, Octree, Quadtree с каким-нибудь хитрым хешированием. Называйте, как хотите.

Comments

[VjacheslavP]

То, что там какой-то хитрый алгоритм, я тоже понял. Этим вопросом я бы хотел более конкретизировать и разобрать для себя то, что используется в Mapshaper и как мне добиться подобного быстродействия.

[Сергей Протько]

@VjacheslavP кода там не так уж и много. Тратить время на его разбор я не могу, просто бегло просмотрел.