Вопросы с тегами [delaunay]

0

голосов
0

ответ
4

Просмотры

Кластер расстояния между большим от точки R

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

голосов
0

ответ
42

Просмотры

Ошибка с Delaunay4Points: индексировать из границы

У меня есть эта матрица: v библиотека (DatabionicSwarm) Delaunay4Points (v, IsToroid = FALSE) Ошибка в UniqDelaunay [Uniq2DataInd, Uniq2DataInd]: индекс вне границ Является ли это ошибка? К сожалению, нет Github репо для заполнения вопроса. Я по сравнению с другим инструментом, и результат должен быть: [0,1,0,1,0,0,0,1] [1,0,1,1,0,0,1,1] [0, 1,0,1,1,1,1,1] [1,1,1,0,0,1,0,1] [0,0,1,0,0,1,1,1] [0 , 0,1,1,1,0,0,1] [0,1,1,0,1,0,0,1] [1,1,1,1,1,1,1,0]
1

голосов
1

ответ
57

Просмотры

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

Я в настоящее время с помощью функции Делона в scipy.spatial.Delaunay, как так (упрощенно): импорт NumPy в нп от scipy.spatial импорта Делоне пункта1 = np.random.rand (10,2) points2 = np.random.rand ( 10,2) три = Делон (пункта1) # tri2 = три (points2)? - потребность помочь здесь я хотел бы иметь такую ​​же триангуляцию применяется к point2 - если я бегу Делона снова я мог бы получить другую триангуляцию. Можно ли «копию» один триангуляции и применить его к другому набору точек одного и того же размера?
Shtut
1

голосов
2

ответ
1.1k

Просмотры

координата отображения же, как отображение пикселя в MATLAB для триангуляции Делона

