Menu
I have a set of vertices(called A) and I want to find all the border vertices such that this border vertices set is an outline of the shape.
Many of the vertices in A are redundant because they are inside the shape, I want to get rid of these vertices.
My question is similar to Best Algorithm to find the edges (polygon) of vertices but i need it to work for a non-convex polygon case.
EDIT: Clarification: The below image is a concave polygon. This is what i meant by non-convex. If I run a convex hull algorithm on it, it would not preserve the concave part of the polygon.(unless i'm mistaken).
I have a set of vertices inside and on the border of the polygon: [[x1,y1], [x2,y2]...] I want to reduce the set so that the vertices are just the border outline of the shape.
385
A polygon is convex if all the interior angles are less than 180 degrees. If one or more of the interior angles is more than 180 degrees the polygon is non-convex (or concave). All triangles are convex It is not possible to draw a non-convex triangle.
A polygon, with at least one interior angle, is greater than 180° is called a non-convex polygon or concave polygon. Sum of all the interior angles of a polygon of n sides = (n – 2)180°. The diagonals of the convex polygon lie completely inside the polygon.
A convex polygon is a polygon with all its interior angles less than 180°. The vertices of a convex polygon will always point outwards i.e. away from the interior of the shape.
This seems to be a hot topic.. https://gis.stackexchange.com/questions/1200/concave-hull-definition-algorithms-and-practical-solutions
This paper seems to be the best. Duckham, M., Kulik, L., Worboys, M.F., Galton, A. (2008) Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition v41, 3224-3236
97
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
