X,Y line offset algorithm without self intersection

[CanOr1]

I am trying to create an X,Y line offset algorithm without self intersection, to probe the chuck/tool on a cnc lathe. The code is written in C#. The Y-axis component of the algorithm works the X-axis does not. Have tried using code seen in different forums elsewhere but have hit a wall. Any help would be greatly appreciated. This is the algorithm within the program.[/SIZE][/FONT]

private void OffsetData(double R)
        {
            double Increment = 0.01;
            X2 = (double[])X.Clone();  // copy original

            // apply a circle to every measured point and
            // push neighbor points out beyond the circle
            for (int i = 0; i < Npts; i++)
            {
                // offset forward
                double k = i + Increment;
                while (k < Npts - 1)
                {
                    // determine how far away the neighbor is in Y
                    double dy = (k - i) * DeltaY;

                    // compute extent outward in X
                    double d = R * R - dy * dy;
                    if (d < 0) break; // beyond circel radius - no need to go further
                    double dx = Math.Sqrt(d);

                    //interpolate to find X[k] where K is a fraction
                    int ki = (int)k;
                    double Xk = X[ki] + (X[ki + 1] - X[ki]) * (k - ki);

                    // if x value is within circle push out
                    if (X2[i] < Xk + dx) X2[i] = Xk + dx;
                    k += Increment;
                }
                // offset backward
                k = i - Increment;
                while (k > 0)
                {
                    // determine how far away the neighbor is in Y
                    double dy = (k - i) * DeltaY;

                    // compute extent outward in X
                    double d = R * R - dy * dy;
                    if (d < 0) break; // beyond circel radius - no need to go further
                    double dx = Math.Sqrt(d);

                    //interpolate to find X[k] where K is a fraction
                    int ki = (int)k;
                    double Xk = X[ki] + (X[ki + 1] - X[ki]) * (k - ki);

                    // if x value is within circle push out
                    if (X2[i] < Xk + dx) X2[i] = Xk + dx;
                    k -= Increment;
                }
            }
        }

Within the image the yellow line represents the boundary line and the black line shows the actual line traveled by the tool. Within the circle you can see the tool goes beyond the boundary thus damaging the chuck and product.
Appreciate your time on this manner, looking forward to everyone's thoughts.

[wolle]

Code is often the ultimate explanation of an algorithm but only if it works. Yours doesn't so you will have to explain the algorithm in some other way. Only then can one tell what's wrong with the code.

[CanOr1]

Thanks for your response Wolle. So I'll start from the beginning. To create the starting reference line, there's a program that first probes the tooling every 40 thousandth of an inch which generates an exact x,y coordinate for each point. This, once completed creates a highly accurate profile of the tooling (the Red line). Then, this program (the one we're trying to correct) should give an offset distance from the red line (which could be any programmed distance but typically an 8th or 16th of an inch) which the tool should not exceed or intersect with during operation or while programming the tools passes.
Hope this gives better insight. If not please let me know.

[wolle]

I suppose X is an array holding the input x,y-coordinates but it seems X is one-dimensional. Does it mean one of the coordinates, say x, is implicit in the array index while the other one, say y, is actually stored? Does Npts stand for "number of points" denoting the size of X?

I suppose R means radius and "circle" is mentioned in a comment. Which role does this circle play in the algorithm? Is it somehow "moved" along one side of the reference line represented by X and used to calculate the offset distance? Please explain exactly how this is supposed to work.

Observations to the code:

You are using a floating point as loop variable (double k). To repeatedly add up the same floating point increment may result in a rounding error eventually. This may cause problems and especially in this case where k is cast into an int and used as array index. I recommend you instead use an integer loop variable and calculate k from it where needed.

What I can see the code in the two while loops are identical (except for the increment/decrement of k). Is this intentional? Are the forward and backward directions fully symmetrical?

[CanOr1]

Hi Wolle, hope the following adequately answers your questions.

1)I suppose X is an array holding the input x,y-coordinates but it seems X is one-dimensional. Does it mean one of the coordinates, say x, is implicit in the array index while the other one, say y, is actually stored?

Answer: The X value should only be the X value of the x,y coordinate of each point taken while probing the tool.

2)Does Npts stand for "number of points" denoting the size of X?

Answer: Npts stands for the total number of points on the line taken during the initial probing exercise. So if the tool profile is an inch long and a point is taken every .04 of an inch there would be 25 points taken or Npts =25. as I understand it.

3)I suppose R means radius and "circle" is mentioned in a comment. Which role does this circle play in the algorithm?
Answer: Yes R is radius. The circle dictates the offset. Essentially the offset is expressed as a ring which is around the starting x,y reference point and every other point there after. It continues to offset these rings until the rings intersect between two points. This intersection is what defines the offset line. Sorry if I poorly explained that.
Here's a pictoral of what I'd like to express.
Attachment 35423

