3
votes
Convex Polygon Triangulation: Line Intersects at most $O(\log n)$ Triangles
Let the polygon be defined by the vertices in clockwise order: $(v_1, \dotsc, v_n)$. For simplicity, assume that $n$ is even.
Add the lines: $(v_1,v_3)$, $(v_3,v_5)$,...,$(v_{n-2},v_1)$.
Then, ...
- 5,827
3
votes
Accepted
Efficiently finding point triangle inclusion when doing incremental delaunay triangulation?
These parts of the algorithm are discussed in the book Computational Geometry by de Berg et al. I will provide a summary here. Let $P$ be the set of input points.
Make 3 points that are large enough ...
- 7,768
2
votes
Fast measurement of distance from point to mid segment?
If you use an under-/overflow-safe euclidean norm implementation along the lines of LAPACK's dnrm2, your line-to-point distance function will look something like the following Scala code:
...
- 632
1
vote
Accepted
How to avoid global delaunay check in conforming triangulation?
I figured it out. The implementation of lawson's algorithm I had was incorrect, this is the right one:
...
- 331
1
vote
Constrained Delaunay triangulation algorithm?
Page 7 of "FAST ALGORITHM FOR GENERATING CONSTRAINED DELAUNAY TRIANGULATIONS" (a publication on a CDT algorithm) explains the process very clearly and the figures are extremely useful.
- 331
1
vote
Accepted
Constrained Delaunay triangulation algorithm?
You can find Johnathan Shewchuck's UC Berkely website here, which contains:
Excellent lecture notes on Delaunay Mesh Generation
sample chapters from the book "Delaunay Mesh Generation" (...
- 632
1
vote
Inflate a polyline so that the 2D band can be triangulated without self-intersections
I think your "inflated polyline" can be correctly defined as a union of "inflated line segments". Each such "inflated line segment" will be a rectangle with half-disks on ...
- 3,048
1
vote
Accepted
Delaunay triangulation from an EMST
The Wikipedia article states, that:
the Delaunay triangulation can be constructed from the Euclidean minimum spanning tree in the near-linear time bound $O(n\log ^{*}n)$, where $\log ^{*}$ denotes ...
- 3,048
Only top scored, non community-wiki answers of a minimum length are eligible