Вопросы с меткой [вычислительная-геометрия]

Руководство по использованию метки отсутствует.

Фильтрация
Сортировка
Метки
1 голос
1 ответ
127 показов

Поиск центра окружности с максимальным кол-вом вхождений точек в нее

На вход программе подается кол-во рандомных точек (N) и радиус окружности (R). Нужно найти координаты центра окружности радиусом R так, чтобы в окружности было максимальное кол-во точек. Вообще нет ...
Motilyok's user avatar
3 голоса
1 ответ
218 показов

Самопересечение ломаной

Перед написанием вопроса читал похожую на SO статью, но мне интересно разобраться в чем именно у меня проблема. Пишу код для определения самопересекается ли ломаная или нет. Если хотя бы два звена ...
Stan's user avatar
  • 287
0 голосов
0 ответов
46 показов

Упрощение сетки меша триангуляцией

Как работает алгоритм упрощения полигональной сетки модели триангуляцией Делоне? Как именно из сетки первой модели можно получить такую же сетку как у второй без потери формы геометрии?
Jija's user avatar
  • 1
0 голосов
1 ответ
73 показа

Подсчет пересечений прямоугольников

Необходимо подсчитать сколько раз каждый прямоугольник пересекается с другими введенными прямоугольниками. На вход даются координаты диагоналей каждого прямоугольника. Проблема в функции, ...
Владимир's user avatar
0 голосов
0 ответов
42 показа

Вернуть список внутренних точек, после поиска минимальной выпуклой оболочки

