Minimum Quadrilaterlization of Polygons - existing algorithms?
I'm currently trying to find a way to take irregularly shaped polygons and divide them into as few quadrilaterals as possible.
I can't find an obvious out of the box algorithm anywhere that does this, so I'm thinking of going down two possible routes.
1.Getting the optimal triangulation first, and then converting these to quadrilaterals
2.Trying to alter the CGAL optimal_convex_partitions function from their 2d polygon partitioning package to create quadrilateral partitions https://doc.cgal.org/latest/Partition_2/group__PkgPolygonPartitioning2.html#ga3ca9fb1f363f9f792bfbbeca65ad5cc5
I'm a total beginner to computational geometry, so I'd just like to know if either of these approaches seems like a fools errand before I try to learn C++? If anyone knows anything about the best possible approach to this that'd be even better. Thanks!
(Edit) Including a sample polygon - None of them should have holes, though they may have complex exteriors and concavity.
I assume that if you start with triangles and then try to merge two adjacent triangles into one quadrilateral in a greedy fashion you may end up with many isolated triangles.
Not sure how the convex partition may come handy.
You may find useful information in the articles below. As far as know, finite element analysis requires that the input object comprise of triangles or quads, so there has been some research done in this direction. Here are two papers that might be relevant:
Ted D. Blacker amd Michael B. Stephenson, “Paving: a new approach to automated quadrilateral mesh generation” Int. J. Num.Meth.Engg, Vol 32, 811-847 (1991)
Jinwoo Choi and Yohngjo Kim , Development of a New Algorithm for Automatic Generation of a Quadrilateral Mesh, International Journal of CAD/CAM Vol. 10, No. 2, pp. 00~00 (2011
I'm far from being an expert on this subjest, but I'm certain that these alg. can be implemented using CGAL...
- How to Expand a Polygon Until One of the Borders Reaches a Point
- Compute the area of intersection between a circle and a triangle?
- Behavioral difference between constructing a `Nef_polyhedron_3` directly from OFF file and constructing from a `Polyhedron_3` built from the same file
- Catmull-Rom interpolation on SVG Paths
- Intersection between AABB and a capsule (swept sphere)
- Compute minimum area convex k-gon in 2d
- Difference between algorithm solution and MATLAB CVX solution in Graphical LASSO?
- k-way triangle set intersection and triangulation
- How to find the intersection point of a 3D curve and a 3D surface?
- Extending a line segment to fit into a bounding box
- Find visibility polyhedron given a point inside it
- While finding count of points inside some shape using KD-Tree, do we need to check areas intersection, or just compare depth-appropriate properties?
- Check if a 3D point lies inside a 3D platonic solid?
- How to check a point is inside an ellipsoid with orientation?
- In solidworks, is there a way to get the direction cosines of a surface normal?
- How to find overlapping area of convex coplanar polygons in 3D?
- Compensate IMU pan/tilt
- derive (approximate) rotation transform matrix (numpy) on a unit sphere given a mapping of vectors (n=12)
- Find two furthest points in a point set in linear time (2-approximation algorithm)
- Difference between quadtree and kd-tree
- How do I compute, in O(n) time, a convex hull of a set of points which are sorted by x-coordinate?
- Check if a point projected on a line segment is not outside it
- Segment Intersection
- How to convert spherical geometry to ellipsoid geometry c++ vertex generation
- Closest edge to a rectangle in a plane of rectangles
- What is most efficient way to find the intersection of a line and a circle in python?
- Initializing Half-edge data structure from vertices
- How to draw a circle in GNU Octave
- Calculate the outline of an abstract shape with holes
- What is the algorithm for finding the center of a circle from three points?