Questions tagged [triangulation]
The triangulation tag has no usage guidance.
14
questions
1
vote
1
answer
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 ...
- 331
1
vote
0
answers
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:
...
- 331
1
vote
1
answer
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\|$$...
- 331
0
votes
1
answer
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 ...
- 331
1
vote
0
answers
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 ...
- 331
3
votes
2
answers
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 ...
- 331
3
votes
2
answers
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 ...
- 331
0
votes
0
answers
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
1
answer
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.
...
- 119
0
votes
2
answers
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
1
vote
0
answers
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 &...
2
votes
1
answer
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 ...
user16034
3
votes
0
answers
348
views
Prove that the set of edges of a Delaunay triangulation of $P$ contains an EMST (Euclidean minimum spanning tree) for $P$
I was studying computational geometry on my own from "Computational Geometry: Algorithms and Applications" - by Mark de Berg. In chapter 9, i.e. Delaunay Triangulation, there is an exercise ...
3
votes
1
answer
208
views
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 ...
- 41