# Questions tagged [triangulation]

The tag has no usage guidance.

14 questions
Filter by
Sorted by
Tagged with
1 vote
14 views

### How to avoid global delaunay check in conforming triangulation?

I implemented a conforming (i.e. it creates Steiner points using Ruppert's algorithm) delaunay triangulator, which is working, but there is one step I am doing that I straight up don't understand and ...
1 vote
26 views

### How to actually implement ruppert's algorithm?

I have been scouting the internet for resource son how to properly implement Ruppert's algorithm and what I ahve found is always lacking in details. The best resources I have so far are these 2: ...
1 vote
38 views

### Fast measurement of distance from point to mid segment?

Say you have a segment defined by 2 points $a,b$ and a third point $p$. You want to know the distance from $p$ to the midpoint of the edge. This is very straightforward: $$d = \|\frac{a + b}{2} - p\|$$...
24 views

### How to enforce convexity of triangulation output?

I implemented an incremental Delaunay triangulation algorithm. It basically works except it has this weird issue. The algorithm starts by creating a bounding triangle that it then splits recursively ...
1 vote
39 views

### Algorithm for Steiner points?

I am trying to find resources that explain an easy to implement (not necessarily optimal but reasonable runtime) algorithm for inserting Steiner points in a triangulation. There seems to be little ...
80 views

### Constrained Delaunay triangulation algorithm?

I am trying to find a resource which explains how to compute the constrained Delaunay triangulation of a set of points and edge constraints, I found these slides by Jonathan Shewchuck, but without the ...
64 views

### Efficiently finding point triangle inclusion when doing incremental delaunay triangulation?

I want to implement a delaunay triangulator by using incremental building, which is purported to be $O(n \log(n))$ I am a little puzzled about 2 things. Ever resource I read on the matter says: Make ...
23 views

### Are there any retopology algorithms that prioritise low file size and aesthetics, specifically for B-rep to quad/tri mesh?

So I have reserched lots into GMSH - Quasi structured quads, whitch seems to use several passses to align the mesh with the cross field and its singularities (where verticies should be surrounded by 5 ...
1 vote
198 views

### Inflate a polyline so that the 2D band can be triangulated without self-intersections

Introduction I have simple polylines as sequences of points. I need a triangulation with a configurable width. The goal is to get a 2D 'band' from the input polyline without self-intersections. ...
110 views

### Convex polygon triangulation with stabbing number O(log n)

The stabbing number of a triangulated simple polygon P is the maximum number of diagonals intersected by any line segment interior to P. Give an algorithm that computes a convex polygon triangulation ...
1 vote
30 views

### Computing the unique triangles and edges from vertex connectivity of a Delaunay triangulation

I am currently studying triangular mesh generation in 2D and, in that connection, the Delaunay triangulation of a list of vertices $\{ v_1, v_2, ..., v_N \}$. The divide and conquer algorithm of Lee &...
61 views

### Delaunay triangulation from an EMST

Assume you know the Euclidean Minimum Spanning Tree of a set of $n$ 2D points (in general position). Is there an efficient way (faster than $O(n \log n)$ operations) to obtain the Delaunay ... ### Convex Polygon Triangulation: Line Intersects at most $O(\log n)$ Triangles
Suppose a convex polygon $P$ in plane is given. We want to triangulate it such that any arbitrary line $L$ intersects with $O(\log n)$ triangles. I divide $P$ in half using a diagonal line. Then I ...