Дан массив точек на плоскости. С помощью алгоритма Грэхема строю минимальную выпуклую оболочку. struct pt { double x, y; }; bool cmp (pt a, pt b) { return a.x < b.x || a.x == b.x &&...
Loki's user avatar
  • 53
1 голос
1 ответ
70 показов

Прямая с наибольшим кол-вом пересечений с триангуляцией

Дан выпуклый многоугольник с триангуляцией и надо найти такую прямую внутри многоугольника, чтобы она имела максимум пересечений с диагоналями его триангуляции. Решать задачу можно перебором всех ...
vados inferno's user avatar
0 голосов
1 ответ
2k показов

Центроид четырехугольника

У меня есть четырехугольник со следующими параметрами: Четырехугольник должен быть выпуклым. Невырожденный выпуклый четырехугольник своими диагоналями делится на четыре невырожденных треугольника. ...
user avatar
3 голоса
2 ответа
114 показов

Определить, является ли один треугольник поворотом другого

Вопрос относится к этой задаче ACMP: Ссылка По координатам точек треугольников А и Б нужно определить, можно ли получить А из Б с помощью поворота. Я сравнивал треугольники "в лоб" и считал ...
UnsignedZero's user avatar
1 голос
1 ответ
87 показов

Поиск оптимального кольца

Помогите пожалуйста с решением задания. На вход из файла поступает N-ное количество значений x,y и значение r. Задание состоит в том, чтобы найти координаты точек, являющихся вершинами фигуры Кольцо ...
eternal's user avatar
  • 166
2 голоса
2 ответа
80 показов

Написание программы в С

Программа для вычисления длин сторон прямоугольного треугольника и его площади (вычисление длины должно быть оформлено в виде функции). Вот собственно мои не особо успешные труды: #define ...
MarshalStroheim's user avatar
2 голоса
1 ответ
133 показа

Минимизация расстояний от множества точек до плоскости

Подскажите что почитать или с помощью какого алгоритма лучше сделать следующую процедуру: Есть облако точек, нужно поместить плоскость среди них так, чтобы сумма квадратов расстояний от точек до ...
Даниил Козлов's user avatar
1 голос
1 ответ
503 показа

Как найти косое (псевдоскалярное) произведение векторов?

У меня сразу два вопроса по вычислительной геометрии. Мне необходимо найти косое (псевдоскалярное) произведение векторов, каждый из которых задан двумя точками. Нашел только такую инфу: если векторы ...
faritowich's user avatar
2 голоса
2 ответа
3k показов

Как вычислить перпендикуляр к прямой?

Известны две точки прямой, например, {100, 100} и {200, 200}, и есть точка, не лежащая на прямой, например {200, 100}. Как определить, в какой точке относительно прямой будет перпендикуляр, если ...
Dyno Cris's user avatar
  • 153
0 голосов
1 ответ
60 показов

Эффективный алгоритм поиска общих сегментов полигональной геометрии

Разрабатываю картографический движок для морских навигационных карт. В стандарте указано, что если участки линий друг на друга накладываются (имеют общие сегменты), то участок линии с наименьшим ...
Pavel Saenko's user avatar
2 голоса
2 ответа
864 показа

Как найти координаты пересечения двух отрезков зная их концы и угол при пересечении?

У меня есть координаты двух точек. А(1,7) и Б(8, 2). В коде, угол пересечения прямых, из этих точек, будет динамическим от 90 до -90 градусов (на картинке я показал угол). и для примера взял угол в 45 ...
AZOT KLAS's user avatar
1 голос
0 ответов
49 показов

Лежит ли точка в 3D обьекте (выпуклый или вогнутый)

Нужна помощь по определению нахождения точки XYZ в трехмерном объекте построенным по XYZ точкам(к примеру КуБ) как с вогнутой стороной так и с выпуклой. Для 2D отлично работает алгоритм луча с ...
cryer enable's user avatar
4 голоса
1 ответ
367 показов

Вычисление координат в матрице

Есть 5x5 матрица квадратов в произвольной части экрана. Как найти координаты (x, y) в центре каждого квадрата?
THD's user avatar
  • 43
1 голос
1 ответ
356 показов

Путь между двумя точками

Разбираюсь с перемещением персонажа на стороне сервера. Клиент присылает точку куда выполняется движение персонажа и мне требуется получить координаты каждого тика на протяжении всего пути. Но ...
 Quesadilla's user avatar
0 голосов
0 ответов
82 показа

Расстояние между точками на плоскости

Есть у меня плоскость 255x255 разбитая на квадратные сектора одинакового размера и нужно найти найти расстояние между двумя точками. Сейчас я делаю что-то подобное: (XSector - 1) * 1920 + X (YSector ...
 Quesadilla's user avatar
0 голосов
1 ответ
139 показов

Как преобразовать один многоугольник в другой, используя только параллельный перенос и пропорциональное масштабирование?

На входе даны два многоугольника (перечислены координаты вершин этих многоугольников в порядке их обхода; однако, порядок обхода для разных многоугольников может быть выбран разный). Можно ли ...
Yorn's user avatar
  • 3
1 голос
2 ответа
2k показов

Площадь невыпуклого многоугольника

Задача: Многоугольник (необязательно выпуклый) задан на плоскости перечислением координат вершин в порядке обхода его границы. Определить площадь многоугольника. Написал код для вычисления площади ...
llatibro's user avatar
0 голосов
1 ответ
155 показов

Как реализовать метод определения точки многоугольнику. Метод учёт числа оборотов

мне необходимо реализовать метод учет числа оборотов, подскажите пожалуйста алгоритм моих действий. На данный момент у меня сформирован следующий список действий, одна в некоторых моментах я запутался:...
shlop's user avatar
  • 1
1 голос
1 ответ
960 показов

Расстояние от точки до прямой С++

у меня есть следующий код по нахождению расстояния между точкой и прямой: template<typename T> using point_t = std::pair<T, T>; template<typename T> using line_segment_t = std::...
QuickDzen's user avatar
  • 713
0 голосов
1 ответ
328 показов

Определение попадания точки в многоугольник [закрыт]

Незнаю какой алгоритм придумать для такой задачи...была мысль с лучом соединяющий точку и вершину но с вогнутой фигурой нельзя применить
эдик ерошов's user avatar
1 голос
1 ответ
359 показов

Вычислительная геометрия, уравнение прямой

Имеется ли у кого-то пример кода работающего с полуплоскостями. В частности по уравнению прямой ax+by+c=0, определяющий полуплоскость, в которой однозначно ax+by+c>=0. Нужен просто способ это делать, ...
Berestovsky's user avatar
1 голос
2 ответа
291 показ

Как правильно составить формулу?

В общем, я недавно уже задавал вопрос по поводу программы с циклом и расчета выгодности кредитования. Сильно поменялись условия и реализовывать это надо аля рейтинг в отеле. Изначальный код выглядел ...
Michael Stepanov's user avatar
-1 голос
1 ответ
410 показов

Нахождение расстояния между двумя отрезками на плоскости

Нужна помощь по теме "вычислительная геометрия". Нужно найти расстояние между двумя отрезками на плоскости. На вход дается 8-м чисел которые являются координатами концов этих отрезков, сначала первого,...
BeerBaron's user avatar
2 голоса
1 ответ
363 показа

Как проверить, являются ли прямые скрещивающимися? (N-мерное пространство)

Есть два отрезка в N-мерном пространстве (N < 50), каждый из которых задан двумя точками - началом и концом отрезка. Точки заданы координатами. Необходимо определить, являются ли прямые, на ...
9Pasha's user avatar
  • 1,017
7 голосов
2 ответа
2k показов

Подсчитать число пересечений прямоугольников (кубов)

Для простоты будем рассматривать задачу про прямоугольники (для кубов -- аналогично). Задача состоит в том, чтобы подсчитать суммарную площадь пересечений прямоугольников (или любую другую аддитивную ...
hedgehogues's user avatar
  • 9,251
0 голосов
1 ответ
94 показа

Алгоритм разделения прямоугольника на области для каждой точки

Где-то видел алгоритм с визуализацией, но уже забыл и не могу найти. Есть прямоугольник, на нем - некоторым образом расположены точки. Нужно для каждой точки отчертить/определить границу (для ...
user avatar
2 голоса
1 ответ
178 показов

Как вычислить полигоны модели попадающие во фрустум (прямоугольник)?

Есть сцена, на сцене obj модель. Требуется выделить полигоны модели. Нажимается правая кнопка мыши далее вокруг нажатой точки рисуется прямоугольник, на углах прямоугольника рисуется селектирующие ...
Санаев's user avatar
  • 1,875
1 голос
1 ответ
262 показа

Кратчайший путь до точки

Условие: Дано n точек на координатной плоскости (x,y). Найти прямую, расстояние от любой точки до которой будет минимально. Мое решение: Я думаю, надо перебирать все точки на плоскости, строя из ...
Шерзод Ёров's user avatar
-2 голоса
1 ответ
6k показов

код для точки в треугольнике C++ [закрыт]

Даны три вершины треугольника с координатами (координаты вводятся с клавиатуры) А(х1,y1) B(х2,y2) и С(х3,y3). Имеются координаты еще одной точки D(х4,yх4). Нужно определить, принадлежит эта точка ...
Хомяк 's user avatar
12 голосов
2 ответа
280 показов

Куб минимального объема

На множестве точек n-мерного пространства определить координаты вершин n-мерного гиперкуба содержащего внутри себя все точки исходного множества, гиперкуб должен быть минимального объема. ...
Fil's user avatar
  • 123
-1 голос
1 ответ
934 показа

Как учесть, угол поворота прямоугольника на плоскости

Есть прямоугольник и отрезок, необходимо определить факт пересечения отрезком прямоугольника. if ((p1.x < p2.x) && (p1.y>p2.y)) { p3.x = p1.x; p3.y = p2.y; p4.x = p2.x; ...
user avatar
0 голосов
1 ответ
2k показов

Сортировка точек на плоскости по/против часовой стрелки

Есть набор точек типа std::pair<int, int>, представляющих собой вершины некоторого многоульника (вообще говоря, невыпуклого). Дана некоторая вершина из набора. Необходимо отсортировать набор так,...
iii's user avatar
  • 19
1 голос
1 ответ
385 показов

Определение видимости отрезка

дано N отрезков на плоскости с началом координат в (0, 0) соответственно, расположение которых может быть абсолютно любым последний отрезок назовём красным. необходимо определить - видим ли красный ...
ampawd's user avatar
  • 3,682
3 голоса
2 ответа
2k показов

Не могу разобраться с параметрами кватерниона

Вот что я нашел: Всего у кватерниона четыре компоненты: X, Y, Z и W. XYZ — ось поворота, W — угол поворота. У меня сразу возник вопрос, как ось может описана координатами одной точки, ведь что бы ...
perfect's user avatar
  • 9,941
0 голосов
1 ответ
25 показов

Рассчитать "y" при определенном "x" при известных текущей позиции и скорости объекта

Есть объект, который находится на координатах "x": 200, "y": 200. Перемещается со скоростью 140 по оси "y" и 200 по оси "x". Необходимо определить, какова будет его "y" координата, когда его "x" ...
smellyshovel's user avatar
  • 5,188
1 голос
1 ответ
154 показа

Фиксированное положение фигур - C#

Подскажите, как зафиксировать положение фигур(треугольник и квадрат перемещаются по консоли, когда их координаты совпадут, нужно зафиксировать их положение)? Думаю, что подобным образом: 1-ая фигура ...
Julia Ponomareva's user avatar
0 голосов
0 ответов
26 показов

Увеличить изображение относительно центра своего родителя

Помогите решить задачку. Как вычислить смещение изображения так, чтобы при изменении его масштаба казалось, что область просмотра родителя, словно бы, становится ближе/дальше к изображению? ...
Dmitry V's user avatar
0 голосов
1 ответ
60 показов

Нахождение центра окружности(описанной) по кординатам

У меня такой вопрос. Я получаю от пользователя кординаты 3-ёх точек (x,y). Эти три точки являются вершинами треугольника. Моя задача заключается в том , что я должен найти центр описанной окружности, ...
Jegor Melnik's user avatar
7 голосов
2 ответа
191 показ

Структура данных для упорядочения двумерных точек

Столкнулся с задачей - имеется достаточно много (ну, скажем, десятки тысяч) точек на плоскости (возможно, позже будут в трехмерном пространстве, но пока вопрос о плоскости). Требуется много раз решать ...
Harry's user avatar
  • 215k
0 голосов
6 ответов
2k показов

Каким алгоритмом или формулой можно выяснить, находится ли точка между паралельными прямыми?

Есть две паралельные прямые, заданные уравнениями: a1x + b1y + c1 = 0, a2x + b2y + c2 = 0. Как определить, находится ли точка P(x, y) между ними?
Khusamov Sukhrob's user avatar
6 голосов
4 ответа
6k показов

Задача о покрытии отрезка

Задача в общем виде формулируется так: По данным n отрезкам необходимо найти множество точек минимального размера, для которого каждый из отрезков содержит хотя бы одну из точек. Вполне понятно, что ...
Lescott's user avatar
  • 323
4 голоса
1 ответ
84 показа

Построить 4 нормальные прямые в пространстве от центра фигуры

Здравствуйте! Собственно, реализую редактор поверхностей, основная проблема встала с расчётом "габаритов" кисточки, а точнее, поверхности в пространстве, попадающей под эту самую кисточку. Привожу ...
test123's user avatar
  • 1,042
0 голосов
2 ответа
930 показов

Зарисовать область пересечения двух треуглольников

Собственно, вся задача. Треугольники заданы координатами своих вершин. Как это математически рассчитать я не догадался, но придумал, как "обхитрить" - залить треугольники разными цветами и там, где ...
mushhr's user avatar
  • 1
0 голосов
4 ответа
1k показов

Нахождение внутренней точки многоугольника

У меня есть многоугольник заданный множеством своих вершин и мне необходимо найти внутреннюю точку данного многоугольника. Какие алгоритмы существуют для данной задачи? (кроме перебора)
Error's user avatar
  • 688