Polygon andb triangle tessellation7/24/2023 If you wanted slightly irregular-looking polygons you could randomize the locations of the grid points. if all 4 points are in the polygon, make a quad, if 3 are in make a triangle, 2 are in make a rectangle, etc. Then you just do something similar to marching cubes. Another way to pose this problem is treating the 2d polygon like a function, and overlaying a grid of points. If you had a polygon-line intersection, the implementation would be simple. ![]() The algorithm I was thinking of was basically splitting polygons with lines, where the lines are a grid, so you mostly get quads. In any case, to directly answer your question, I don't know of any simple library that does what you're looking for. Turns out it's quite different, and not what I meant at all. Okay, I made a bad assumption - I assumed that marching squares would be more similar to marching cubes. If you're trying to cut a polygon into little pieces, you could implement some kind of marching squares. cv::distTransform is still maintained but operates on pixels and generates pixel output, not vertices and edge polygon data structures, but may be sufficient for my needs if not yours.Ī bit more detail on your desired input and output might be helpful.įor example, if you're just trying to get the polygons into triangles, a triangle fan would probably work. It looks like OpenCV used to support do something along these lines, but it has been deprecated (but the c-api still works?). The other package that looks to be a lot better than a random academic homepage orphan project is. Voro++ is 3D oriented but it is suggested elsewhere that approximately 2d structure will work, but be much slower than software oriented towards 2D voronoi. The next step is creating the voronoi polygons. All the sharp triangle points become blunted: The voronoi edges are the dotted lines in this picture, and are sort of the complement of the delaunay triangulation. So the first thing is to be able to generate those cell center points- generating them over the bounding box of the source polygon and a interior/exterior test shouldn't be too hard. The original polygon will get a scattering of semi random points that will be the centers of the voronoi cells, the more evenly distributed they are the more regularly sized the cells will be, but they shouldn't be in a perfect grid otherwise the interior polygons will all look the same. I've just begun looking into this same problem and I'm considering voronoi tessellation. It might not be the simplest to install but you get the most used and robust computational geometry library there is out there, and the cgal mailing list is very helpful to answer questions. ![]() To install cgal, if you are on windows you can use the installer to get the precompiled library, and there are installations guides for every platform on this page. ![]() at this point partition_polys contains the partition of the input polygons Typedef CGAL::Random_points_in_square_2 Point_generator ĬGAL::random_polygon_2(50, std::back_inserter(polygon),ĬGAL::y_monotone_partition_2(polygon.vertices_begin(), In terms of ease of use this is a small example code generating a random polygon and partitioning it (based on this manual example): typedef CGAL::Exact_predicates_inexact_constructions_kernel K For example you could generate y-monotone partition of a polygon (works for non-convex polygons, as well) and you would get something like this: The best would be probably to use the 2D Polygon Partitioning package.
0 Comments
Leave a Reply. |