Nesting: Optimal results buried in list, results not properly sorted by "not placed objects"

[mahe]

Hello,

I have a problem, or a nuissance, with QCAD and nesting, and since it is Sunday and I got a bit of time, I thought I'd ask:

So QCAD 3.32.6, Linux, the problem is present for a couple of years already.

I am regulary nesting shapes with QCAD before I cut them on the machine. I stay within QCAD, the machine's software can read DXF. I convert the shapes into polylines and then nest them.

The attached files are showing a typical job for me, on the smaller side for my work, but a good example.

I first "nest" the shapes into a rectangular box to check if all shapes are closed, sometimes the data is not accurately closed, then I have to manually correct. But this is step is already finished in the attached file and not shown. The shapes/polylines to be cut are in the layer "SCHNITT", the rectangular box for the first sort is the on the layer "RAHMEN__SORTIERUNG". This is my preparation.

Then I nest for the cutting/production all shapes from the layer "SCHNITT" again to the sheets on layers "RAHMEN__WJ__1", "RAHMEN__WJ__2", and "RAHMEN__WJ__3". Which are the sheets of material to be cut on the machine.

And the results of the nesting with QCAD are good, just the ordering of the results as displayed on screen is broken. None of the real optimal results are shown first in the list. On this job there are just a couple of wrong results, but on other jobs I get pages over pages of wrong optimal results shown before there is any real result.

So what am I doing wrong ? Am I seeing a bug ? Or is this a problem that I am causing myself ? How can I have the sorting so that results with 0 of not placed objects are always shown first ?

It is a nuissance for me, because usually the nesting takes quite a bit of time, especially on bigger jobs, and then I just stop by the computer every once in a while and I would like to be able to see at first glance if a real result has been found and not having to scroll through pages of false optimal results that are no results at all ? The false results are especially often shown if the nesting is a tight fit for the sheets of material on the machine.

Thanks
Kind regards

[CVH]

Hi,
I can not replicate your problem with a quick attempt using QCAD/CAM trial 32.3 on a Windows platform.
By default a near optimal solution so far is listed at the top.
That is a bit standard since 3.29.4 what includes alternative sorting.


'Near optimal' depend on what is considered by that.
Sometimes the second or the third best is somewhat smaller in overall occupied space.
But that are fractions.


Another problem persists.
Selecting 324 (logically closed) polylines ... Only 276 are added from the selection ...
... And still my NFPs count is much higher ... And never twice the same.
Here is an older topic on the matter ... Before the 3.29.4 release.

Eventually only 10 are nested what is a QCAD/CAM trial limitation.


I see many identical shapes ... What about the use of nesting quantity?
You also allow only 2 rotations.
I am pretty sure that I can manually nest the L-shapes far more compact.


Regards,
CVH

[mahe]

Hi CVH,

thank you for your reply
Yes the older topic that you found seems quite similar, yet I cannot see what I can apply from that other topic to this problem. My shapes are nicely closed, and the align and hull options are not present in the current QCAD version anymore.

In the end the sorting of the results in the list is just wrong. In the example I gave the "not a solution" placed at the list top cannot place 5 shapes and has a much larger area. That is not a solution at all, and it should simply not be shown.

And I am aware that with more rotations the result can be better, however it also takes longer. With that many parts only allowing two rotations sometimes gives better results. I often take straight parts or near straight parts and nest them with only two rotations and then nest the rest with four rotations. And the example file is a small file for me, I often have much bigger files with many more shapes.

You wrote "Selecting 324 (logically closed) polylines ... Only 276 are added from the selection".
I am aware of this type of message, I frankly do not understand this type of message, and thus I ignored that class of messages so far. The end result that I get from nesting with QCAD is correct in general; in the end all parts are nested and cut and when I place the cut parts after the cutting then none is missing. With this example that I attached the message that I get is:
Teile aus der Auswahl hinzufügen...
0 duplicate parts found
276 parts found
And yet in the end all 324 shapes are correctly nested. So yes, confusing message, but can be ignored, since QCAD works. Why QCAD reports 276 parts found, when there are 324 shapes, that I do not know or understand.

I have no control over the parts that I want to nest, these are output from another program. I am aware that many shapes are duplicates. And QCAD is not detecting the duplicates either, there is that message about "duplicate parts found" , but QCAD never find any duplicate parts. But because of the large number of parts I never count them, and I do not get them in an ordered manner as output from the other program either. The other program that is generating the parts is not nesting the shapes at all. So that is what I am using QCAD for.

In the end my questions is: Is this a something that I am causing somehow with bad program usage, or is this a bug that I should report, is this a behaviour of QCAD that is correct and that I just do not understand ?

Thanks
Kind regards

[CVH]

An attempt with 135 selected to 1 sheet reported 96 found ... = -39 pieces
324 vs 276 found ... = -48 pieces
There seems to be no logic but after some investigations ...

You have parts that are drawn inside each other.
There are 2 approaches for that.
Or one considers this as 4 parts each ...
Or as 1 part with holes and islands in holes .. holes on islands .. and so on, like QCAD/CAM does.

In you example 64 are such shapes in 16 groups ... 64 - 16 = 48 are locked in place with the 16 outer shapes.
324 - 48 = 276
Probably one mystery solved.


The NFP (No-Fit Polygon) of an identical to X vs an identical to Y remains the same as for an NFP of X vs Y.
If you rotate one of the shapes only by a bit then the NFP is different.
It would need less calculation time for all NFPs of 36 shapes 12x X,12x Y and 12x Z ... If we process 12x (X, Y, Z)

Logically speaking it is a permutations problem or rather reduced to a combinations problem.
In both cases I expect a logical steady number of NFPs for the same selection of shapes.


Back to the topic 'Optimal results buried in list':
In the Changelog 3.29.4 (2024/02/07) is stated:

• Improve nesting dialog with additional columns alternative sorting

And that works just fine for me (3.32.3 trial).
There are indeed additional columns but I see no method to sort differently than by default.

That 'default' is not the most ideal at the top on your system is beyond me.
Perhaps a bug report is in order.

Regards,
CVH

[mahe]

Hi CVH,

thank you for the explanation, this shapes nested inside each other indeed makes sense as a reason for the numbers that are shown.

As I said, I get the dxf files that I nest as the output from another program, and even if there are parts that are duplicates of each other, I do not get that information. And sorting a couple hundred pieces to find the duplicates is beyond me, even if I'd love to reduce the complexity of the problem space to reduce computational time needed to get faster nesting.

So I'll gather a couple more files from the past where this sorting problem happens and then I'll file a bug report. Maybe with a good bug report I'll also get duplicate detection, that would really help.

Thank you
Kind regards

[CVH]

Maybe with a good bug report I'll also get duplicate detection

Would be very beneficial but that might probably need a re-code.
It may downsize the permutation/combination array drastically.

An exact duplicate would be Congruent without Reflection or a pure Translation/Rotation.
An semi exact duplicate with islands and holes would have a duplicate as most outer contour.
First tests would exclude an unequal 'enclosed surface', but an equal surface is in itself not conclusive.
And/or an equal contour length.

And then there is the capability to place things in holes.

Regards,
CVH