4)Is it somehow "moved" along one side of the reference line represented by X and used to calculate the offset distance? Please explain exactly how this is supposed to work.
Answer: How it works (but not ideally how we'd like) is it incrementally offsets rings from two points beside one another until both these points offsets intersect. This intersection defines the offset. This occurs from one side to the other (right to left) but is not biased in a single direction and could work left to right. That's to say within this process it systematically calculates the offset between the first two points then moves to the next point. Please refer to the image above. Hope that this makes sense. If not I can elaborate.


Observations to the code:

You are using a floating point as loop variable (double k). To repeatedly add up the same floating point increment may result in a rounding error eventually. This may cause problems and especially in this case where k is cast into an int and used as array index. I recommend you instead use an integer loop variable and calculate k from it where needed.

Response: Thank you, we'll take a look at this!

What I can see the code in the two while loops are identical (except for the increment/decrement of k). Is this intentional? Are the forward and backward directions fully symmetrical?

Answer: We believe is this intentional but are not 100% certain as we can only reflect on the comments like yourself and cannot ask the individual whom wrote the code, from our perspective we might be stating the obvious but the lines profile wouldn't change in its total profile but if you were in the middle of the line it's left and right side would not be symmetrical reflections of one another. Hope this feedback is helpful, I greatly appreciate your time and thoughts on this issue.

[CanOr1]

probed file.pdf

[CanOr1]

Please let me know if the pdf doesn't work for you Wolle. Thank you.

[wolle]

Please let me know if the pdf doesn't work for you Wolle. Thank you.

Hi again, sorry for the delay.

Yes I can read that pdf-file fine. I think I understand the problem now but I don't understand why you need the two innermost while loops in your code?

Let's say two adjacent probed profile points are the centers of two overlapping circles with the same radius. Then to find the two intersection points of the two circles at a certain distance (offset) is standard geometry. I can be done with a closed (no iteration) formula.

In principle it's just to calculate the normal to the line between the circle centers, then multiply the normal with the wanted offset distance, and finally add the adjusted normal to the middle point between the circle centers. There are two intersection points and the one outside the product is used.

Note that in the solution above the offset distance is fixed. This makes the circles somewhat superfluous so maybe it's the degree of overlap between the circles that's supposed to be fixed and the offset varies? In that case my suggested solution must be modified to reflect that but still, the result is a closed formula so no iteration is necessary.

Furthermore, the above solution strategy has an element of averaging. It means sharp points in the probed profile may be cut off. I can think of other strategies that avoid this but maybe you should make a search for solutions in the scientific literature to be on solid ground here.

[CanOr1]

Good Morning Wolle! Thank you for your help and time in this matter we truly were at a loss to understand the behaviour of the program. We had a machine that worked in the past and had the same code, so we tried all the suggestions unfortunately still one piece always seemed to be missing. In the end we removed some lines of code that gave a zero reference x,y start and a space at the end of the code and for some reason (which we still don't understand) this resolved the problem? I just wanted to send my deep gratitude for your time and effort. This has been quiet a frustrating undertaking and your help always gave us a bit of hope to try a different approach. Thank you!

[wolle]

Thank you!

You're welcome.

I based my reply in #8 on the pdf-file you posted but after having had a look at the actual code I don't think it quite correctly describes what the code does.

Instead it's more like what I assumed in #4. The algorithm slides a circle along the profile. The circle always touches but never intersects with the profile. This means that as a minimum the circle radius R should always be added to the x-values. But this is not always enough. In deep narrow valleys the circle may still intersect will the profile so more than R must be added to some x-values. This is what the innermost while loops ensure. Since you have changed the code you must ensure it still can handle deep narrow values.

Since the algorithm deals independently with each value in the X array it has no knowledge of direction and so "outside" the profile always means "above" the profile, that is positive values are added to the x-values. It also means one could add R to all x-values right from the start. This should resolve any corner cases where R isn't properly added so why not try,

     X2 = (double[])X.Clone();  // copy original
     for (int i = 0; i < Npts; i++) X2[i] = X2[i] + R; // add minimum offset

Good luck!

[CanOr1]

Sorry if I misrepresented any info, unfortunately I'm not familiar with c-code and was echoing the understanding fellow staffers here had. Thanks Wolle, so far so good with regards to corner's but if we encounter any issues we'll definitely be applying that code. Again I'd like to thank you for your time and knowledge in helping us.
When your in a position where you don't understand something but still have to fix it under tight time lines, help from kind people like yourself is priceless. Hope you have a great weekend Wolle. Been a pleasure.