Вопросы с тегом «computational-geometry»

У меня есть набор пар. Каждая пара имеет форму (x, y), так что x, y принадлежат целым числам из диапазона [0,n). Итак, если n равно 4, то у меня есть следующие пары: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) У меня уже есть пары. Теперь я должен построить комбинацию, используя n/2пары, чтобы ни одно из...

Я заказал несколько кожаных листов, из которых я хотел бы собрать шары для жонглирования, сшивая края вместе. Я использую платоновские тела для формы шаров. Я могу отсканировать кожаные листы и создать многоугольник, который приблизительно соответствует форме кожаного листа (как вы знаете, это кожа...

Я хотел бы написать простую программу, которая принимает набор окон (ширина + высота) и разрешение экрана и выводит расположение этих окон на экране таким образом, чтобы окна занимали больше всего места. Поэтому можно изменить размер окна, сохраняя при этом output size >= initial sizeи...

С приближением праздничного сезона я решил сделать несколько звезд с корицей . Это было весело (и результат вкусно), но мой внутренний ботаник съежился, когда я положил первый поднос со звездами в коробку, и они не поместились бы в один слой: Почти! Есть ли способ, которым они могли бы...

Есть ли способ определить, могут ли два набора точек быть разделены линией? У нас есть два набора точек и если существует линия, разделяющая и такая, что все точки и только на одной стороне линии и все точки и только на другой стороне.B A B A A B BAAAВBBAAAВBBAAAAAAВBBВBB Самый наивный алгоритм,...

Я пытаюсь найти подход к следующей проблеме: По заданному набору точек и радиусу найдите центральную точку окружности, чтобы в окружности было максимальное количество точек из множества. Время работы должно быть .r O ( n 2 )SSSrrrO(n2)O(n2)O(n^2) Сначала это казалось чем-то похожим на проблему...

Алгоритм Рамер-Дуглас-Peucker для упрощения линии имеет наихудший среда выполнения. Для правильно распределенных случайных входов ожидаемая сложность времени выполнения . В 2D есть другие алгоритмы со сложностью времени выполнения худшем случае , которые вычисляют точно такой же результат, что и...

Размышляя над одной проблемой, я понял, что мне нужно создать эффективный алгоритм, решающий следующую задачу: Проблема: нам дан двумерный квадратный прямоугольник со стороной nnn , стороны которого параллельны осям. Мы можем посмотреть на это через верх. Тем не менее, есть также mmm горизонтальных...

Проблемы с обрезкой - это проблемы, при которых определенный большой объект следует разрезать на несколько небольших объектов. Например, представьте , у вас есть завод , который работает с большими листами сырого стекла, шириной и длиной . Есть несколько покупателей, каждый из которых хочет...

|P|=n|P|=n|P| = nkkkkkknnnC={c1,c2,…,ck}C={c1,c2,…,ck}C = \{ c_1,c_2,\ldots,c_k\}kkkcost(C)=maximinjD(pi,cj)cost(C)=maximinjD(pi,cj)\text{cost}(C) = \max_i \min_j D(p_i, c_j)DDDобозначает евклидово расстояние между входной точкой и центральной точкой . Каждая точка присваивается ближайшему центру...

Определение : Многоугольник PPP на плоскости называется монотонным относительно прямой LLL , если каждая прямая, ортогональная LLL пересекает PпP не более двух раз. Для данного многоугольника PPP возможно ли определить, существует ли какая-либо прямая LLL такая, что многоугольник PPP является...

В книге Марка де Берга и др. «Вычислительная геометрия: алгоритмы и приложения» описан очень простой алгоритм грубой силы для вычисления триангуляций Делоне. Алгоритм использует понятие недопустимых ребер - ребер, которые могут отсутствовать в допустимой триангуляции Делоне и должны быть заменены...

К сожалению, я все еще не настолько силен в понимании алгоритма Sweep Line . Все статьи и учебники по этой теме уже прочитаны, однако до понимания еще далеко. Просто чтобы прояснить ситуацию, я стараюсь выполнять как можно больше упражнений. Но действительно интересные и важные задачи все еще...

Размещая геометрические объекты в квадри (или октодереве), вы можете разместить объекты, размер которых превышает один узел, несколькими способами: Размещение ссылки на объект в каждом листе, для которого он содержится Размещение ссылки на объект в самом глубоком узле, для которого он полностью...

У меня есть тетраэдр и многогранник . ограничен так, что он всегда разделяет все свои вершины с . Я хочу определить, находится ли внутри .п т п т пttt ppptttpppttt ppp Я хотел бы добавить одну деталь к проблеме в случае, если она может внести вклад в решение: - тетраэдр Делоне, а грани p...

Я столкнулся с алгоритмом, чтобы решить реальную проблему, и я помню класс, который я взял, где я сделал что-то очень похожее для некоторых для домашней работы. По сути, это график точек, и линии нарисованы так, чтобы они были равноудалены между двумя точками. Он образует идеальное разделение, где...

Я пытаюсь решить следующую проблему покрытия. Есть передатчиков с зоной покрытия 1 км и n приемников. Определите в O ( n log n ), что все приемники охвачены любым передатчиком. Все приемники и передатчики представлены своими координатами x и y .NNnNNnO ( n logн )О(Nжурнал⁡N)O(n\log n)ИксИксxYYy...

Предположим, нам даны два числа и и мы хотим найти для .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Наивный алгоритм просто проверяет все возможные пары; например, в ruby ​​у нас будет: def max_xor(l, r) max = 0 (l..r).each do |i| (i..r).each do |j| if (i ^ j > max) max...

В компьютерной науке существует такая популярная проблема [1] [2], которая заключается в нахождении минимального числа прямых, охватывающих данный набор точек в 2D. Несмотря на то, что я отсканировал много бумаг, ни у одной из них нет четкой мотивации проблемы. Какая польза от решения этой...

Для заданного ортогонального многоугольника (многоугольник, стороны которого параллельны осям), я хочу найти наименьший набор внутренних непересекающихся квадратов, объединение которых равно многоугольнику. Я нашел несколько ссылок на слегка отличающиеся проблемы, такие как: Покрытие ортогонального...