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

На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...

У меня есть два набора точек в 2-мерной плоскости. Я хочу найти ближайшую пару точек такую, чтобы , , а евклидово расстояние между как можно меньше. Насколько эффективно это можно сделать? Можно ли это сделать за , где?s , t s ∈ S t ∈ T s , t O ( n log n ) n = | S | + | T |S,TS,TS,Ts,ts,Ts,ts∈Ss∈Ss...

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

Ради интереса я пытаюсь сделать каркасный просмотрщик для DCPU-16 . Я понимаю, как сделать все, кроме как скрыть линии, которые скрыты в каркас. Все вопросы здесь, касающиеся SO, предполагают, что у вас есть доступ к OpenGL, к сожалению, у меня нет доступа ни к чему подобному для DCPU-16 (или к...

Для заданного набора точек и радиуса . Что представляет собой сложность поиска точки с большим числом точек на расстоянии, меньшем, чем . Например, тот, который максимизирует ?x1,…,xn∈R2x1,…,xn∈R2x_1, \ldots, x_n \in \mathbb{R}^2rrrrrr∑ni=11∥x−xi∥≤r∑i=1n1‖x−xi‖≤r\sum_{i=1}^n \mathbb{1}_{\|x - x_i\|...

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

Хорошо известно, что монотонные полигоны играют решающую роль в триангуляции полигонов . Определение: Многоугольник на плоскости называется монотонным относительно прямой , если каждая прямая, ортогональная пересекает не более двух раз.PPPLLLLLLPPP При заданной прямой и многоугольнике существует ли...

Для данного плоского графа встроены в плоскости, определяется набором отрезков Е = { е 1 , . , , , e m } , каждый сегмент e i представлен своими конечными точками { L i , R i } . Создайте структуру данных DCEL для плоского подразделения, опишите алгоритм, докажите его правильность и покажите...

Для двух наборов и каждый из которых содержит непересекающихся точек на плоскости, вычисляется кратчайшее расстояние между точкой в и точкой в , т. Е. .AAABBBnnnAAABBBmin { dist(p,q) | p∈A∧q∈B }min { dist(p,q) | p∈A∧q∈B }\min \space \{\mbox{ } \text{dist}(p, q) \mbox{ } | \mbox{ } p \in A \land q...

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

Что такое вырожденные полигоны? Как проверить, является ли данная пара полигонов вырожденной или

Учитывая триангуляцию (без точек Штейнера) простого многоугольника , можно рассмотреть дуал этой триангуляции, который определяется следующим образом. Мы создаем вершину для каждого треугольника в нашей триангуляции и соединяем две вершины, если соответствующие треугольники имеют общее ребро....

Мне дали упражнение, к сожалению, я сам не справился. Существует множество прямоугольников и прямоугольник R 0 . Используя алгоритм подметания плоскости, определите, полностью ли покрыто R 0 набором R 1 . , R n .р1, , рNR1..RnR_{1}..R_{n}р0R0R_{0}р0R0R_{0}р1, , рNR1..RnR_{1}..R_{n} Более подробную...