У меня есть набор точек в 2D (координаты для x и y), теперь мне нужно отбросить все точки, которые не имеют для меня значения, и я имею в виду, что меня интересует только область, в которой эти точки отслеживают.
Короче говоря, это
он должен производить это
вопрос: какой алгоритм может выполнять такую фильтрацию по этим точкам?
Вы можете использовать Graham_scan для вычисления выпуклой оболочки заданных точек. Когда у вас есть все точки на выпуклой оболочке, вы можете исключить остальные.
Существуют другие алгоритмы для вычисления выпуклых оболочек, но сканирование Грэма легко реализуемо и выполняется за O(n logn).
Я полагаю, что вы ищете алгоритм выпуклой оболочки. Я лично использую алгоритм Graham Scan для реализации выпуклой оболочки, поскольку он имеет очень хорошую сложность O(n*log(n)) и относительно прост. реализовать.
