0
ответов
Поиск прямоугольников, содержащих точку – эффективный алгоритм
Добрый день. Моя ситуация :В двухмерном -пространстве. Введите :набор прямоугольников (и перекрывающихся прямоугольников ). Координаты прямоугольников имеют целочисленный тип. Никаких ограничений на прямоугольник -...
вопрос задан: 13 May 2019 08:39
0
ответов
Получить альфа-форму (вогнутый корпус) из набора точек, используя Джулию
Я хочу вычислить альфа-форму (или даже только вогнутую оболочку) набора точек, используя Джулию. В других вопросах они решили эту проблему в python, используя границу тесселяции Делоне ...
вопрос задан: 11 March 2019 14:52
0
ответов
Ищем алгоритм, дающий внешнее приближение к выпуклой оболочке множества точек
Я ищу алгоритм (и, возможно, реализацию, которую я могу вызвать из python), решающую следующую проблему: задан набор S из N точек (N порядка 1000) в многомерном пространстве (...
вопрос задан: 18 January 2019 18:27
0
ответов
Наивный график видимости; пересекающиеся отрезки
Я пытаюсь реализовать алгоритм наивного графика видимости (т.е. время выполнения O (n ^ 3)), но столкнулся с несколькими проблемами. Мой подход заключается в следующем: Дано: массив полигонов (представлен массивом [x, ...
вопрос задан: 16 January 2019 17:20
0
ответов
Какой самый быстрый способ найти ближайшая точка к заданной точке?
Какой самый быстрый способ найти ближайшую точку к заданной точке в массиве данных? Например, предположим, что у меня есть массив A трехмерных точек (с координатами x, y и z, как обычно) и точки (x_p, y_p, z_p). ...
вопрос задан: 12 November 2018 13:59
0
ответов
Какой алгоритм наиболее эффективен для поиска прямой линии, проходящей через большинство точек?
Проблема: N точек даны на 2-мерной плоскости. Какое максимальное количество точек на одной прямой? Задача имеет O (N2) решение: пройдите через каждую точку и найдите количество ...
вопрос задан: 19 September 2018 00:16
0
ответов
Как мне обнаружить пересечения между кругом и любым другим кругом в той же плоскости?
Я ищу алгоритм, чтобы определить, пересекается ли круг с любым другим кругом в той же плоскости (учитывая, что могут быть более одного круга в плоскости). Один из найденных мной методов - это ...
вопрос задан: 26 March 2018 00:30
0
ответов
Существует ли надежная реализация алгоритма Бентли-Оттмана на C ++?
Алгоритм Бентли-Османа находит все пересечения в наборе отрезков линии. Для хорошо известного и важного алгоритма кажется довольно странным, что реализация C ++ алгоритма Бентли-Оттмана & ...
вопрос задан: 24 March 2018 12:23
0
ответов
Реализация алгоритма триангуляции Шазеля
Существует алгоритм триангуляции многоугольника за линейное время, созданный Шазелем (1991), но, AFAIK, нет никаких стандартных реализаций его алгоритма в общем математическом программном обеспечении ...
вопрос задан: 13 March 2018 17:56
0
ответов
Асимптотически оптимальный алгоритм для вычисления того, пересекает ли линия выпуклый многоугольник
Алгоритм O (n) для определения пересечения линии с Выпуклый многоугольник состоит в проверке того, пересекает ли какое-либо ребро многоугольника линию, и проверке, является ли количество пересечений нечетным или четным. Здесь ...
вопрос задан: 3 March 2018 23:44
0
ответов
Найти точку ближайшего пересечения в плане
Недавно на собеседовании мне задали следующий вопрос: Допустим, у вас есть следующая сетка в декартовой системе координат (квадрант I). o - x - x - x - o
| | | | |
x - x - x - o - x
| | ...
вопрос задан: 24 December 2017 14:21
0
ответов
Как найти самый большой круг, который лежит в пределах выборной границы?
Данные наборы 2D-моментов, которые являются границами нерегулярной формы, форма, которая не может быть выпуклой и может иметь внутренние отверстия, есть алгоритм Чтобы найти самый большой круг, который вписывается в ...
вопрос задан: 22 October 2017 23:43
0
ответов
Самый большой круг внутри невыпуклого многоугольника
Как мне найти самый большой круг, который может поместиться внутри вогнутый многоугольник? Алгоритм грубой силы в порядке, если он может обрабатывать полигоны с ~ 50 вершинами в реальном времени.
вопрос задан: 22 October 2017 02:02
0
ответов
Как эффективно найти k-ближайших соседей в многомерных данных?
Итак, у меня есть около 16 000 75-мерных точек данных, и для каждой точки я хочу найти ее k ближайших соседей (с использованием евклидова расстояния, в настоящее время k = 2, если это упрощает) Моя первая мысль была ...
вопрос задан: 3 September 2017 07:26
0
ответов
Как проверить, находится ли точка (x, y) внутри многоугольника в декартовой системе координат? [дубликат]
На этот вопрос уже есть ответ здесь: Точка в многоугольнике, также известная как тест на попадание C# Точка в многоугольнике Учитывая случайный многоугольник, сформулированный с помощью уравнений N линий в декартовой системе координат, существует ли ...
вопрос задан: 23 May 2017 12:33
0
ответов
Как быстрее всего проверить, находится ли точка (3D) внутри выпуклой оболочки с учетом по набору точки
я установил P точки (3D), которые являются вершинами выпуклой оболочки (каждой). Я ищу метод проверки, находится ли данная точка p0 НЕ за пределами этой выпуклой оболочки. Придется повторить проверку ...
вопрос задан: 23 May 2017 12:25
0
ответов
как определить, находится ли точка внутри прямоугольника? [дубликат]
Возможный дубликат: определение, лежит ли точка внутри прямоугольника или нет. Есть вопрос интервью: «Как определить, находится ли точка внутри прямоугольника». Обратите внимание, что ...
вопрос задан: 23 May 2017 12:04
0
ответов
найти наименьший содержащий выпуклый многоугольник с заданным количеством точек
учитывая выпуклый полигон и число N, как мне найти наименьший многоугольник, который содержит все точки исходного многоугольника имеет ровно N угловых точек Например, предположим, что у меня есть набор точек...
вопрос задан: 23 May 2017 11:46
0
ответов
Упрощенные (или гладкие) многоугольники, содержащие исходный подробный многоугольник
У меня есть подробный двумерный многоугольник (представляющий географическую область ), который определяется очень большим набором вершин. Я ищу алгоритм, который упростит и сгладит многоугольник (уменьшая ...
вопрос задан: 23 May 2017 10:32
0
ответов
Учитывая набор многоугольников и серию точек, найдите, какие многоугольники являются точками, расположенными
Это вопрос, аналогичный приведенному здесь, но я полагаю, что он было бы полезно, если бы я мог переделать его в более общих терминах. У меня есть набор многоугольников, эти многоугольники могут касаться друг друга, перекрываться ...
вопрос задан: 23 May 2017 10:00
0
ответов
Какой самый быстрый алгоритм вычисления минимального расстояния между двумя наборами точек?
Я хочу найти минимальное расстояние между двумя многоугольниками. Мне нужно найти минимум кратчайшего расстояния между каждой вершиной первой формы и всеми вершинами другой. Что-то вроде ...
вопрос задан: 15 May 2017 11:58
0
ответов
Способ рисования эквидистантной кривой
Я разместил этот вопрос на mathoverflow, но я также хочу узнать ваше мнение по этому поводу. Я хочу нарисовать кривую, которая всегда находится на определенном расстоянии от нормали к поверхности ...
вопрос задан: 13 April 2017 12:57
0
ответов
Определить, находится ли точка внутри выпуклой оболочки для набора точек, не вычисляя сама оболочка
Каков самый простой способ проверить, находится ли точка P внутри выпуклой оболочки, образованной набором точек X? Мне нужен алгоритм, который работает в многомерном пространстве (скажем, до 40 измерений), который не ...
вопрос задан: 29 May 2016 00:50
0
ответов
Учитывая два (больших) набора точек, как я могу эффективно найти пары, которые являются ближайшими друг к другу?
Мне нужно решить вычислительную задачу, которая сводится к поиску взаимно ближайших пар точек между двумя наборами. Проблема выглядит примерно так: задан набор точек A и набор ...
вопрос задан: 6 January 2016 17:27
0
ответов
Поиск диапазона в многомерных R-деревьях
Я пытаюсь реализовать R-Tree в C ++. При реализации Range Queries я обнаружил, что мне нужно проверить пересечение точки (с заданным диапазоном) с многомерным гипер прямоугольником. ...
вопрос задан: 26 December 2015 11:02
0
ответов
Конвергенция точек останова в алгоритме Fortune
Я реализую алгоритм Fortune для вычисления диаграмм Вороного. Моя основная ссылка — «Вычислительная геометрия: алгоритмы и приложения» де Берга и др., и хотя их…
вопрос задан: 15 November 2015 22:24
0
ответов
Как нарисовать круг в GNU Octave
В Matlab вы можете нарисовать круг, просто указав центр и радиус следующим образом: R = 10;
Center = [5,8]; { {1}} круг (Центр, R, 1000, 'b -');
удерживать
график (Центр (1), Центр (2), 'g.') Тот же код for ...
вопрос задан: 30 May 2015 05:21
0
ответов
Как обнаружить граничные вершины 3D-модели с открытой сеткой?
Существует два типа моделей поверхностных сеток: закрытая сетка, такая как сфера или куб, и вторая модель — модель с открытой сеткой, что означает, что поверхность модели не находится в замкнутом контуре. Открыт от...
вопрос задан: 1 March 2015 16:42
0
ответов
Треугольник вписывается внутри другого треугольника
, учитывая длины сторон 2 треугольников. Определите, может ли второй треугольник вписываться в первый треугольник? Для получения более подробной информации прочитайте полное заявление о проблеме ниже: http: //acm.timus.ru / ...
вопрос задан: 21 January 2015 20:29
0
ответов
Как удалить последовательные элементы из Java ArrayList?
Я относительно новый программист на Java, и мне сложно удалить более одного элемента из ArrayList. В идеале я бы хотел сделать примерно так: ArrayList ar1 = new ArrayList ();
как я могу определить, сложен он или нет? Сложный многоугольник имеет пересечен
вопрос задан: 8 May 2014 07:15