Лучшие computational-geometry вопросы ИТ разработчиков

  • 10 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Рассчитать конечную точку с учетом расстояния, пеленга, начальной точки

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

Задан 12 Jul 2010, 04:05 от Sri
  • 6 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Как найти все точки пересечения двух наборов контуров эффективным способом

Мне интересно, как лучше найти все точки пересечения (с ошибкой округления) между двумя наборами контурных линий. Какой метод лучше? Вот пример: import matplotlib.pyplot as plt import numpy as np x = np.linspace(-1,1,500) X,Y = np.meshgrid(x,x) ...

Задан 02 Jul 2013, 01:57 от Pablo
  • 28 голосов
  • 6 ответов
  • 0 просмотров
6 ответов

Как узнать геометрическую медиану

Вопрос в том: Для заданных N точек (в 2D) с координатами x и y найдите точку P (в N заданных точках), чтобы сумма расстояний от других (N-1) точек до P была минимальной. Этот момент обычно известен какГеометрическая ...

Задан 17 Oct 2012, 12:20 от SexyBeast
  • 2 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Путаница с триангуляцией Делоне и крупнейшим вписанным кругом

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

Задан 10 Jan 2015, 04:49 от Linda
  • 6 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

 сложность.

вая выпуклый многоугольник как список против часовой стрелки из n вершин, дайте алгоритм O (lgn), чтобы определить, находится ли данная точка внутри многоугольника. Предположим, что основные операции принимают O (1). Я думаю, что направление: ...

Задан 07 Mar 2011, 18:59 от SecureFish
  • 2 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Поиск в локальном хешировании

Я пытаюсь понять раздел 5. изЭта бумага о LSH, в частности, как создать сгенерированные хэши. Цитирую связанный документ:Учитывая битовые векторы, состоящие ...

Задан 22 May 2016, 16:52 от justHelloWorld
  • 21 голос
  • 6 ответов
  • 0 просмотров
6 ответов

Площадь пересечения прямоугольника с прямоугольником

Ниже 2прямоугольники, Учитывая координаты вершин прямоугольника - (x1, y1) ... (x8, y8), как можно вычислить область перекрывающейся области (белой на рисунке ниже)? Обратите внимание, что: Координаты точек могут быть любымиПрямоугольники могут ...

Задан 04 Nov 2011, 15:00 от Vadim
  • 10 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Sub O (n ^ 2) алгоритм подсчета вложенных интервалов?

У нас есть список интервалов вида[ai, bi], Для каждого интервала мы хотим подсчитать количество других интервалов, которые вложены в него. Например, если у нас было два интервала,A = [1,4] а такжеB = [2,3], Тогда рассчитывать наB было бы0 так ...

Задан 18 Oct 2012, 03:10 от mandy
  • 7 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Вычислительная сложность и форма вложенности

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

Задан 29 Jul 2013, 13:46 от Nik Kyriakides
  • 6 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

Вы можете использовать PMR QuadTree, я сделал один на Java (который отвечал на кинетические обновления), который был эффективен в диапазоне объектов 10-50 КБ. Но +1 R-Tree.

ою графический редактор в C #, где пользователь может размещать узлы, а затем соединять их с направленным или ненаправленным краем. По завершении алгоритм поиска пути A * определяет наилучший путь между двумя узлами. Что у меня есть:Класс Node с ...

Задан 18 May 2011, 09:46 от Dave
  • 7 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

пересечение сегмент-полигон

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

Задан 18 Sep 2010, 16:09 от ricfow
  • 9 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

Оценка позы камеры (OpenCV PnP)

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

Задан 28 Apr 2013, 17:38 от Gouda
  • 9 голосов
  • 5 ответов
  • 0 просмотров
5 ответов

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

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

Задан 01 Mar 2013, 17:37 от philipp
  • 12 голосов
  • 4 ответа
  • 0 просмотров
4 ответа

Генерация новых полигонов из вырезанного полигона (2D)

Я застрял с этой маленькой проблемой, и мой алгоритм для решения этой проблемы неТ для всех случаев. У кого-нибудь есть идеи, как это решить?Вот'Пример п...

