Контрольная точка для ее положения относительно выпуклой оболочки в log (n)

Ответ 1

Сначала разрешите только одну цепочку. Мы хотим проверить, находится ли (qx, qy) над выпуклой цепочкой сегментов линии.

Дорогая часть - это двоичный поиск в списке координат x, чтобы найти самую большую, меньшую, чем ваша точка запроса. Все, что вам нужно для этого, - это массив точек цепи, отсортированных по порядку x. Тогда это простая "точка над строкой?". тест.

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

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

РЕДАКТИРОВАТЬ. Я вижу, что ваш вопрос также может быть проанализирован как "то, как выглядят структуры данных точечного местоположения ilke?" а не "как сохранить выпуклый корпус для эффективного тестирования внутри/снаружи?"

Естественно исследовать местоположение точки в чуть более общем контексте, чем внутри-внешнее тестирование. Существует

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

С учетом сказанного, Haran и Halperin сравнили производительность различных алгоритмов CGAL. Они использовали современный компьютер с 2008 года, и они составили множество тестовых данных и попытались использовать различные стратегии размещения точек CGAL на каждом тестовом сценарии. Среди прочего, у них есть случай около 1,4 миллиона случайно расположенных краев, где их лучшая структура данных требуется всего около 190 микросекунд, чтобы ответить на запрос местоположения точки.

Это очень быстро, учитывая сложность типичных алгоритмов определения местоположения точки - я не мог этого сделать сам. И теория говорит нам, что она растет как O (log n). Однако, что O (log n) на несколько порядков медленнее, чем время O (log n), которое требуется для поиска отсортированного массива. Имейте это ввиду, когда вы выполняете вычислительную геометрию; константы имеют значение, и они часто не очень малы.

Ответ 2

Эта проблема может быть классифицирована как классическая проблема point-location.

• Предварительная обработка будет включать вычисление выпуклой оболочки для множества точек, а отрезки линии выпуклой оболочки будут использоваться на следующем шаге (или весь CH как область).

