Блог

Главная - Вопросы по программированию - Количество точек над некоторой строкой

Количество точек над некоторой строкой

#computational-geometry

#вычислительная геометрия

Вопрос:

Рассмотрим некоторые точки на плоскости 2d и функцию f(x)=ax , где b=0 . Допустим, точка представляет собой квадрат 1×1.

Теперь мы хотим сказать, сколько точек находится между f(x) функцией и линией y, как показано на рисунке ниже.

Черные точки допустимы, белые — нет. Мы также говорим, что точка действительна, если она:

  • пересекается с y осью;
  • или с помощью функции f(x) ;
  • или находится между ними.

Как показано на рисунке :

введите описание изображения здесь

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

Комментарии:

1. это похоже на этот ceee.rice.edu/Books/LA/leastsq/index.html

2. Эй, обычно у меня есть несколько точек на плоскости, и я хочу найти эту функцию с помощью простого двоичного поиска (я имею в виду найти, что a в f (x) = ax ), чтобы иметь максимальные допустимые точки, и их количество не превышает некоторого значения X. Приближения по методу наименьших квадратов кажутся хорошим методом для нахождения этогоэта функция, но я действительно не знаю, как заставить ее работать. Не могли бы вы уточнить, подходит ли этот метод для моей проблемы? Спасибо

Ответ №1:

Если я правильно понимаю, точки являются случайными и задаются вам по их координатам, и линия также предоставляется вам. Если это так, не может быть никаких априорных знаний о какой-либо взаимосвязи между точками, поэтому вам нужно будет просмотреть их в указанном порядке и сравнить их координату x с 0, а их координату y с f (x) . Если точка проходит проверку, вы увеличиваете счетчик, в противном случае вы этого не делаете. Алгоритм выполняется за O (n) раз, и я очень сомневаюсь, что вы сможете добиться большего успеха без дополнительной информации о точках.

Ответ №2:

Вопрос довольно неясен, но он появляется из комментария «Я имею в виду, что a в f (x) = ax имеет максимальное количество допустимых точек, и их количество не превышает некоторого значения X», которое вы хотите найти a так, что N(a)=X , где N(a) я имею в виду количество точек справа от оси yи над строкой y=ax ; или, если такого a не существует, найдите a такое, что m = N(a)<X и N(b)<m подразумевает N(b)<X .

Вот алгоритм O (n * ln (n)): для каждой точки p , исключая любую p нижеприведенную y=0 , вычислите наклон M_p как отношение p координат y и x, или DBL_MAX, если x = 0. Отсортируйте M в порядке возрастания (это шаг O(n * ln(n))) и вызовите отсортированный массив S .

Теперь мы настроим массив T таким образом, чтобы при задании любого X S[T[X-1]] из них был наклон, который разместит X точек на этом склоне или выше:

    S[n] = DBL_MAX;
   for (k=0, j=n-1; k<=n; --j) {
      T[j] = k;
      do   k; while (S[k]==S[k-1] amp;amp; k<=n);
   }

После этого пусть задан любой X. Пусть h = T[X-1] . Если h<n тогда N(S[h]) <= X ; если h==n на оси Y есть несколько точек, и конечный наклон не будет работать.

Этот алгоритм использует время O(n * ln(n)) и пространство O(n) для предварительной обработки набора из n точек первого квадранта, а затем использует время O(1) для нахождения a для любого заданного X, 0 < X <= n, такого, что N(a) = X , если таковой a существует, else возвращает a такое, что N(a) < X < N(b) if b>a , else возвращает DBL_MAX.