Задан 21 Nov 2009, 12:16 от sulf
  • 3 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Триангуляция Делоне с пространственным ограничением [закрыт]

В целях реализации высокопроизводительного алгоритма динамического поиска пути на сфере (в C ++) я заинтересован в выполнении инкрементной ограниченной триан...

Задан 17 Jan 2015, 06:39 от lushr
  • 7 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Геодезические вычисления на треугольных сетках?

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

Задан 12 Sep 2014, 18:27 от jason
  • 34 голосов
  • 10 ответов
  • 0 просмотров
10 ответов

Перпендикуляр на линии от заданной точки

Как нарисовать перпендикуляр на отрезке линии от заданной точки? Мой отрезок линии определяется как (x1, y1), (x2, y2), если я рисую перпендикуляр из точки (x3, y3), и он встречается с линией в точке (x4, y4). Я хочу это выяснить (х4, у4).

Задан 28 Nov 2009, 04:25 от Zinx
  • 1 голос
  • 4 ответа
  • 0 просмотров
4 ответа

(Это журналы base-2.) Вот код, который сделает поиск. Выполнение этого на 30 тыс. Местоположениях и событиях 1M занимает около 40 секунд и включает в себя 16 млн. Расчетов геодезических расстояний. (Путь грубой силы займет около 21 часа.)

