Телеграмм чат группы proalgorithms страница 3953

Size: a a a

pro.algorithms

1950 membersпожаловаться на группу

2021 April 29

Мне интересно именно, как здесь можно оптимизировать использование k-d дерева - я знаю про Vantage-point tree, Quad tree, ...

источник

19:31пожаловаться #1

Defragmented Panda in pro.algorithms

записывай в каждую ноду дерева размер области которую нода и все ее потомки вместе покрывают

потом смотри есть ли пересечение ноды с кругом. если нет - нода и все ее потомки можно отбросить из поиска

источник

19:31пожаловаться #2

‌‌Gleb Pilipets... in pro.algorithms

Хм, получается хранить 4 точки для ноды - top-left, top-right, bottom-left, bottom-right.

И потом проверять вот это - https://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection.
Выглядит немного сложно в реализации разве что, потому что сейчас я строю k-d дерево прям на входном массиве, не выделяя доп памяти...

Ок, спасибо. А на практике что лучше реализовать для такой задачи - vantage-point tree?

Stack Overflow

Circle-Rectangle collision detection (intersection)

How can I tell whether a circle and a rectangle intersect in 2D Euclidean space? (i.e. classic 2D geometry)

источник

19:37пожаловаться #3

Defragmented Panda in pro.algorithms

достаточно 2 точек.

крайние по длинной диагонали точки для куба выровненного по осям

источник

19:38пожаловаться #4

Defragmented Panda in pro.algorithms

в случае с k-d наверное можно схитрожопить до 1 точки на ноду. но уже надо будет подумать

источник

19:39пожаловаться #5

‌‌Gleb Pilipets... in pro.algorithms

Да, понял, спасибо

источник

19:39пожаловаться #6

Defragmented Panda in pro.algorithms

и я думаю квадрат-квадрат детектить проще. в конечной стадии уже проверять на это среди нескольких претендентов

источник

19:40пожаловаться #7

Defragmented Panda in pro.algorithms

vantage point tree ты устанешь кодить, а бонус минимален

источник

19:46пожаловаться #8

‌‌Gleb Pilipets... in pro.algorithms

А Quad? Там же так же глянуть, пересекается ли покрываемая область с кругом.

источник

19:50пожаловаться #9

Defragmented Panda in pro.algorithms

quad плох для не-равномерной плотности.

в пределах города ок. в пределах страны - нет

шашлычек в тайге нет

источник

19:51пожаловаться #10

‌‌Gleb Pilipets... in pro.algorithms

Понял, спасибо.

источник

19:51пожаловаться #11

AntiSpamBot in pro.algorithms

This is spam protection. You have 30 seconds to press the button or you will be banned!

источник

21:22пожаловаться #12

2021 April 30

‌‌Gleb Pilipets... in pro.algorithms

источник

01:50пожаловаться #13

‌‌Gleb Pilipets... in pro.algorithms

Как-то так сделал для поиска количества внутри

источник

01:50пожаловаться #14

Nikolai Karpov in pro.algorithms

https://nometa.xyz/

источник

10:06пожаловаться #15

Nikolai Karpov in pro.algorithms

Так какой вопрос то?

источник

10:19пожаловаться #16

Defragmented Panda in pro.algorithms

Есть ли отдельный термин для вычислений где есть много ячеек, но ячейки общаются только с соседями?

Имеет смысл для нейронок, fpga, некоторых симуляций

источник

14:39пожаловаться #17

Evgenii Zheltonozhsk... in pro.algorithms

Systolic array?

источник

14:41пожаловаться #18

Defragmented Panda in pro.algorithms

Да, спасибо, очень интересно

источник

14:47пожаловаться #19

2021 May 01

AntiSpamBot in pro.algorithms

This is spam protection. You have 30 seconds to press the button or you will be banned!

источник

17:59пожаловаться #20