Я должен преобразовать пиксели с одного изображения на другое изображение, при обнаружении признаков. Я вычислил проективную матрицу преобразования. Одно изображения является базовым изображением, а другой является линейно переводится изображением. Теперь я должен определить большую сетку и назначить пиксели из базового изображения к нему. Например, если базовая изображение 20 в точке (1,1), по большей сетке у меня будет 20 ат (1,1). и назначить нули для всех незаполненных значений сетки. Тогда я должен отобразить линейно переведенное изображение на основное изображение и написать свой собственный алгоритм, основанный на «триангуляции Делоне» интерполировать между изображениями. Мой вопрос состоит в том, что, когда я карту переведенного изображения на базовое изображение, я использую понятие (ш, г) = Inv (Т). * (Х, у) А = INV (Т). * В, где (ш, г ) являются координатами базового изображения, (х, у) являются координатами переведенного изображения, А представляет собой матрицу, содержащую координаты (WZ 1) и В является матрица, содержащая координаты (х-1). Если я использую следующий код, я получаю новые координаты, но как я могу связать эти вещи с изображением? Учитываются ли мои пиксели из второго изображения также переводятся на первое изображение? Если нет, то как я могу это сделать? закрыть все; CLC; очистить все; image1_gray = imread ( 'C: \ Users \ Javeria Фарук \ Desktop \ изображения проекта \ a.pgm'); рисунок; imshow (image1_gray); Ось на; Сетка на; Название ( «Базовое изображение»); impixelinfo держись image2_gray = imread ( 'C: \ Users \ изображения проекта Javeria Фарук \ Desktop \ \ j.pgm'); фигура 2); imshow (image2_gray); Ось на; Сетка на; Название ( 'незарегистрированный image1'); impixelinfo% Обнаружение и извлекать объекты из обоих изображений points_image1 = detectSURFFeatures (image1_gray, 'NumScaleLevels', 100 'NumOctaves', 5 ' MetricThreshold», 500); points_image2 = detectSURFFeatures (image2_gray, 'NumScaleLevels', 100 'NumOctaves', 12 'MetricThreshold', 500); [Features_image1, validPoints_image1] = extractFeatures (image1_gray, points_image1); [Features_image2, validPoints_image2] = extractFeatures (image2_gray, points_image2); % особенность Match векторы indexPairs = matchFeatures (features_image1, features_image2, 'Prenormalized', правда); % Получить соответствие точек matched_pts1 = validPoints_image1 (indexPairs (:, 1)); matched_pts2 = validPoints_image2 (indexPairs (:, 2)); рисунок; showMatchedFeatures (image1_gray, image2_gray, matched_pts1, matched_pts2, 'монтаж'); Легенда ( 'соответствуют точки 1', 'соответственных точек 2'); рисунок (5); showMatchedFeatures (image1_gray, image3_gray, matched_pts4, matched_pts3, 'монтаж'); Легенда ( 'соответствуют точки 1', 'соответственных точек 3'); % Вычисление матрицы преобразования, используя RANSAC фигуры [ТГет, inlierFramePoints, inlierPanoPoints, статус] = estimateGeometricTransform (matched_pts1, matched_pts2, 'проективного') (6); showMatchedFeatures (image1_gray, image2_gray, inlierPanoPoints, inlierFramePoints, 'монтаж'); [Млн] = размер (image1_gray); image1_gray = двойной (image1_gray); [X1g, x2g] = meshgrid (т, п)% сетчатой ​​сеткой 2X2 к = imread ( 'C: \ Users \ Javeria Фарук \ Desktop \ образы проекта \ a.pgm'); Ind = sub2ind (размер (к), x1g, x2g); % [TForm1, inlierFramepPoints, inlierPanopPoints, статус] = estimateGeometricTransform (matched_pts4, matched_pts3, 'проективное')% рисунок (7); showMatchedFeatures (image1_gray, image3_gray, inlierPanopPoints, inlierFramepPoints, 'монтаж'); % Invtform = инвертный (ТГогт)% х = invtform% [XQ, YQ] = meshgrid (1: 0,5: 200.5,1: 0,5: 200,5); г = []; А = []; к = 1; % Я didnot знаю, как обращаться к переменной TForm так я написал преобразование% матрицу из переменной структуры TForm Т = [0.99814272, -0,0024304502, -1.2932052e-05; 2.8876773e-05,0.99930143,1.6285858e-06; 0.029063907,67.809265 , 1]% позволяет принимать = 1: 400 так что мой г = 2 и в результате сетка 400х400 для я = 1: 200 для J = 1: 200 A = [A; IJ 1]; г = А * Т; г = [г; г (к, 1) / г (к, 3), г (к, 2) / г (к, 3)]; к = к + 1; конец конец% я преобразовал координаты, но, как присвоить значения ?? % Г (I, J) = C (I, J) d1 = []; d2 = []; для л = 1: 40000 d1 = [d1; А (л, 1)]; d2 = [d2; г (л, 1)]; Х = [d1, d2]; X '= X (:); Конец с1 = []; с2 = []; для л = 1: 40000 с1 = [с1; А (л, 2)]; с2 = [с2; г (л, 2)]; Y = [с1 с2]; Y = Y (:); конец% этого Делон триангуляция вершин, насколько я понимаю% оленья кожа иметь любое значение пикселя любого изображения DT = Триангуляция Делон (X, Y); triplot (ДТ, X, Y);
Jav
1

голосов
2

ответ
492

Просмотры

Как обнаружить сбой во внешнем модуле в Python?

Я использую модуль Triangle для создания стесненных триангуляции Делона (доступной в http://www.lfd.uci.edu/~gohlke/pythonlibs/). В некоторых случаях функция triangle.triangulate падает, а окна говорит: "python.exe перестал отвечать. Я попытался с помощью Try / за исключением структур, как в следующем примере, который завершает работу в аварийном непоследовательно. Я предполагаю, что часть процесса триангуляции является случайным (см «вторичный вопрос», ниже), но я не совсем уверен. Непоследовательность довольно тревожная. Я на Windows. от shapely.geometry импорта многоугольника, MultiPolygon, LINESTRING импорта NumPy как нп импорта треугольника импорта matplotlib.pyplot как PLT импорта matplotlib.tri как три случайного импортной четкость meshXOR (polyRef, форма, otherVerts, otherSegs, otherHole): asarray (Verts), сегменты = np.asarray (SEGS)) печати 'о', чтобы TRI B = triangle.triangulate (А, выбирает = 'пи') # Это тот шаг, который попробовать / за исключением того, не работает на печать ' «попытка: b_t = B [ "треугольники"] ToList (), за исключением:. печать 'Completed Tri не trianlges', если b_t = []: смещ_по_столбцам = [] импорт вкось для три- в b_t: cols.append (random.random ( )) plt.figure () plt.gca () set_aspect ( 'равно') х = np.asarray (Verts) plt.tripcolor (х. [:, 0], [х:, 1], b_t, facecolors = пр .array (перевалы)) три в # для b_t: #print «три является:», [Verts [т] для т в три-] plt.show () еще: печать «нет треугольников» Мой вопрос: есть ли способ сделать нечто вроде «Try / за исключением» структуры, чтобы поймать эту ошибку? С другой стороны, я делаю что-то неправильно с модулем треугольника? EDIT: Решение: цитата из ответа Gamrix приводит к решению. Если точки отделены друг от друга слишком малой разности (евклидово расстояние), функция Triangulate падает. Удаление точек, разделенных на величину меньше, чем 1e-12 решить эту проблему.
Alex Smith
1

голосов
1

ответ
0

Просмотры

CGAL 2D Делоне триангуляции: Как получить все ребра

Как получить / перебирать все ребра в графе 2D Делона в CGAL (C ++)? Например, в среде MATLAB это только ребро (DT).
911
1

голосов
1

ответ
4.2k

Просмотры

Плавное преобразование изображений с триангуляции Делоне

я занимаюсь разработкой простого алгоритма морфинга два изображений с помощью ключевых точек и триангуляцию Делоне. Идея должна быть простой: выбрать пункт управления источником выбрать пункт управления назначения получить триангуляции Делона для источника и назначения кадров для каждого пикселя в исходном изображении получить пиксельные барицентрические координаты, относящиеся к исходному треугольнику, в котором пиксель лежит получить пиксель барицентрическая координата, связанные с треугольником назначения, в котором пиксель лежит с использованием отношения Px = w1 * V0x + w 2 * V1x + W3 * V2x (то же самый для у, и пиксельное назначения) назначить OUT [PdestX, PdestY] = IN [Рх , Py]. Но это не работает X_x Это мой источник MATLAB: функция из = myMorph (im1, p_source, p_dest, tri_source, tri_dest) [HW] = размер (im1); % Получают единичные векторы-столбцы для источника и назначения управления изображением точек Psource_x = p_source (:, 1); Psource_y = p_source (:, 2); Pdest_x = p_dest (:, 1); Pdest_y = p_dest (:, 2); % Для каждого промежуточного кадра ... из = нули (размер (im1)); % Получить треугольники. Каждый массив 3n х 2, где п число треугольников triangles_source = []; triangles_dest = []; для г = 1: размер (tri_source, 1) triangle_s = getTriangle (Psource_x, Psource_y, tri_source, я); triangle_d = getTriangle (Pdest_x, Pdest_y, tri_dest, я); triangles_source = кошка (1, triangles_source, triangle_s); triangles_dest = кошка (1, triangles_dest, triangle_d); конец% итерация каждого пиксель при й = 1: ч при у = 1: ш% получить источник и треугольник назначения для пикселя [х]% исходного треугольника при т = 1: 3: размера (triangles_source, 1) -2 [w1, w2, w3, inTriangle] = inTri (х, у, ... triangles_source (т, 1), triangles_source (т, 2), ... triangles_source (т + 1,1), triangles_source (т + 1,2), ... triangles_source (т + 2,1), triangles_source (т +2,2)); если (inTriangle == 1) перерыва; % Точка [х, у] должны принадлежать к одному (и только) конец треугольника конец% исходного треугольника к = 1: 3: размер (triangles_dest, 1) -2 [W1D, w2d, W3D, inTriangleD] = inTri (х, у, ... triangles_dest (к, 1), triangles_dest (к, 2), ... triangles_dest (к + 1,1), triangles_dest (к + 1,2), ... triangles_dest (к + 2,1 ), triangles_dest (к + 2,2)); если (inTriangleD == 1) перерыва; конец конец v_source = [w1 * triangles_source (т, 1) + ... ш2 * triangles_source (т + 1,1) + ... W3 * triangles_source (т + 2,1), ... w1 * triangles_source (т, 2) + ... w 2 * triangles_source (т + 1,2) + ... w3 * triangles_source (т + 2,2)]; v_dest = [W1D * triangles_dest (к, 1) + ... w2d * triangles_dest (к + 1,1) + ... W3D * triangles_dest (к + 2,1), ... W1D * triangles_dest (к, 2 ) + ... w2d * triangles_dest (к + 1,2) + ... W3D * triangles_dest (к + 2,2)]; если (inTriangle ~ = 1 && inTriangleD ~ = 1) продолжить; Конец v_source = круглый (v_source); v_dest = круглый (v_dest); если (v_source (1)> 0 && v_source (1) 0 && v_source (2) 0 && v_dest (1) 0 && v_dest (2) исходного изображения% IM2 -> конечное изображение% linesNum -> количество линий функции [Р] = getControlPoints (им, controlPtsNum) закрыть все нули Р ​​= (controlPtsNum, 2); % от линии выбора фигуры исходного изображения; imshow (им, []); название ( 'выберите контрольные точки') для I = 1: controlPtsNum% получить точки управления источником [х, у] = ginput (1); Р (я, :) = [х, у]; держать на участке (х, у, 'о', 'Цвет', 'R'); удержать конечные% Получить контрольные точки, используемые для трансформироваться им в другое изображение и делать Делон% триангуляции, используя контрольные точки% им -> исходного изображения% IM2 -> конечное изображение% controlPtsNum -> количество функции контрольных точек [Р, три] = getControlPointsAndTriangulate (им, controlPtsNum) P = getControlPoints (IM, controlPtsNum); [HW] = размер (им); % Добавить углы контролировать точки Р = кошка (1, Р, [1 1]); Р = кошка (1, Р, [ш 1]); Р = кошка (1, Р, [1 час]); Р = кошка (1, Р, [WH]); три = Делон (Р (:, 1), Р (:, 2)); держать на triplot (три, Р (:, 1), Р (:, 2)) удерживать и эта функция (я нашел в сети), тест, если точка лежит на данном треугольнике, и вернуть U, V, ш значения: функция [w1, w2, w3, г] = inTri (Vx, Vy, V0x, V0y, V1x, V1Y, V2x, v2y) %%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%% inTri проверяет, является ли входная точка (Vx, Vy) находится в треугольнике, вершины которого% (V0x, V0y), (V1x, V1Y) и (V2x, v2y) и возвращает линейная комбинация% вес, т.е. ъх = w1 * V0x + w 2 * V1x + W3 * V2x и% уу = w1 * V0y + w 2 * V1Y + W3 * v2y. Если точка находится в треугольнике, то%, что соответствует г будет 1, а в противном случае 0.%% Эта функция принимает несколько входов точки, например, для двух точек (1,2),% (20,30), V = (1 , 20) и уу = (2, 30). В этом случае, w1, w2, w3 и г будут векторы%. Эта функция принимает только вершины одного треугольника. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%% V0x = repmat (V0x, размер (ух, 1), размер (ух, 2)); V0y = repmat (V0y, размер (ух, 1), размер (ух, 2)); V1x = repmat (V1x, размер (ух, 1), размер (ух, 2)); V1Y = repmat (V1Y, размер (ух, 1), размер (ух, 2)); V2x = repmat (V2x, размер (ух, 1), размер (ух, 2)); v2y = repmat (v2y, размер (ух, 1), размер (ух, 2)); w1 = ((ух-V2x) * (V1Y-v2y) -.. (уу-v2y) * (V1x-V2x)) / ... ((V0x-V2x) * (V1Y-v2y) -.. (V0y -v2y) * (V1x-V2x) + EPS). w2 = ((ух-V2x) * (V0y-v2y) -.. (уу-v2y) * (V0x-V2x)) / ... ((V1x-V2x) * (V0y-v2y) -.. (V1Y -v2y) * (V0x-V2x) + EPS). W3 = 1 - w 1 - w 2; г = (w1> = 0) и (w2> = 0) и (w3> = 0) и (w1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%% V0x = repmat (V0x, размер (ух, 1), размер (ух, 2)); V0y = repmat (V0y, размер (ух, 1), размер (ух, 2)); V1x = repmat (V1x, размер (ух, 1), размер (ух, 2)); V1Y = repmat (V1Y, размер (ух, 1), размер (ух, 2)); V2x = repmat (V2x, размер (ух, 1), размер (ух, 2)); v2y = repmat (v2y, размер (ух, 1), размер (ух, 2)); w1 = ((ух-V2x) * (V1Y-v2y) -.. (уу-v2y) * (V1x-V2x)) / ... ((V0x-V2x) * (V1Y-v2y) -.. (V0y -v2y) * (V1x-V2x) + EPS). w2 = ((ух-V2x) * (V0y-v2y) -.. (уу-v2y) * (V0x-V2x)) / ... ((V1x-V2x) * (V0y-v2y) -.. (V1Y -v2y) * (V0x-V2x) + EPS). W3 = 1 - w 1 - w 2; г = (w1> = 0) и (w2> = 0) и (w3> = 0) и (w1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%% V0x = repmat (V0x, размер (ух, 1), размер (ух, 2)); V0y = repmat (V0y, размер (ух, 1), размер (ух, 2)); V1x = repmat (V1x, размер (ух, 1), размер (ух, 2)); V1Y = repmat (V1Y, размер (ух, 1), размер (ух, 2)); V2x = repmat (V2x, размер (ух, 1), размер (ух, 2)); v2y = repmat (v2y, размер (ух, 1), размер (ух, 2)); w1 = ((ух-V2x) * (V1Y-v2y) -.. (уу-v2y) * (V1x-V2x)) / ... ((V0x-V2x) * (V1Y-v2y) -.. (V0y -v2y) * (V1x-V2x) + EPS). w2 = ((ух-V2x) * (V0y-v2y) -.. (уу-v2y) * (V0x-V2x)) / ... ((V1x-V2x) * (V0y-v2y) -.. (V1Y -v2y) * (V0x-V2x) + EPS). W3 = 1 - w 1 - w 2; г = (w1> = 0) и (w2> = 0) и (w3> = 0) и (w1 V2x = repmat (V2x, размер (ух, 1), размер (ух, 2)); v2y = repmat (v2y, размер (ух, 1), размер (ух, 2)); w1 = ((ух-V2x) * (V1Y-v2y) -.. (уу-v2y) * (V1x-V2x)) / ... ((V0x-V2x) * (V1Y-v2y) -.. (V0y -v2y) * (V1x-V2x) + EPS). w2 = ((ух-V2x) * (V0y-v2y) -.. (уу-v2y) * (V0x-V2x)) / ... ((V1x-V2x) * (V0y-v2y) -.. (V1Y -v2y) * (V0x-V2x) + EPS). W3 = 1 - w 1 - w 2; г = (w1> = 0) и (w2> = 0) и (w3> = 0) и (w1 V2x = repmat (V2x, размер (ух, 1), размер (ух, 2)); v2y = repmat (v2y, размер (ух, 1), размер (ух, 2)); w1 = ((ух-V2x) * (V1Y-v2y) -.. (уу-v2y) * (V1x-V2x)) / ... ((V0x-V2x) * (V1Y-v2y) -.. (V0y -v2y) * (V1x-V2x) + EPS). w2 = ((ух-V2x) * (V0y-v2y) -.. (уу-v2y) * (V0x-V2x)) / ... ((V1x-V2x) * (V0y-v2y) -.. (V1Y -v2y) * (V0x-V2x) + EPS). W3 = 1 - w 1 - w 2; г = (w1> = 0) и (w2> = 0) и (w3> = 0) и (w1
sultanofswing.90
1

голосов
1

ответ
637

Просмотры

CGAL - неправильный индекс вершины извлекаться после триангуляции Делоне в 3D

Я использую последнюю CG (4.5) с VS2012. После того, как триангуляции Делоне, я вывожу весь тетраэдр сетки на «testFile1» с выходом потока по умолчанию CGAL триангуляции Делоне в. Данные в «testFile1» правильно. (Я представлял себе сетку и это нормально) Тогда я перебрать все тетраэдры и получить индекс и выводить их Вершины к „testFile2“, но индексы совершенно разные с показателями в "testFile1". Я представлял себе сетку, и это полностью беспорядок. Я также выход положение вершина каждого тетраэдра в моих собственных итераций, они же с testFile1 (коорд 1-й вершины 1-го тетраэдра то же самое, и так далее). Таким образом, тетраэдр testFile1 и testFile2 одно и то же, проблема заключается в получении индексов вершин. мой код: станд :: вектор V; V.reserve (pointCount);
Wood
1

голосов
1

ответ
381

Просмотры

Как я могу получить диаграммы Вороного на эритроцитарной с использованием XYZ координат точек и данных подключения лица из триангуляции Делоне?

UPDATE (1/12/14): Уважаемые все, я пытался все, что я могу закодировать алгоритм д-ра Darren ниже в MATLAB, но я все же добиться успеха с ним. Я смиренно прошу, что добрый самаритянин должен любезно помочь мне с кодом и делиться м-файл. Еще раз спасибо. Я намерен получить диаграммы Вороного на РБК с использованием MATLAB / FORTRAN. Мне нужно следующую конкретную информацию. Вороного вершин, используя обычный вектор для каждого треугольника Делоне; Порядок каждого многоугольника Вороного; списки вершин Вороного, которые определяют многоугольники Вороного; Компонент нормалей на полигоны Вороного; Области полигонов Вороного; Центроиды полигонов Вороного; Наконец, участок Вороного многоугольники с помощью PATCH; Вы можете найти ссылку на соответствующие текстовые файлы, которые содержат RBC_1 XYZ узел координаты на РБК и RBC_2, которые содержат данные о лице подключения от триангуляции Делоне (RBC_1 и RBC_2 в Zip файл). https://www.dropbox.com/s/slan053xbr2e864/RBC.zip?dl=0 я пытался следить за работой Джона Burkardt для единичной сферы: http://people.sc.fsu.edu/~jburkardt/ m_src / sphere_voronoi / sphere_voronoi.html но не работает. Заранее спасибо. NB Любые комментарии и советы будут высоко оценены.
Adesola Ademiloye
1

голосов
1

ответ
1.6k

Просмотры

Представление поверхности LiDAR с использованием 3D триангуляции Делоне в качестве основы?

Я хотел бы представлять собой поверхность, с 3D триангуляции Делоне. Вершины должны быть мой первоначальный ввод данных, точка LiDAR облако из городской местности. Таким образом, поверхность должна регулировать / адаптировать входную информацию. На самом деле, что мне нужно сделать, это следующее: у меня есть облако 3D точки (х, у, г) из городской местности; Мне нужно, чтобы представить поверхность этой области; Я хотел бы сделать 3D триангуляции Делоне (я сделал с CGAL и я получил тетраэдры) и определить только треугольники, которые представляют поверхность (с CGAL у меня есть 4 вершины, и я не могу определить, какие из них представляют собой поверхностный треугольник); Так как эти поверхностные треугольники известны, мне нужно дать точку и получить треугольник, содержащий эту заданную точку. Я хотел бы знать, какие функции мне нужно. Я видел «поколение сетки 3D поверхности», "
ricãO
1

голосов
1

ответ
117

Просмотры

Как триангуляции из диаграммы Вороного?

Я вычислил диаграмму Вороного из набора точки (с Boost.polygon). Я пытаюсь найти триангуляции Делона, соединяя каждый мобильный центр для каждого края Вороного, но пропустить некоторые края. В следующем изображении, красные точки мои начальные точки, синие линии края Вороной (я игнорировал бесконечные ребра), и зеленые линии являются триангуляции края (на зеленой кромке для каждого голубого края, соединяющие две клеточных происхождений). Мы можем видеть, что диагональные ребра отсутствуют. Что мне не хватает?
arthur.sw
1

голосов
3

ответ
2.3k

Просмотры

C ++: CGAL 2D Делоне триангуляции: Вогнутые формы

В настоящее время я в CGAL для некоторых 2D задач триангуляции, и я также получил что-то просто работать Allready. Во всяком случае, я действительно не понимаю, как триангуляции вогнутых форм, так как сейчас я всегда получаю выпуклую оболочку всех точек. В основном я хочу, чтобы добавить точки на Mouseclick аналогично тому, как это работает в иллюстратор так, что все точки в порядке их являются контуры фигуры. Как я могу это сделать с CGAL? Простой пример того, как триангуляции вогнутых форм вообще бы Propably поставил меня на правильном пути! Спасибо!
moka
1

голосов
1

ответ
46

Просмотры

Есть ли упорядочение сетки изменения элемента от прогона к прогону для стесненного триангуляции под CGAL?

Я перебрать finie_vertieces, finite_edges и finite_faces после создания ограниченного Делоне триангуляции с оптимизацией Лойд. Я на VS2012 с помощью CGAL 4.12 в режиме выпуска. Я вижу в данном случае finite_verices список повторяемый (так это список вершин под finite_faces), однако, упорядочение ребер в finite_edges, кажется, изменяется от запуска к запуску для авто (из числа СПЭ = cdtp.finite_edges_begin (!), Из числа СПЭ = cdtp.finite_edges_end (); ++ еи) {сопз авто isConstrainedEdge = cdtp.is_constrained (* еи); Авто & cFace = * (eit-> первая); автоматический cwVert = cFace.vertex (cFace.cw (eit-> второй)); автоматическое ccwVert = cFace.vertex (cFace.ccw (eit-> второй)); Я использую выше фрагмент коды для извлечения списка вершин и списка вершин с заданным краевым меняется от запуска к запуску. Приветствуется любая помощь в этом решении, как я ищу последовательное поведение в коде. Моя триангуляция включает в себя множество ограничений строки на двумерной области.
user6386155
1

голосов
2

ответ
531

Просмотры

Как создать объект Триангуляции Делона из существующей триангуляции в MATLAB

У меня есть существующие триангуляции (вершины х и у и матрица связности три), и я хотел бы применить метод PointLocation класса Триангуляции Делона на этой существующую триангуляции (так же, как устаревшая функция TSearch в старых версиях MATLAB). Однако метод PointLocation очевидно, нужен экземпляр Триангуляции Делона в качестве входных данных. Класс Триангуляции Делона всегда кажется, выполняет свою собственную процедуру триангуляции, что приводит к различной матрице смежности, чем существующие матрицы три- у меня есть, учитывая вершину х и у. Есть ли способ применить PointLocation (или что-то вроде TSearch) к моей существующей триангуляции? У меня есть Matlab 2013a.
mrad
1

голосов
2

ответ
842

Просмотры

Беспорядок на триангуляции Делона и сама большая вписанная окружность

Мне нужно найти наибольшую вписанную окружность выпуклого многоугольника, я искал много сайтов, и я понимаю, что это может быть сделано с помощью триангуляции Делоне. Я нашел нить в CGAL обсуждения с помощью алгоритма с помощью CGAL: Вы можете вычислить это легко с CGAL: Во-первых, вычислить триангуляционную точек. Затем итерация по всем конечным граням триангуляции. Для каждого конечного лица F вычислить его Окружность Ĉ локализовать с в триангуляции (для ускорения вещи, вы можете дать одну вершины е в качестве исходной подсказки расположения точки), если лицо, возвращенное местонахождения (с, намек) конечен, то окружности с лежит в выпуклой оболочке точек, поэтому, е является кандидатом, если е такого кандидата лицо, вычислить его Квадраты держать только описанной окружности лица с минимальным квадратом The CGAL описанной окружности ручной (глава 2D триангуляции, вместе с несколькими вещами из ядра) показывает все основные функции, чтобы сделать это. Я был немного смущен с последней частью этого алгоритма. Когда я прочитал, что я понимаю, от этого является то, что минимальная описанной окружностью триангуляции поверхности является радиусом наибольшего inscibed круга. Но из примеров многоугольника с триангуляцией Делоне, кажется, что даже самая маленькая, иногда не окружность может поместиться внутри многоугольника, так как это может имеет тот же радиус, как самую большую вписанную окружность? Когда я прочитал, что я понимаю, от этого является то, что минимальная описанной окружностью триангуляции поверхности является радиусом наибольшего inscibed круга. Но из примеров многоугольника с триангуляцией Делоне, кажется, что даже самая маленькая, иногда не окружность может поместиться внутри многоугольника, так как это может имеет тот же радиус, как самую большую вписанную окружность? Когда я прочитал, что я понимаю, от этого является то, что минимальная описанной окружностью триангуляции поверхности является радиусом наибольшего inscibed круга. Но из примеров многоугольника с триангуляцией Делоне, кажется, что даже самая маленькая, иногда не окружность может поместиться внутри многоугольника, так как это может имеет тот же радиус, как самую большую вписанную окружность?
Linda
3

голосов
1

ответ
655

Просмотры

How to include all points into error-less triangulation mesh with scipy.spatial.Delaunay?

I am testing scipy.spatial.Delaunay and not able to solve two issues: the mesh has errors the mesh doesn't include all points Code and image of plot: import numpy as np from scipy.spatial import Delaunay,delaunay_plot_2d import matplotlib.pyplot as plt #input_xyz.txt contains 1000 pts in "X Y Z" (float numbers) format points = np.loadtxt("input_xyz.txt", delimiter=" ", usecols=(0, 1)) tri = Delaunay(points) delaunay_plot_2d(tri) plt.plot(points[:,0], points[:,1], 'o') plt.show() As mentioned under scipy.spatial.Delaunay: "Unless you pass in the Qhull option “QJ”, Qhull does not guarantee that each input point appears as a vertex in the Delaunay triangulation." But if I use QJ: tri = Delaunay(points, qhull_options = "QJ") I get Qhull error and if I use QJn (n=some high number): tri = Delaunay(points, qhull_options = "QJ200") to overcome that error the generated mesh looks terrible - triangles all over the place crossing each other. How to include all points into error-less triangulation mesh with scipy.spatial.Delaunay?
Miro
5

голосов
1

ответ
2.4k

Просмотры

Интерполяция с триангуляции Делоне

Имея точку помутнения формы, как какое-то искаженного параболоида, я хотел бы использовать триангуляционный интерполировать точки. Я пробовал другие методы (f.ex. сплайнов), но не удалось провести в жизнь желаемое поведение. Мне было интересно, если есть быстрый способ использовать результаты scipy.spatial.Delaunay в пути, где я могу дать (х, у) COORDS и получить Z-коорд точки на симплекс (треугольник). Из документации выглядит как я могу вытащить индекс симплекс, но я не знаю, как взять его оттуда.
NoIdeaHowToFixThis
5

голосов
1

ответ
542

Просмотры

Difference between Matlab delaunayn and Scipy Delaunay

I'm trying to replicate an N dimensional Delaunay triangulation that is performed by the Matlab delaunayn function in Python using the scipy.spatial.Delaunay function. However, while the Matlab function gives me the result I want and expect, scipy is giving me something different. I find this odd considering both are wrappers of the QHull library. I assume Matlab is implicitly setting different parameters in its call. The situation I'm trying to replicate between the two of them is found in Matlab's documentation. The set up is to have a cube with a point in the center as below. The blue lines I provided to help visualize the shape, but they serve no purpose or meaning for this problem. The triangulation I expect from this results in 12 simplices (listed in the Matlab example) and looks like the following. However this python equivalent produces "extra" simplices. x = np.array([[-1,-1,-1],[-1,-1,1],[-1,1,-1],[1,-1,-1],[1,1,1],[1,1,-1],[1,-1,1],[-1,1,1],[0,0,0]]) simp = scipy.spatial.Delaunay(x).simplices The returned variable simp should be an M x N array where M is the number of simplices found (should be 12 for my case) and N is the number of points in the simplex. In this case, each simplex should be a tetrahedron meaning N is 4. What I'm finding though is that M is actually 18 and that the extra 6 simplices are not tetrahedrons, but rather the 6 faces of the cube. What's going on here? How can I limit the returned simplices to only be tetrahedrons? I used this simple case to demonstrate the problem so I'd like a solution that isn't tailored to this problem. EDIT Thanks to an answer by Amro, I was able to figure this out and I can get a match in simplices between Matlab and Scipy. There were two factors in play. First, as pointed out, Matlab and Scipy use different QHull options. Second, QHull returns simplices with zero volume. Matlab removes these, Scipy doesn't. That was obvious in the example above because all 6 extra simplices were the zero-volume coplanar faces of the cube. These can be removed, in N dimensions, with the following bit of code. N = 3 # The dimensions of our points options = 'Qt Qbb Qc' if N
zephyr
5

голосов
1

ответ
3.9k

Просмотры

CGAL - Получить индекс Vertex После триангуляции Делоне

Я вычисление 2D триангуляции Делона в несколько тысяч пунктов. Каждая точка имеет больше данных, связанные с ним за й и у координат. Поэтому мне было интересно, если это возможно, чтобы получить индекс каждой точки, так что я могу получить доступ к собственной точке структуры в другом векторе. В настоящее время, как я получить доступ вершины из Face_handle, она возвращает точку (т.е. х, у координаты) Как я могу вернуть каждую вершину его ID (индекс) вместо его х, у координаты? Спасибо. #include #include #include ЬурейеЕ CGAL :: Exact_predicates_inexact_constructions_kernel ядра; ЬурейиЙ CGAL :: Delaunay_triangulation_2 Делон; TYPEDEF Kernel :: Point_2 точка; Пример недействительными () {станд :: вектор точки; points.push_back (точка (1,1)); // Индекс 0 points.push_back (точка (1,2)); // индекс 1 points.push_back (точка (1,3)); // индекс 2 points.push_back (Point (2,1)); // Индекс 3 points.push_back (точка (2,2)); // Индекс 4 points.push_back (точка (2,3)); // индекс 5 триангуляции Делоне; triangulation.insert (points.begin (), points.end ()); для (Делоне :: Finite_faces_iterator подходят = triangulation.finite_faces_begin (!), подходят = triangulation.finite_faces_end (); ++ подходит) {Делоне :: Face_handle лицо = подходит; станд :: соиЬ
socratic
3

голосов
4

ответ
951

Просмотры

Скотина-Force Constrained триангуляции Делоне?

Мне нужно, чтобы создать треугольник сетку из множества точек. Комплект имеет очень мало точек, так что не нужно быть быстрым или оптимизированы (я буду иметь дело с максимум 100 баллов). Сетка должна быть ограничена «триангуляции Делоне». На изображении ниже я показал (на левой стороне) множество точек начинают из (синих и красных точек). Я также знаю, связь между этими точками (очертание в черном). Сетка должна выглядеть как пример справа (включая края в сером цвете, которые образуют внешние и внутренние треугольники). Я не могу использовать библиотеки. Я посмотрел на множество различных алгоритмов. Их много, и это легко спутать. Я хотел бы знать, если есть наивная и, таким образом, мы надеемся, более простой алгоритм можно использовать для получения сетки на правой? Грубая сила подход отлично (пс: Я могу сделать триангуляцию Делоне).
user18490
6

голосов
1

ответ
10.9k

Просмотры

Python выпуклая оболочка с scipy.spatial.Delaunay, как eleminate точки внутри корпуса?

У меня есть список 3D точек в np.array называется pointsList, значения с плавающей точкой: [[1, 2, 10.], [2, 0, 1.], [3, 6, 9 .], [1., 1., 1.], [2., 2., 2.], [10, 0, 10], [0, 10., 5], ... и т.д. Этот код триангуляционный облака точек: импорт NumPy как нп импорт scipy.spatial три- = scipy.spatial.Delaunay (pointsList) # Делон индексы триангуляции = tri.simplices # индексы вершин вершины = точки [индексы] # вершина для каждого тетраэдра Однако до этого шага триангуляции, я хотел бы, чтобы удалить из моего списка всех точек, которые находятся внутри выпуклая оболочка решения было бы создать новую np.array имени список, и хранить их там , Но какая функция в SciPy (или любое другое решение), будет делать это? Как я могу запрограммировать эту операцию? Спасибо
5

голосов
1

ответ
1.1k

Просмотры

Как работать с CGAL циркуляционных?

Я пытаюсь сделать Делон триангуляцию множества точек, найти ближайшую точку к входной точке, и получить его инцидентные вершины, но как-то следующий код не работает. #include #include #include ЬурейеЕ CGAL :: Exact_predicates_inexact_constructions_kernel K; ЬурейеЕ CGAL :: Delaunay_triangulation_2 триангуляции; ЬурейиЕ триангуляции :: Edge_iterator Edge_iterator; TYPEDEF триангуляции :: Точка Точка; ЬурейиЕ триангуляции :: Vertex_handle Vertex_handle; ЬурейиЕ триангуляции :: Vertex_circulator Vertex_circulator; ИНТ основной () {станд :: ifstream в ( "data.txt"); утверждают, (в); станд :: istream_iterator начать (в); конец станд :: istream_iterator; Триангуляции Т; T.insert (начало, конец); станд :: соиЬ
aptypr
11

голосов
7

ответ
7.5k

Просмотры

Как найти все сосед данной точки в триангуляционном с использованием scipy.spatial.Delaunay?

Я искал ответ на этот вопрос, но не могу найти что-нибудь полезное. Я работаю с питона научных вычислений стеки (SciPy, NumPy, Matplotlib) и у меня есть набор 2 мерных точек, для которых я вычислим traingulation Делона (вики) при помощи scipy.spatial.Delaunay. Мне нужно написать функцию, которая, учитывая любую точку а, будет возвращать все остальные точки, которые являются вершинами любого симплекса (т.е. треугольника), что также является вершина (соседи А в триангуляции). Однако, документация для scipy.spatial.Delaunay (здесь) очень плохо, и я не могу за жизнь мне понять, как быть указаны симплекс или я бы об этом. Даже просто объяснение того, как соседи, вершины и vertex_to_simplex массивы в выходе Делоне организованы было бы достаточно, чтобы заставить меня идти.
James Porter
3

голосов
4

ответ
540

Просмотры

Какой должна быть вне положенный алгоритма Делоне сетки триангуляции для 3-Dimension?

Если есть входные точки: в алгоритм Делоне сетки триангуляции, то, что будет выход алгоритма Делоне сетки триангуляции для 3-Dimension? A. Это один: или B. Это один [ConvexHull всех заданных точек входа] Что такое ваш ответ? А или В
Pritesh
1

голосов
3

ответ
2k

Просмотры

Интерполяция с триангуляции Делоне (п-тусклый)

Я хотел бы использовать триангуляции Делоне в Python интерполировать точки в 3D. Что у меня есть # мой массив точек точек = [[1,2,3], [2,3,4], ...] # мой массив значений значений = [7, 8, ...] # объект с триангуляции Делоне = три- (точки) # набор из точек, в которых я хочу, чтобы интерполировать р = [[1.5, 2.5, 3.5], ...] # это становится симплексов, содержащих заданные точки S = ​​(р tri.find_simplex ) # это становится вершины для симплексов V = tri.vertices [s] Я только смог найти один ответ здесь, что предлагают использовать метод преобразования для интерполяции, но, не будучи более специфичным. Что мне нужно знать, как использовать вершины, содержащий симплекс, чтобы получить весовые коэффициенты для линейной интерполяции. Давайте предположим, что общий п-тусклый случай так, что ответ не зависит от размерности. РЕДАКТИРОВАТЬ:
mib0163
2

голосов
4

ответ
3.3k

Просмотры

Как найти триангуляции Делоне грани, содержащие заданные точки

Я нанесены п случайных точек (черные точки) и использовали триангуляции Делоне, теперь я хочу интерполировать т случайных точек оценки (красные точки), поэтому мне нужно, чтобы вычислить какой треугольник точка оценки находится внутри. Какой подход для вычисления вершин треугольника для каждой точки?
Chris Seymour
6

голосов
2

ответ
4.1k

Просмотры

Как вырезать треугольники из вогнутой триангуляции Делоне?

Я использую Делон триангуляцию вогнутого полигона, но он заполняет углубления. Как автоматически удалить треугольники, которые находятся вне границ полигона?
Archagon
2

голосов
1

ответ
395

Просмотры

CGAL: 2D Constrained триангуляции Делоне - Добавление информации ограничений

Можно прикрепить информацию (например, Интс) в точках, прежде чем добавить их к объекту triangulator. Я делаю это, так как мне нужно с одной стороны ИНТ-флаг, который я использую Lateron определить свои координаты текстуры, а с другой стороны, индекс, который я использую, так что я могу создать индексированную VBO. http://doc.cgal.org/latest/Triangulation_2/Triangulation_2_2info_insert_with_pair_iterator_2_8cpp-example.html Но вместо очков я только хочу, чтобы вставить ограничительный край. Если я вставляю как CGAL возвращает странные результаты, так как точки кормили в два раза (один раз в качестве точки и один раз в качестве точки сдавленным края). http://doc.cgal.org/latest/Triangulation_2/Triangulation_2_2constrained_8cpp-example.html Можно ли подключить таким же образом, как и с точкой информации «Ограничения», так что я могу использовать только эту функцию CDT. insert_constraint (точка (у, 0), точка (у, 6)); прежде чем я перебирать результирующее лицо? Lateron когда петля над треугольниками мне нужно каким-то образом получить доступ к Инт-флаги, которые я определены ранее. Как это, но не на acutal очков, но «концов» сегмент, определенное ограничение края: для (CDT :: Finite_faces_iterator подходит = m_cdt.finite_faces_begin () подходит = m_cdt.finite_faces_end (); ++ подходит, ++! к) {Int J = K * 3; для (INT I = 0; я <3; я ++) {индексы [J + I] = ПРИГОДНОСТИ> вершина (я) -> информация () первый. }} Этот вопрос является частью другого вопроса я разместил здесь: стесненный (Делон) триангуляция. Поскольку это вопрос его собственного я отправил его во второй раз независимо друг от друга. прежде чем я перебирать результирующее лицо? Lateron когда петля над треугольниками мне нужно каким-то образом получить доступ к Инт-флаги, которые я определены ранее. Как это, но не на acutal очков, но «концов» сегмент, определенное ограничение края: для (CDT :: Finite_faces_iterator подходит = m_cdt.finite_faces_begin () подходит = m_cdt.finite_faces_end (); ++ подходит, ++! к) {Int J = K * 3; для (INT I = 0; я <3; я ++) {индексы [J + I] = ПРИГОДНОСТИ> вершина (я) -> информация () первый. }} Этот вопрос является частью другого вопроса я разместил здесь: стесненный (Делон) триангуляция. Поскольку это вопрос его собственного я отправил его во второй раз независимо друг от друга. прежде чем я перебирать результирующее лицо? Lateron когда петля над треугольниками мне нужно каким-то образом получить доступ к Инт-флаги, которые я определены ранее. Как это, но не на acutal очков, но «концов» сегмент, определенное ограничение края: для (CDT :: Finite_faces_iterator подходит = m_cdt.finite_faces_begin () подходит = m_cdt.finite_faces_end (); ++ подходит, ++! к) {Int J = K * 3; для (INT I = 0; я <3; я ++) {индексы [J + I] = ПРИГОДНОСТИ> вершина (я) -> информация () первый. }} Этот вопрос является частью другого вопроса я разместил здесь: стесненный (Делон) триангуляция. Поскольку это вопрос его собственного я отправил его во второй раз независимо друг от друга. finite_faces_end (); ++ подходит, ++ к) {Int J = к * 3; для (INT I = 0; я <3; я ++) {индексы [J + I] = ПРИГОДНОСТИ> вершина (я) -> информация () первый. }} Этот вопрос является частью другого вопроса я разместил здесь: стесненный (Делон) триангуляция. Поскольку это вопрос его собственного я отправил его во второй раз независимо друг от друга. finite_faces_end (); ++ подходит, ++ к) {Int J = к * 3; для (INT I = 0; я <3; я ++) {индексы [J + I] = ПРИГОДНОСТИ> вершина (я) -> информация () первый. }} Этот вопрос является частью другого вопроса я разместил здесь: стесненный (Делон) триангуляция. Поскольку это вопрос его собственного я отправил его во второй раз независимо друг от друга.
HesselKRaymond
3

голосов
3

ответ
278

Просмотры

Самопроизвольное поведение курсора данных для триангулированного 3d поверхностей в MATLAB R2011b

Я вижу странное поведение от курсора данных в MATLAB R2011b при нанесении на участки триангулированного 3d поверхностей: При нажатии на определенных точках выбирают совершенно разные точки вместо этого. Пример с цилиндром: [г, фи, ч] = meshgrid (1, 0: пи / 10: 2 * пи, 0: 0,05: 1); . Х = г * соз (фи); . У = г * Sin (фи); Z = H; хуг = [х (:) у (:) г (:)]; три = Делон (хуг); trimesh (три, хуг (:, 1), хуг (:, 2), хуг (: '', 3), ... 'LineStyle', 'ни', 'Маркер', 'MarkerSize', 30) вид (-37, 28) Затем включите режим курсора данных и попытаться выбрать самую верхнюю точку одного из столбцов в передней. На моей установке, MATLAB не выбирает точку под курсором, но другой один, казалось бы, выбранный случайным образом. Является ли это ошибка или я делаю что-то не так?
2

голосов
2

ответ
2k

Просмотры

Вычисление расстояния от точки до триангуляции в 3D с Matlab

У меня есть облако точек 3D, что я преобразованный в триангуляции Делоне с помощью функции Matlab в DelaunayTri. Теперь у меня есть контрольная точка в 3D и хочу, чтобы вычислить, в Matlab, наималейшее расстояние между этой точкой и триангуляцией. До сих пор я думал об использовании nearestNeighbor (...) функции-члена класса DelaunayTri в Matlab, чтобы найти точку в триангуляции ближайшей к моей тестовой точке, а затем вычисления расстояния между ними. То есть что-то, но это не то, что я действительно хочу. Ближайшая точка на триангуляции моей тестовой точке, в общем, а не вершина триангуляции, но где-то на грани треугольника. Как я могу найти эту точку зрения? Спасибо!!!
Patrick Bangert
2

голосов
4

ответ
1.7k

Просмотры

Как получить очки на лице, чтобы нарисовать триангуляционную

Как я могу иметь рот и глаза угловые точки и центральная точка носа с помощью OpenCV, как на этой картинке? Может кто-нибудь мне помочь?
TIBOU
2

голосов
2

ответ
2.4k

Просмотры

Делоне триангуляции - Удаление Треугольники

Я сделал триангуляционную с использованием версии Matlab 2013. Теперь я хочу, чтобы удалить некоторые из треугольников, что означает отмену их подключения, например, треугольник число 760. Как я могу применить его? когда я попытался изменить список подключений, говоря: dt.ConnectivityList (760, :) = []; Я получил сообщение: Не удается присвоить значения триангуляции. я думал о том, может справиться конкретные области с другой структурой, но: а. я не знаком со структурами, так что я не знаю, как сделать это правильно. б. после того, как я буду копировать структуру, как я могу получить мои треугольники? дт содержит 3 поля: точки, ConnectivityList и ограничений (пустое поле). Пожалуйста, помогите мне :) Большое спасибо.
user3121718
2

голосов
0

ответ
445

Просмотры

Python scipy.spatial.Delaunay, по-видимому, не установлена ​​с SciPy 0.13.3?

Я пытаюсь использовать пакет Scipy.spatial.delaunay Python для создания 3-мерного Делон сеток, за исключением того, как представляется, не будет установлено. Когда я просматриваю каталог Scipy.spatial я не вижу никакого упоминания о Делоне, ConvexHull или Вороного (только регулярные ближайшие соседи запросы расстояния, kdtree и ckdtree). Являются ли эти модули отдельно от основной установки SciPy? У меня есть самая последняя SciPy установлена ​​(ст 0.13.3) вместе с до-до настоящего времени Numpy (ст 1.8.1), работает на Python 2.6.6 на Ubuntu 10.10.
MikeFenton
5

голосов
1

ответ
1.8k

Просмотры

Как установить максимальную длину стороны треугольника в триангуляции Делоне в R?

Как удалить расстояние от триангуляции Делоне, которые больше, чем мне нужно? Пример данных: х
Ladislav Naďo
2

голосов
1

ответ
137

Просмотры

Как напечатать кромки Делона графика?

После этого: Как напечатать лицо диаграммы Вороного ?, у меня теперь есть: #include #include #include #include #include #include #include ЬурейеГо CGAL :: Exact_predicates_inexact_constructions_kernel K; ЬурейиЙ CGAL :: Segment_Delaunay_graph_traits_2 Gt; ЬурейиЙ CGAL :: Segment_Delaunay_graph_2 DT; ИНТ основные () {станд :: ifstream сослагательного наклонения ( "data.cin"); утверждают (IFS); DT VD; сайт DT :: Site_2; // читать сайты из потока и вставить их в диаграмму, а (МФС >> сайт) {vd.insert (сайт); } Ifs.close (); // проверить диаграмму Assert (vd.is_valid (правда, 1)); станд :: соиЬ
gsamaras
2

голосов
2

ответ
2k

Просмотры

Быстрый способ вычисления диаграммы Вороного зная К-ближайших соседей

Я знаю, что это относительно легко вычислить множества к-ближайших соседей от А мозаик Вороного. А как насчет обратной задачи? У меня уже есть множество к-ближайших соседей (в 3D), и я хотел бы вычислить объемы и центры ячеек Вороного. Интуитивно, должно быть О (п) алгоритм, который делает это, верно? Кто-нибудь видел что-то подобное реализовано где-нибудь? Заранее спасибо PS: Я предполагаю, что никакая клетки Вороной не имеет больше к ребрам (это предварительное знание о расположении точек, вероятно, что делает возможным вычислить диаграмму в O (N), независимо от размерности). PPS: Я также предположить, что для данной точки, вершины ячейки Вороного принадлежат множеству Knn (см комментарии ниже).
calys
2

голосов
1

ответ
305

Просмотры

генерировании ограничений краев случайным образом для генерирования ограниченной триангуляции Делона

Я реализовал подход развертки строки, используемый Domiter и Zalik для создания ограниченной триангуляции Делона для множества точек в пространстве 2D в Java. Я хочу, чтобы убедиться, что код, который я разработал действительно работает для русских случайно сгенерированных точек и к ограничению ребер между ними. Теперь, используя общую стратегию, я хотел бы выбрать случайную точку из множества п вершин, а затем выбрать вторую случайную точку и имеет ребро между ними не может работать, так что я понимаю из определения несвободной триангуляции Делона является то, что ограничительные ребра кромки плоской прямой линии графика. Таким образом, они не пересекаются. Если точки выбраны случайным образом проверка, возможно, придется быть выполнены, чтобы определить, что они не производят пересекающиеся ограничений. Такой подход не может быть эффективным на всех. Таким образом, Мне было интересно, знал ли кто-нибудь эффективной стратегии для создания ограничений в случайном порядке. Заранее спасибо.
chaitanya
2

голосов
1

ответ
3.9k

Просмотры

Filling triangles in Matplotlib triplot with individual colors

Можно ли построить список треугольников, порожденных scipy.spatial.Delaunay с использованием функции triplot pyplot таким образом, чтобы каждый треугольник может быть нарисован и заполнен с индивидуальным цветом? Основной питон скрипт который я создал импорт NumPy в н.п. импорт matplotlib.pyplot как PLT из scipy.spatial импорта Делон импорта matplotlib.image как mpimg ч = 300 ш = 1000 НЦА = 30 = PTS np.zeros ((НПЦ, 2 )) PTS [: 0] = np.random.randint (0, ш, НПЦ) PTS [: 1] = np.random.randint (0, ч, НПЦ) три = Делон (PTS) (plt.xlim 0, ш) plt.ylim (0, ч) # Определить цвет, используемый для каждого треугольника, основанного на ортоцентр # треугольника и соответствующего цвета пиксела в фоновом изображении. Центры = np.sum (PTS [tri.simplices], ось = 1, DTYPE = 'INT') / 3,0 = цвета [IMG [у, х] для х, у в центрах] # Это участки края каждого треугольника с нет заливки. Я' d любит # включать список цветов для построения заливки для каждого. plt.triplot (PTS [:, 0], Очки [:, 1], tri.simplices.copy ()) plt.show () Есть ли какой-нибудь аргумент triplot, где я могу передать список цветов, который содержит цвет для соответствующий треугольник. Я уверен, что я могу сделать каждый треугольник в цикле, используя соответствующий цвет заливки, но это хорошо, если бы был более элегантным и более быстрым способом.
sizzzzlerz
3

голосов
2

ответ
499

Просмотры

Евклидова минимального остовного дерева и триангуляции Делоне

Я хочу, чтобы вычислить минимальный остов на основе евклидова расстояния между множеством точек на 2D плоскости. Мой текущий код сохраняет все ребра, а затем выполняет алгоритм Прима, чтобы получить минимальный остов. Тем не менее, я знаю, что делать это занимает O (N ^ 2) пространство для всех ребер. После выполнения некоторых исследований, становится ясно, что память и время выполнение могут быть оптимизированы, если рассчитать триангуляции Делона первыми на этом множестве точек, то получат минимальный остов с помощью запуска алгоритма Примы или Краскали по краям триангуляции. Это является частью конкурса программирования (https://prologin.org/train/2017/qualification/taxi_des_neiges), так что я сомневаюсь, что я смогу использовать scipy.spatial. Есть ли какие-либо альтернативы просто получить края, содержащиеся в триангуляции Делоне? Заранее спасибо.
Jingjie YANG
2

голосов
1

ответ
61

Просмотры

Что входы на функции getEdges означают?

Я нашел способ сделать триангуляции Делоне, но я не совсем понимаю, что входы ИНТ [] х, ИНТ [] у, ИНТ [] г есть. импорт java.awt.Point; импорт java.util.Iterator; импорт java.util.TreeSet; общественного класса Триангуляция Делоне {INT [] [] adjMatrix; Триангуляция Делоне (размер INT) {this.adjMatrix = новый INT [размер] [размер]; } Общественного INT [] [] getAdj () {вернуть this.adjMatrix; } // п = Кол-во пунктах // adjMatrix = какой момент подключен к какому (двойной) TreeSet getEdges общественного (Int N, Int [] х, INT [] у, INT [] г) {TreeSet результата = новый TreeSet ( ); если (п == 2) {this.adjMatrix [0] [1] = 1; this.adjMatrix [1] [0] = 1; result.add (новый GraphEdge (новые GraphPoint (х [0], у [0]), новый GraphPoint (х [1], у [1]))); возвращать результат; } Для (INT I = 0; <п - 2; я ++) {для (Int J = I + 1, J <п; j ++) {для (Int к = I + 1; к <п; K ++) {если (J == к) {продолжить; } INT х = (у [J] - у [г]) * (г [к] - г [г]) - (у [к] - у [г]) * (г [J] - г [г] ); INT уп = (х [к] - х [г]) * (г [J] - г [г]) - (х [J] - х [г]) * (г [к] - г [г]) ; INT Zn = (х [J] - х [г]) * (у [к] - у [г]) - (х [к] - х [г]) * (у [J] - у [I]) ; логический флаг; если (флаг = (гп <0 1:! 0) = 0) {для (интермедиат т = 0, т <п; M ++) {флаг = (флаг) && ((х [м] - х [г]) * хп + (у [м] - у [г]) * уп + (г [м] - г [г]) * гп 0)) {Int N = pointsSet.size (); INT [] х = новый INT [п]; INT [] у = новый INT [N]; INT [] г = новый INT [п]; INT = 0; Итератор итератор = pointsSet.iterator (); в то время как (iterator.hasNext ()) {точка точка = (точка) iterator.next (); х [г] = (целое) point.getX (); у [I] = (целое) point.getY (); г [г] = (х [г] * х [г] + у [г] * у [I]); я ++; } Вернуть getEdges (п, х, у, z); } Возвращать нуль; }} г [г] = (х [г] * х [г] + у [г] * у [I]); я ++; } Вернуть getEdges (п, х, у, z); } Возвращать нуль; }} г [г] = (х [г] * х [г] + у [г] * у [I]); я ++; } Вернуть getEdges (п, х, у, z); } Возвращать нуль; }}
doominabox1

Просмотр дополнительных вопросов

Связанные вопросы