Skutecznie odnajduj punkty wewnątrz okręgu

Mam zestaw 2d punktów rozmieszczonych losowo. Muszę wykonać czasochłonną operację na małym podzbiorze tych punktów, ale muszę najpierw dowiedzieć się, jakie punkty muszę wykonać w tym czasie intensywnej operacji. Aby określić, jakich punktów potrzebuję, muszą przejść szereg kryteriów geometrycznych.

Najbardziej podstawowymi kryteriami są te, które znajdują się w pewnej odległości od określonego punktu. Drugim najbardziej podstawowym kryterium jest to, czy są one zawarte w sektorze koła (stożek 2-D) wychodzącym z tego konkretnego punktu. (Edytuj: Ta operacja jest wywoływana regularnie z innym określonym punktem za każdym razem, ale ten sam zestaw punktów 2d.)

Moją pierwszą myślą było stworzenie siatki zawierającej punkty 2d, a następnie iterowanie wzdłuż stożka chwytającego kwadraty siatki, które przecina. W zależności od wielkości siatki odfiltrowałaby większość niepotrzebnych 2d punktów. Niestety, system wbudowany, na którym pracuję, jest poważnie ograniczony pamięcią, więc duża (według naszych standardów, nie każda) tablica 2d byłaby zbyt intensywna.

Próbowałem zbadać wykorzystanie drzew KD do przyspieszenia obliczeń, ale nie byłem w stanie znaleźć algorytmu dotyczącego sektorów okręgu i drzew kd.

Czy istnieje skuteczny algorytm do znajdowania punktów 2d w sektorze okręgu?

Uwaga, nasz szczególny system jest wolny zarówno w matematyce zmiennoprzecinkowej, jak i trygonometrii, więc rozwiązanie, które obejmuje mniej takich, jest rozwiązaniem wyższym, które wymaga wiele.

questionAnswers(2)

yourAnswerToTheQuestion