Finish the Polygon class: simplify, triangulate

[IlliaHryshchuk]

• Implement next methods: simplify, triangulate
• Implement openMP parallelism, if it can provide acceleration
• Write unit tests

[VladGribinchuk]

Before you may ask about simplification approach, I will outline the main idea. The goal of this method is to remove unnecessary consecutive small segments by replacing those just with one straight line. Which segments should be considered as unnecessary is defined by smallestLineLength parameter. It defines the new smallest line segment length in the polygon, thus any old segments which are smaller than smallestLineLength are considered as unnecessary.

If you take a look at the 1st image, original ABCDE can be simplified to ACE with some smallestLineLength value. New AC and CE segments should be not less than smallestLineLength. If smallestLineLength value is a bit larger, then original ABCDE will be simplified to just AE.

Besides this main approach, please add some protection mechanism of losing geometry. For example, add extra boolean parameter smth like saveSharpCorners. If saveSharpCorners is enabled, and if algorithm considers two line segments to simplify, but those are shaping a sharp angle, then this simplification is not allowed, and algorithm will left those segments in original polygon. Simplifiacation will be allowed only for angles >90 (please see 2nd image). Please see also 3rd image for some real case. Imagine AB, BC, CD are all smaller than smallestLineLength. Simlification AC is allowed, because ABC angle is obtuse. But further simplification AD is not allwed, because ACD angle is acute. Thus algorithm will do only AC simplification even though AC length is less than smallestLineLength. Above mentioned protection mechanism is just some my raw ideas. Haven't really thought about details. We will see how it works only after implementation :) Sure, if you have other ideas, you are welcome.

[IlliaHryshchuk]

The main idea is clear, but i hardly imagine how to do it with facets yet.

It means that we have to work with points/lines, and we mustn't take into account the belonging a point to facet? After deleting unnecessary points the .stl file will be not completed, so, in this case, we have to to rebuild new facets.

Or we just have to delete unnecessary whole facets (like in my screenshot)?

[VladGribinchuk]

@IlliaHryshchuk Ok, let me clarify: Polygon, in our case, is a set of points, that encloses an area in a 2D plane. It doesn't have any relation to mesh facets in a 3D space. Polygon simplifying doesn't mean deleting unnecessary points in the .stl or rebuilding the 3D mesh topology. Simplifying is just a process of removing unnecessary points from the one particular polygon, and that's all) So, you dont have to imagine how to do it with facets, because it is completelly different thing. Let me please know if you have questions.

[VladGribinchuk]

Maybe images in my previous comment were somewhat confusing.. particulary, 1st one(or 3rd). But consider those line segments, AB, BC, CD, etc. as a parts of one 2D polygon.

[IlliaHryshchuk]

@VladGribinchuk, oh, i have understood. Thanks for clarifying

[okrdima]

@VladGribinchuk for the method of triangulate I need to implement the Delaunay algorithm?

[VladGribinchuk]

@VladGribinchuk for the method of triangulate I need to implement the Delaunay algorithm?

It would be cool if you could 😎 But you can start for now with simpliest algorithm which will work only for convex polygons. That will be enough for our needs for now. Just connect vertices of polygon to split it on set of triangles.

[okrdima]

@VladGribinchuk I have one interesting question. Is polugon with vertex ABCDE. For the isConvexHul method is important that the vertices are clockwise.If the points are chaotic then the method returns false. Is it also important for my method of triangulation that the points are clockwise? Can the points be chaotic, then sort them and then do the triangulation? For example, there should be a polygon ABCDE or chaotic BACED

[VladGribinchuk]

Only one important thing for the isConvexHull() method is whether points are shaping convex outline. isConvexHull() works with both orientations - clockwise (cw) or counter clockwise (ccw).

Answering your question - triangulate() should work disregarding to polygon orientation, whether it is ccw or cw. But important prerequisite - polygon should be convex, because simple triangulation approach won't work for concave. So, just return empty triangle array for non-convex polygon. About orientation of resulting triangles - they should have the same orientation as the polygon. For example, if polygon is ccw, then resulting triangles should be ccw also, and vice versa.

P.S. btw, in your example, "chaotic" BACED polygon should be like this:

UPD: also remember important condition - counter clockwise(ccw) orientation means the polygon is some external contour (outline), while clockwise (cw) means that polygon is a hole. This is the basic rule acceptable for many graphics libraries. We follow the same rule.