True Shape Nesting 04: going for Intf intersection

We talked about polygon intersection algorithm in the Lesson 14 of our video tutorials. It also took quite a while to bring the Intf algorithm to Mobius, as the algorithm appeared to be badly coupled with whatever guts of the library you'd never want to touch. The reason this algorithm caught my attention is because it was used in one commercial mesher for intersecting triangle links with polylines, and that is how I know it's good enough. Since then, it has never proved to be a bad choice, so let's start with this one and see how far we can get.

To intersect two polygons named a and b, the following command is to be given in the console of Mobius:

intf a b

The Intf algorithm is conceptually simple. It iterates the segments of each polygon in a nested loop and checks whether two straight segments intersect or not. So far, the algorithm looks promising, and the performance demonstrated on a simple case is more than satisfactory. The question is whether the Intf algorithm can handle more realistic cases without any significant degradation in timing. After all, it clearly has quadratic complexity, even though most of the non-tentative segments are filtered out thanks to the early bbox collision check.

What would we need to heavy-test the Intf algorithm? Apparently, some more realistic polygons have to be loaded in. Ideally, we should enable something like DXF import, but such a function is not available neither in Mobius nor in Analysis Situs (open source). Developing such a function would take us too far from the main subject of nesting, so I would go for a somewhat simpler solution. Why not to read a polyline definition from a simple text file, which is, in its turn, produced by polygonizing of a whichever two-dimensional contour in Analysis Situs (#326)?

To import a polygon from file in Mobius, the following command can be used:

import-polygon <filename> <name>

Some examples of serialized contours can be found here: www.gitlab.com/ssv/AnalysisSitus/-/tree/master/data/cad/contours

Want to discuss this? Jump in to our forum.