On 23/01/2018 at 14:05, xxxxxxxx wrote:
Hi Frank, thanks for writing us and above all sorry for coming late here.
With regard to your question the methods pointed out in the post you're referring to, are actually only paving the first part of the road to get the external (outer) edges of a n-gon.
A short recap, for those not familiar with n-gons, on the terminology i'm going to use down below:
- n-gon: a face made of more than 4 edges and made up of at least two polygons sharing an internal edge (like the object on the left made up of poly 0,1,2,3,4,5);
- polygon: a face made of 3 or 4 edges (like poly 6 and 7 on the object on the right);
- face: a polygon or a n-gon;
- external edge: an edge which define the outer or inner boundary of a face and represented when Wireframe Display mode is active (all green numbers marked with a orange circle);
- internal edge: an edge which is shared across the polygons building up a n-gon (all the remaining green numbers)
- vertex/point: the start or end point of an edge (marked in red numbers).
It's also worthy to note that only n-gon can contain holes and can be concave (tracing a generic segment in the ngon might end in intersecting the ngon external outer/inner edges multple time) whilst a simple polygon cannot have holes and can be only convex (tracing a generic segment in the polygon will never end in intersecting the polygon external outer edges). For the sake of completeness, PolygonObjects which are made of multiple polygons or ngons can instead create holes and be concave as well.
My solution to find the outer edge is conceptually simple:
- identify edges which are external (inner or outer doesn't matter);
- in case the PolygonObject is made by multiple polygons or ngons, identify those edges already marked external at point 1 which are shared across two faces (like edge marked in purple) and mark them as internal;
- walk across the list of the external edges and create an ordered lists of edges which are:
* external; * are connected in CW or CCW order;
- split the list in multiple lists to create the different islands;
- compute the area of each island (projected on a 2D-plane) and identify the biggest one which represent the island of the outer edges.
The PolygonObject.GetNgonEdgesCompact() is helpful to mark which edges are internal or external in a PolygonObject made by just one n-gon.
At the same time Neighbor.GetNeighbor() is helpful to distinguish those external edges which are mutually used by a polygon and a n-gon (or two n-gons or two polygons) from those actually representing the real "external" boundary or a PolygonObject (like those in purple in the image above).
So far i don't think that either PolygonObject.GetPolygonTranslationMap() or PolygonObject.GetNGonTranslationMap() are needed, but maybe approaching the problem from a different perspective could be helpful as well.
Hope these few lines could help.