Is there an algorithm similar to the Delaunay triangulation which can organize a set of points into a set of four sided polygons instead of triangles?
Delaunay-like algorithm to get four sided polygons instead of triangles?
5
$\begingroup$
computational-geometry
-
2There are a number of algorithms for *quadrilateral mesh generation*. See [this](http://dx.doi.org/10.1002/nme.1620320410) and [this](http://dx.doi.org/10.1002/cnm.1640090205) and [this](http://dx.doi.org/10.1002/1097-0207(20001210)49:10<1327::AID-NME996>3.0.CO;2-L) for instance. – 2011-09-02
-
0Thanks J-M that is a lot to read ! Is there any specific techniques which you can think of given a set of points in a 2D space? – 2011-09-02
-
0I've read those, but I haven't experimented on them. You will have to experiment for yourself. – 2011-09-02
1 Answers
1
I don't know of any quadrangulation having similar properties to a Delaunay triangulation, but you can always convert a triangulation to a quadrangulation by adding additional points, called Steiner points. See the first section of http://www.cs.mcgill.ca/~cs507/projects/1998/rachelp/ for instance.