я есть список L из ~ 30k местоположений (записанных как пары долгота / широта) и список E из ~ 1 м событий (с местоположениями, записанными как пары долгота ...

Задан 12 Apr 2017, 14:42 от Connor Harris
  • 10 голосов
  • 9 ответов
  • 0 просмотров
9 ответов

Как найти случайную точку в четырехугольнике?

Я должен быть в состоянии установить случайное местоположение для точки маршрута для симулятора полета. Математическая задача проста:«Чтобы найти одно случай...

Задан 17 Jun 2010, 00:34 от MrGreggles
  • 1 голос
  • 1 ответ
  • 0 просмотров
1 ответ

Алгоритм маскирования для расчета излучения

Я работаю над программным обеспечением (Ruby - Sketchup) для расчета радиации (солнца, неба и окружающих зданий) в пределах городской застройки на уровне пеш...

Задан 07 Sep 2014, 11:13 от Rojj
  • 6 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

Выпуклый корпус и SciPy

Я пытаюсь использовать scipy (0.10.1) для быстрого взлома, чтобы визуализировать выпуклую оболочку. Я могу получить выпуклую оболочку, используя следующий код: vecs = [[-0.094218, 51.478927], [-0.09348, 51.479364], [-0.094218, 51.478927], ... ...

Задан 06 Feb 2013, 08:50 от Anony-Mousse
  • 23 голосов
  • 6 ответов
  • 0 просмотров
6 ответов

Алгоритм наименьшего расстояния между точками

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

Задан 21 Oct 2009, 16:57 от geord
  • 2 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

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

У меня есть край многоугольника (выпуклый или вогнутый). Я хочу выяснить, должен ли я, двигаясь прямо от начальной к конечной точке этого края, повернуть нап...

Задан 03 Mar 2014, 22:41 от gvlasov
  • 6 голосов
  • 5 ответов
  • 0 просмотров
5 ответов

Алгоритм нахождения отрезка, перекрывающего два коллинеарных отрезка

ОБНОВЛЕНИЕМоя оригинальная реализация в C #Моя окончательная реализация в C #, основанная на ответах, которые я получил.Учитывая следующие условия, как я мог...

Задан 17 Mar 2014, 14:08 от Stécy
  • 39 голосов
  • 10 ответов
  • 0 просмотров
10 ответов

! Поэтому сначала убедитесь, что полигон прост!

раницы руководства дляXFillPolygon [https://tronche.com/gui/x/xlib/graphics/filling-areas/XFillPolygon.html]: Еслиshape являетсяСложныйпуть может самопересекающийся. Обратите внимание, что смежные совпадающие точки на пути не рассматриваются как ...

Задан 23 Jan 2009, 05:16 от hhafez
  • 31 голос
  • 6 ответов
  • 0 просмотров
6 ответов

@ OlivierMelançon Я думаю, что я мог бы добавить псевдокод, поскольку Gassa предложила более элегантное решение, которое имеет некоторое сходство.

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

Задан 17 Mar 2018, 08:21 от Tapan Vaishnav
  • 4 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Реализация алгоритма Hoey Shamos с C #

Хорошо, теперь я получаю правильную информацию из моего текущего алгоритма! Однако, с проверкой 700 000 полигонов,просто слишком медленно! Предыдущая проблем...

Задан 29 Aug 2013, 11:49 от Evan Parsons
  • 5 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

@JimMischel: ерунда Замечание о том, что самый большой круг всегда касается 3 точек, уменьшает набор решений, который потенциально необходимо найти, чтобы найти оптимальный от бесконечного размера до полинома.

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

Задан 08 Sep 2011, 13:26 от drb
  • 4 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Нахождение полигонов в неориентированном графе

Пожалуйста, смотрите изображение:http://i.stack.imgur.com/NPUmR.jpg [https://i.stack.imgur.com/NPUmR.jpg] У меня есть неориентированный граф, который содержит один или несколько связанных подграфов. Граф определяется набором упорядоченных пар ...

Задан 21 Mar 2012, 11:54 от Dev.D
  • 10 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Вот моя Java реализация этого алгоритма:

ужно найти, если Path2D пересекает себя. Сейчас я делаю это, просто извлекая массив строк из пути и обнаруживая, пересекаются ли они. Но он имеет сложность O (n ^ 2) и поэтому очень медленный. Есть ли более быстрый способ сделать это?

Задан 18 Dec 2010, 16:48 от Rogach
  • 140 голосов
  • 5 ответов
  • 0 просмотров
5 ответов

list.Reverse () .................. Clockwise_order

вая массив точек x, y, как мне отсортировать точки этого массива по часовой стрелке (вокруг их средней средней точки)? Моя цель состоит в том, чтобы передать точки в функцию создания линий, чтобы в итоге получилось нечто «сплошное», настолько ...

Задан 08 Aug 2011, 21:57 от Philipp Lenssen
  • 6 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

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

Алгоритм Бентли-Оттмана работает для нахождения пересечений множества прямых. Но у меня много полилиний: Есть ли способ найти пересечения множества полилиний? Я выясняю, но в то же время, если кто-то может дать некоторые советы или идеи, это ...

Задан 14 Nov 2011, 09:18 от Sam
  • 9 голосов
  • 7 ответов
  • 0 просмотров
7 ответов

C ++ 2D библиотека тесселяции?

У меня есть несколько выпуклых многоугольников, хранящихся как вектор точек STL (более или менее). я бы хотелукладывать мозаику [http://en.wikipedia.org/wiki/Tesselate]их очень быстро, желательно на довольно ровные по размеру кусочки, и без ...

Задан 13 Sep 2009, 21:05 от mpen
  • 11 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Булевы операции над путями SVG [закрыто]

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

Задан 23 Feb 2013, 01:16 от Nik Kyriakides
  • 6 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

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

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

Задан 10 Jan 2011, 12:19 от Ojala
  • 4 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Как эффективнее найти ближайший отрезок к определенной точке?

Это проблема, с которой я часто сталкивался, и я ищу более эффективный способ ее решения. Посмотрите на это фото:Допустим, вы хотите найти кратчайшее расстоя...

Задан 27 Jun 2014, 22:27 от Steve Benett
  • 9 голосов
  • 4 ответа
  • 0 просмотров
4 ответа

Проверьте, не находится ли точка, спроецированная на отрезке, за ее пределами

Смотрите изображение выше; в основном, я хочу простой тест, чтобы проверить, находится ли точка в отрезке 'Диапазон с. Информация (или ввод, если хотите)...

Задан 10 Jul 2013, 20:04 от Xkynar
Page 1 of 3
1 2 3