Get outer edges of each Ngon

Helper

On 18/01/2018 at 03:18, xxxxxxxx wrote:

Hello,

I need to get the outer edges of each Ngon in a PolygonObject. The code in this thread (https://developers.maxon.net/forum/topic/156/13225_get-all-ngons-solved&PID=52316) does not seem to do the trick, as it gives me all outer edges of all Ngons, so I don't know which edge belongs to which Ngon.

I see in the SDK docs that since R19 we have PolygonObject::GetNGonTranslationMap() in Python:
https://developers.maxon.net/docs/Cinema4DPythonSDK/html/modules/c4d/C4DAtom/GeListNode/BaseList2D/BaseObject/PointObject/PolygonObject/index.html?highlight=polygonobject#PolygonObject.GetNGonTranslationMap

Based on the information in the docs, I wrote this little script, to see what the function can do:

import c4d

def main() :
** polyMap = op.GetPolygonTranslationMap()**
** nGonMap = op.GetNGonTranslationMap(len(polyMap), polyMap)**
** print(nGonMap)**

if __name__=='__main__':
** main()**

Why does it give me this error?
_ TypeError: PolygonObject.GetNGonTranslationMap expected int or long, not list_

It clearly says in the docs:

polymap (list of int) – The polygon map. Pass the list returned by GetPolygonTranslationMap(), or a similarly formatted array.

How can I use GetNGonTranslationMap() ?

Thanks for any help!

Cheers,
Frank

Helper

On 19/01/2018 at 04:31, xxxxxxxx wrote:

The documentation is not entirely clear on this (perhaps this could be improved by giving a quick example), but what you are supposed to do is this:

  
ngonCount, polyTrans = polyObj.GetPolygonTranslationMap()   
ngonTrans = polyObj.GetNGonTranslationMap(ngonCount, polyTrans)

There is one more thing I noticed. The documentation states that GetNGonTranslationMap() returns a list of lists of int - one list of ints per N-Gon. There that says this:

The number of polygons in N-gon i is stored in list _[0]. Then the polygon indices are stored in list _[j] where j goes from 1 to list _[0].

However, this appears to only hold true in the C++ API (where these lists are C-Arrays). In Python these lists hold their size anyways and it doesn't make sense to store them explicitly as the first list item. That also doesn't appear to be what is happening. In the examples I tried it with, if an N-Gon contained three polygons, the list also only had three entries with the polygon indices. Therefore this documentation note seems to be misleading.

Timm

Helper

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.

![]([URL-REMOVED]
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.

Best, Riccardo

[URL-REMOVED] @maxon: This section contained a non-resolving link which has been removed.

Helper

On 30/01/2018 at 02:18, xxxxxxxx wrote:

Hi Riccardo,

thank for all the information, you've put a lot of work into this!

We have now developed an algorithm that gives a a list with all vertex loop for any face of the geometry. Now I can do everything I need

Thanks!

Cheers,
Frank