• Существует множество стандартных O(log n) алгоритмов запроса-времени для таких проблем (http://en.wikipedia.org/wiki/Point_location), как триангуляция Киркпатрика, рандомизированные трапециевидные карты и т.д.

Также обратите внимание, что в ожидании количество точек в CH(S) равно O(log n), где N - это количество общих точек в S. Таким образом, количество сегментов линий, рассмотренных для местоположения точек, уже сокращено до O(log n), что означает, что время запроса на самом деле равно O (log log N) в ожидании (в терминах общих точек в S).

Ответ 3

Вы должны сделать это, используя алгоритм развертки (например, растрирование, скажем, с использованием горизонтальной линии развертки). Создание отсортированных ребер вершин n * log (n), но после сортировки вы можете найти линию развертки на основе точки q и найти края, которые пересекает линия развертки.

Растеризация упрощается в выпуклом случае, так как вам не нужно беспокоиться о вогнутости в линии развертки.

Простая схема состоит в том, чтобы обойти многоугольник, построив краевые объекты, используя обмотку для определения левой и правой сторон. Все значения y для каждой точки переходят в отсортированный список (или массив, или набор, или карту, что угодно).

Ваша точка q.y используется для поиска края (ов) в левой и правой сторонах, тогда вы можете просто определить, находится ли q.x между левой и правой координатами. Сначала вы можете вычислить выпуклый корпус, чтобы убедиться, что ваши левые/правые части выпуклые.

(Ничего себе, при поиске растрового сканирования я встретил заметки из моего класса undergrad здесь с того момента, как я закончил. )

Ответ 4

struct point {
     LL x,y ;
} C[100010];


/*return area of triangle */
LL areaTriangle(const point &a, const point &b, const point &c) {
    return (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
}

/*An user define function to calculate where a point p inside a convex hull or not */

bool inConvexPoly(int N, const point p) {

/*Input: C is an array with vertex x, y of a convex hull, points must be anticlock-wise, If it clockwise then just reverse it. p is a point and we have to find does p inside polygon C or not*/

/*Most important part, finding two point using binay search such that point p may be lie inside the trianle
  made by those two points and point0 or point p may be lie inside the triangle which is
  made by point0, point_last, point_start */


LL start = 1, last = N - 1;
while(last - start > 1) {
    LL mid = (start + last) >> 1;
    if(areaTriangle(C[0], C[mid], p) < 0)   last = mid;
    else    start = mid;
}

/*Area of triangle form by point0, start point and last point*/
LL r0 = abs(areaTriangle(C[0], C[start], C[last]));


/*If point p is inside a triangle then the area of that triangle must be equal to
  the area ((point0, poin1, p) + (point0, point2, p) + (point1, point2, p))
  here point0 = C[0], point1 = C[start], point2 = C[last]*/

LL r1 = abs(areaTriangle(C[0], C[start], p));
LL r2 = abs(areaTriangle(C[0], C[last], p));
LL r3 = abs(areaTriangle(C[start], C[last], p));

/*Point p must not lie on any border line of the convex hull, So if the area is 0 then that three point lie on the
  same line */

LL r4 = areaTriangle(C[0], C[1], p);
LL r5 = areaTriangle(C[0], C[N - 1], p);

/*If the area of triangle form by point0, start and last point is equal to area
  from by triangle (point0, last, p) + (point0, start, p) + (last, start, p)
  and p don't lie on start-last line, point0-point1 line, point0-point[N - 1] line
  then the point p inside the convex hull */


 return (r0 == (r1 + r2 + r3) && r3 != 0 && r4 != 0 && r5 != 0);
}

 /*Try to draw picture for better understand */ 

 //End

Ответ 5

Вы можете сделать это в журнале (h), где h - это количество точек, которые являются уже рассчитанными точками корпуса. Это абсолютно неверно, что оно связано с Log (n), хотя это то, что написано в Википедии.

Вы должны заметить, что Wikipedia "Convex hull algorithmms" фильтруется Дэвидом Эппштейном, о котором вы говорите. Этот парень предотвращает добавление полезной информации. Если этот парень согласится добавить полезную информацию (новый алгоритм) и поймет это, он поймет, что вы можете достичь своей цели в O (Log h). Пожалуйста, просмотрите страницу Wikipedia для истории страницы.

В алгоритме выпуклый Hull AVL можно использовать промежуточный результат (avl tree по квадранту) и напрямую смотреть внутрь. Вы достигнете своей цели самым быстрым способом (лучшая производительность: журнал (h)).

2 важных момента:

• Сначала вам нужно определить квадрант. Вы должны проверить, может ли это быть границей квадранта. После этого, используя либо только корневую точку для непересекающегося квадранта, либо используя перекрестное произведение с первой и последней точкой квадранта, чтобы знать, находится ли оно справа (в случае перекрестного произведения, если ни один квадрант не найден, это потому, что точка не может быть точкой корпуса - нет необходимости идентифицировать квадрант).
• Точки упорядочиваются по координате x.

Если бы я мог найти какое-то время, я добавлю интерфейс в свой класс, чтобы проверить/добавить новую точку динамически. Но вы можете сделать это прямо сейчас: получить промежуточный результат выпуклой оболочки и использовать его напрямую (см. 2 важные точки).

Ответ 6

Альтернативное решение с использованием углов:

Выберите некоторую точку C внутри выпуклой оболочки, используя некоторую эвристику по вашему выбору.

Выберите некоторую строку L, проходящую через C, например, линию, параллельную оси OX.

Для каждой точки P на выпуклой оболочке вычислите угол между линией CP и L и используйте ее для сортировки выпуклых точек корпуса.

Теперь, если вы хотите узнать, находится ли какая-либо заданная точка T внутри выпуклой оболочки, вычислите угол между линиями CT и L и, используя двоичный поиск, найдите точки в выпуклой оболочке, которые находятся сразу и перед ним (A и B соответственно).

Теперь вам нужно только проверить, что T находится на одной стороне линии AB, чем C (внутри) или нет (снаружи).