Offsetting can sometimes be quite slow.
Polygon and line clipping and offsetting library (C++, C#, Delphi)
Brought to you by:
angusj
Menu
▾
▴
2 Attachments
#154 Offsetting can sometimes be quite slow.
The offsetting algorithm can sometimes take quite a while. It occurs mostely when several small rings are merged as part of the offsetting operation. Attached is a minimal program with a modaratly sized input (8mb), running the program on the input takes around 9hours on my machine, while running the program on other simular sized inputs will normarly terminate in minutes.
Discussion
Anonymous
View and moderate all "bugs Discussion" comments posted by this user
Mark all as spam, and block user from posting to "Bugs"
You will be much better off, if you first perform an offset using clipper per each ring separately, and then to merge them, probably not all at once, but somehow grouped to smaller batches. We are on the same boat, I am currently solving similar issues.
View and moderate all "bugs Discussion" comments posted by this user
Mark all as spam, and block user from posting to "Bugs"
op here,
If I offset each ring seperatly and then merge pairwise recursivly (think merge sort), the example can be computed in a few minutes.
However I have have deviced another algorithm that performs much better os these kinds of inputs, for this paticular input it takes around 5seconds.
The algorithm is somewat simular to the one implemented in clipper.
First a basic offsetting of each segment and point is done individually and then the edges adjacent to the right faces in the resulting planar graph are ouputted.
The main difference is that i do not use winding numbers to detect the outside faces, instead I just require that all the edges adjact to the face point outwards, and that the center point is sufficiently far away from an input segment. Doing this means that I am free to prune away segments that I can prove are not part of the outside faces before adding the intersection points. In my paticular implementation I prune the basic offset segments by doing a walk in the voronoi diagram of the endpoints of the input segmens, if the basic offset segment is always closer to an endpoint then the offset distance, it can safely be discarded. Doing this dramatically reduces the number of segments that need to be cut by the intersection sweep (benteley ottman in my case), which in turn reduces the number of intersections from O(n^2) to O(n) in most cases.