Stack Overflow
Stack Overflow

Questions tagged [delaunay]

A *Delaunay* triangulation is a triangulation such that no vertex of the triangulation is inside the interior of the circumcircle of any triangle of the triangulation.

See the Wikipedia page Delaunay triangulation.

488 questions
49
votes
3 answers

Mesh generation from points with x, y and z coordinates

Problem: Mesh generation from 3D points (with x, y and z coordinates). What I have is points in 3D space (with x, y and z coordinates) you can see it in image 1. What would be the output is image 2 or image 3, or image 4. In short it would be…
Pritesh
  • 3,208
  • 9
  • 51
  • 70
42
votes
5 answers

Efficient Delaunay triangulation

I'm looking for a .NET implementation which builds Delaunay triangulation from set of points. I have already tested couple of implementations but they all worked only for small amount of points (up to 20,000). I need something that can handle…
AlonH
  • 433
  • 1
  • 4
  • 7
32
votes
5 answers

How do I derive a Voronoi diagram given its point set and its Delaunay triangulation?

I'm working on a game where I create a random map of provinces (a la Risk or Diplomacy). To create that map, I'm first generating a series of semi-random points, then figuring the Delaunay triangulations of those points. With that done, I am now…
CommanderTso
  • 444
  • 1
  • 5
  • 11
19
votes
3 answers

Finding near neighbors

I need to find "near" neighbors among a set of points. There are 10 points in the above image. Red lines are edges from the Delaunay Triangulation, black stars mark the mid-lines of the edges, blue lines are the Voronoi tesselation. Point 1 has…
Jonas
  • 74,690
  • 10
  • 137
  • 177
19
votes
8 answers

Calculate bounding polygon of alpha shape from the Delaunay triangulation

Given a set of points in the plane, a notion of alpha-shape, for a given positive number alpha, is defined by finding the Delaunay triangulation and deleting any triangles for which at least one edge exceeds alpha in length. Here's an example using…
Zach Conn
  • 1,301
  • 2
  • 11
  • 23
19
votes
9 answers

How to find all neighbors of a given point in a delaunay triangulation using scipy.spatial.Delaunay?

I have been searching for an answer to this question but cannot find anything useful. I am working with the python scientific computing stack (scipy,numpy,matplotlib) and I have a set of 2 dimensional points, for which I compute the Delaunay…
James Porter
  • 1,853
  • 2
  • 17
  • 30
19
votes
4 answers

Python: Calculate Voronoi Tesselation from Scipy's Delaunay Triangulation in 3D

I have about 50,000 data points in 3D on which I have run scipy.spatial.Delaunay from the new scipy (I'm using 0.10) which gives me a very useful triangulation. Based on: http://en.wikipedia.org/wiki/Delaunay_triangulation (section "Relationship…
EdwardAndo
  • 333
  • 1
  • 2
  • 7
15
votes
5 answers

How can I get a dictionary of cells from this Voronoi Diagram data?

Using the voronoi/delaunay diagram generation library found in this program, which is based on Fortune's original implementation of his algorithm, with a random set of points as input data, I am able to get the following output data: A list of the…
pdusen
  • 520
  • 2
  • 7
  • 18
15
votes
2 answers

Delaunay triangulating the 2d polygon with holes

I want to triangulate the complex (but not self-intersecting) polygon with holes, so that resulting triangles all lay inside the polygon, cover that polygon completely, and obey the Delaunay triangle rules. Obviously, I could just build the Delaunay…
Rogach
  • 26,050
  • 21
  • 93
  • 172
15
votes
5 answers

How do I iterate over faces in CGAL

I am trying to use CGAL to do some Delaunay triangulation. I used one of the CGAL samples to compute a triangulation which includes a height field attribute. The problem I have having is that I have no idea how to get the resulting triangulation. …
Adam Tegen
  • 25,378
  • 33
  • 125
  • 153
14
votes
6 answers

Triangulate a set of points with a concave domain

Setup Given some set of nodes within a convex hull, assume the domain contains one or more concave areas: where blue dots are points, and the black line illustrates the domain. Assume the points are held as a 2D array points of length n, where n is…
Daniel R. Livingston
  • 1,227
  • 14
  • 36
14
votes
1 answer

Creating regular Delaunay grid in with scipy

Is there some method to get a triangulation in 2D that is more ordered like Matlab Delaunay produces? Here is an example of Matlab's 2D Delaunay triangulation. Using this code: xPoints = np.arange(0,11,1) yPoints = np.arange(0,11,1) gridPoints =…
Vance T
  • 513
  • 2
  • 5
  • 15
12
votes
1 answer

Is there C++ API for Delaunay triangulation in OpenCV?

I'm trying to implement one of active appearance models (AMM) and on one of the steps I need to get triangulated mesh of a face, e.g.: Delaunay triangulation seems to be a good fit for this task (correct me if there are better options), and OpenCV…
ffriend
  • 27,562
  • 13
  • 91
  • 132
11
votes
1 answer

Getting a vertex_handle from an edge_iterator

I'm having quite some difficulty getting a vertex_handle for each of the end points of an edge in a Delaunay triangulation. Since I hammered my head against this for several hours I thought maybe one of you guys could help me out with this…
cdecker
  • 4,515
  • 8
  • 46
  • 75
11
votes
2 answers

Bowyer-Watson algorithm: how to fill "holes" left by removing triangles with super triangle vertices

I am implementing the Bowyer-Watson algorithm as presented at Wikipedia. In my implementation, everything works as I would expect up until the last part of the pseudocode: for each triangle in triangulation // done inserting points, now clean up …
sadakatsu
  • 1,255
  • 18
  • 36
1
2 3
…
32 33