## How to get things trimmed robustly

Friday, April 6th, 2007 at 6:53 pm

I was told to get the following function done quickly because it was needed by someone. I didn’t enjoy coding it, and much less attempting to test it; with the lack of a good interface I had to hack things so that, instead of making const scallop passes from a given boundary, it offset from a rectangle, and fed the results through the trimming function, as shown in the picture.

I don’t want to touch this code again, so I’ve done it properly.

Suppose you have a set of closed boundaries given by a series of points in 2D (the black curves in the diagram), and a second series of points defining a path (the blue curve). You want to trim one by the other.

In this example, it looks like it should be about three short paths corresponding to sections bc, de, and hi. If you were unlucky, you might also get a tiny fragment of the path just going inside at point t, but it’ll probably be too short for any use and need to be filtered away.

The basic functions you need are:

inside(boundaries, point) -> true if point is inside the boundaries.

sequence of intervals along the line(p,q) whose endpoints are either a, b, or a point exactly the distance s from the boundaries.

The implementation of inside() is easy — consider a horizontal line through the point, mark the positions where the boundaries cross it, and it’s inside if there is an odd number of these to the right of the point. This value is not reliable under a change of line direction (consider a vertical line, for example) when the point is practically on the boundary.

The function radapproaches() looks a little more complicated, but it’s an important building block that I tend to have floating around. The implementation is not simple, but it’s definition does give you something robust.

Now choose a tolerance value s, as something small. Run radapproaches() against every line segment in the (blue) path you want to trim, and collect up all the proper end points (the ones which are exactly the s distance away). In this example there will be 10 values (a,...,j), although you may get one or two extra on that outside corner in red between the i and the t, depending on how unlucky you are with your floating point calculations. This instability is similar to the unreliability of the inside() function, in that it is caused by changes of direction.

Now call the inside() function on each of these 10 points. Since these points are a distance s away from the boundaries, it’s reliable, and we can be sure that when we have two consecutive points that are both inside, then that entire section of the path is on the inside of the boundaries. You need to do some special cases with the ends of the path, but the simple result will be that your sequence of points can be grouped into pairs (b--c), (d--e), and (h--i). The worst that can happen in terms of miscalculation is that you could get a spurious point if one of the corners of the path is on the inside at exactly a distance s from the boundaries.

Job done.

But wait, we were supposed to trim the path to the boundary, not the boundary minus a small offset. Also, I’ve made a mistake: points c and d are adjacent and on the inside, so you should also get the section (c--d) in the list. Chaining this with the other two inside sections, gives us two sub-paths: (b--e) and (h--i).

Some might say this answer is pretty dreadful. Not only is the path being trimmed at a distance s of the boundaries, but parts of it can cross back over the boundary without being trimmed.

But others, who have been doing this sort of thing quite a few more years than they care to remember, recognize this as a good feature, and furthermore it’s what justifies this ridiculous implementation in the first place. When you trim a path by a set of boundaries, and part of the path coincides with part of the boundary, your path can get very fragmented. Example: Trimming a linearized arc A by linearized circle C, where both have the same centre point and radius. (CADCAM usage is always throwing up annoying cases like this.) So, allowing the path to stray across the boundaries by a small tolerance and not be split up if it comes back inside is a good thing.

To finish up the ends, extend the point b towards a to somewhere where it crosses the boundary. These crossing points can be collected during the same run through and, although it’s an unreliable calculation, it doesn’t matter, because it’s bound by these two values, both of which are sort of acceptable within tolerance.

Come to think of it, after writing it up at such length, I’m not going to do it like this again if I’m forced to. Hopefully that won’t be necessary if I’ve taken enough precautions to avoid being disenfranchised from my code again. It’s not the money that matters, it’s the utter waste of two days of my precious life that rewriting this function has required me to expend.

### 1 Comment

• 1. Freesteel » Blog Ar&hellip replies at 17th May 2007, 2:52 pm :

[…] therefore triangle it is within. The best answer is probably to make an analogue of my line cutting offset polygon function, and forgo any chance of makin […]