An error occurred when I ran the 'PolygonBoolean Operations DX11' sample program

[bazhi-star]

hi， I tried adjusting the value of mEpsilon to 1e-20. The error occurred when ConstructInvertedEll() and ConstructPentagon() were performing an operation with mXor=P ^ Q; error：mathematics\bsppolygon2.h(gte::BSPPolygon2::InsertEdge,104): Degenerate edges not allowed.

sample program：Geometrics->DX11->PolygonBooleanOperationsDX11

[owai1980]

Hello,

Maybe I'm wrong but your epsilon value is way too small of you use float or double.

It is as if you refuse any error tolerance, but... You should accept some 🙂

David will probably explain better than me...

Johan

Le mer. 27 sept. 2023 à 05:53, bazhi-star @.***> a écrit :

hi， I tried adjusting the value of mEpsilon to 1e-20. The error occurred when ConstructInvertedEll() and ConstructPentagon() were performing an operation with mXor=P ^ Q; error：mathematics\bsppolygon2.h(gte::BSPPolygon2::InsertEdge,104): Degenerate edges not allowed.

sample program：Geometrics->DX11->PolygonBooleanOperationsDX11

— Reply to this email directly, view it on GitHub https://github.com/davideberly/GeometricTools/issues/75, or unsubscribe https://github.com/notifications/unsubscribe-auth/AG3BAQOR3XGLMAHSZNII2J3X4OPLPANCNFSM6AAAAAA5IV2XD4 . You are receiving this because you are subscribed to this thread.Message ID: @.***>

[bazhi-star]

Okay, thank you for your reply. wish you every success

[davideberly]

I do not prefer to speculate about why the error has occurred. I am re-opening the issue so that I can investigate.

The BSPPolygon2 code uses a BSP tree. I never liked that code because for large datasets, the number of vertices and edges from splitting is too large. One of my long-term goals is to use a sweep algorithm, but that is a large project. It would occur only in GTL. (I need to re-post at my website a PDF on "polysolids", which discusses Boolean operations that can be implemented in 2D and in 3D.)

[davideberly]

The problem occurs because of floating-point rounding errors in the computations. I have modified the sample code (PolygonBooleanOperationsWindow2.{h,cpp}) to allow rational arithmetic. The default now for executing the sample is to use rational arithmetic. I have added some comments to the header file that indicate the problem. I also mention that if you apply a large set of Boolean operations to the input polygons, the number of bits required for rational arithmetic can become so large that the program will not terminate in a reasonable amount of time. In particular, any time a split occurs, the intersection point of two line segments needs more bits than the line segment endpoints.

I do not know how large your datasets are, so you can try rational arithmetic. If too slow, I actually have rational wrappers similar to BSNumber and BSRational that uses the GNU multiple precision library (GMP). It is probably time for me to polish the classes and post the code.

That said, be aware that my code uses the Boost License. GMP uses the dual licenses GNU LGPL v3 and GNU GPL v2. I am not a lawyer, so I do not know how the two licenses can co-exist. I certainly do not want to use the LGPL or GPL licenses. When I post the rational wrappers for GMP, it will be as a separate project with several header files that contain the proper LGPL/GPT license verbage. I will not modify any of my files to use GMP; users will have to do that themselves (that is, the users now have to become lawyers...).

I have a LONG TERM TODO to implement my own optimized rational library (which is needed for rational multiplication), but no idea yet as to when that will happen.

[davideberly]

Closing inactive resolved issue.