How to eliminate "undercuts" of a 2d curve?

I have a curve made up of a 2d vector of points which has "undercuts". I'd like to create a new curve which eliminates these undercuts. In the figure below, I want to turn the blue curve into the red curve. I could figure out something from scratch (maybe just march along x and skip indices where x does not increase,) but I suspect this can be done with existing functions. In the end, I'd also like to end up with an even point spacing in x, but I can handle that with interp1 after the fact if needed. thanks

[John D'Errico]

I don't know of any simple solution, using existing tools. You will need to just write it. To the extent that this will use existing low level tools, you can describe that anyway you want. But no off the shelf tool exists that I can think of.

Answer 1

[William Rose]

@paul harder,

data=load('undercutdata.txt');
xin=data(:,1);
yin=data(:,2);
xout(1)=xin(1);
yout(1)=yin(1);
i=2; j=1;
while i<=length(data)
    if xin(i)>xout(j)
        xout(j+1)=xin(i);
        yout(j+1)=yin(i);
        i=i+1;
        j=j+1;
    else
        i=i+1;
    end
end
plot(xin,yin,'-b.',xout,yout,'-rx');

Produces the plot below.

The undercutting in the plot above is a bit different than in your drawing. To get results as in your drawing, modify as follows: change the code so it only removes undercuts where y is decreasing, on the first pass. Then negate the output y-vector, to turn the output of pass 1 upside down, and run it through the filter again. Then negate the output y-vector of pass 2, to turn it right-side up. Flippng it in time is an alterative to negation, and would give the same result.

[William Rose]

@paul harder, Correction to the two-pass method needed to produce a figure like the one you drew:

On pass 1, only remove undercuts where y is decreasing. On pass 2, process the pass 1 output signal in a similar manner, but start at the end and work toward the start (Matthew 20:16), removing down-going undercuts. It works. Plot below has 3 panels. Top panel: output of the original algorithm given in my initial answer. Middle panel: Input signal and pass 1 output. Bottom panel: input signal and pass 2 output. The bottom panel looks like your original drawing.

[paul harder]

@William Rose you are the man! hopefully others will find this useful in the future as well.

[Star Strider]

I encourage that to be made suitably robust (with error-checking and such) and then submited as a File Exchange contribution.

[paul harder]

Agreed. I could envision many possible applications for this.... and many applications for a fancier 3d version which "drapes" an object surface along a specified vector direction. I suppose it's the same idea as mapping shadows.

Another idea i had was to code it as "looking down from above, which points are in front."

[William Rose]

@paul harder, @Star Strider, I have done as you suggested: I have added error checking to make it more robust, in preparation for submission Matlab File xchange. I have also turned it into a function:

function [xout,yout]=undercutRemoval(xin,yin,varagin) 

where varargin is an optional "method" argument. If you would provide any feedback before I submit, I would appreciate it. There are (at least) four approaches to undercut removal. method selects which one. It is easier to explain by a picture - see below.

Methods 3 and 4 may look unappealling due to their assymmetry, but they have the virtue of being unbiased, i.e. they are equally likely to raise or to lower the mean y-value of a random signal with undercuts. Methods 1,2 always raise,lower the mean y-value.

The figure was generated by undercutRemovalTest.m, which calls undercutremoval() once for each method. @paul harder, woud you try the four methods on your data file, which is more realistic than my simulated data, to make sure nothing crazy happens? You would only have to change the filename in undercutRemovalTest.m. Thank you.

The computer animation people have efficient ways of solving the 3D version of the problem. When they render a scene, they remove objects and parts of objects that are obscured by more foreground objects. I don't know how they do it.

The 3D draping idea reminds me of a problem I worked on a few years ago: determining the orientation of the scapula (shoulder blade), relative to the thorax, by scanning the skin of the upper back. The idea was that the skin drapes over the scapula, so it might be possible to figure out the scapula's orientation by observing the skin and modeling the draping process. It didn't work very well. The reason we cared: when analyzing shoulder joint function, one is limited by the difficulty of determining scapular orientation. The scapula glides around under the skin, so you cannot track its position by markers on the skin, the way you can track the humerus, femur, pelvis, etc. The skin does undercut the scapula in subjects with significant scapular winging, as seen below.

https://www.consultant360.com/articles/photoclinic-winged-scapula

[paul harder]

@William Rose you continue to impress with your insights and generosity! I honestly hadn't realized that there are two ways to span any undercut and had some "method 1" blinders on. The function appears to work great!

Your comments about the 3d version are interesting. I suspect the CNC machining world has also solved this problem somehow. Luckily, I don't really need the 3d version in my application :)

[paul harder]

@William Rose the one minor tweak I would suggest is to synchronize the subplot axes in "undercutRemovalTest.m", so users can more interactively navigate the plots when applying this function to larger data sets. Suggested changes to lines 12 and 19 below

%undercutRemoval.m  W. Rose 20211206
%Test function undercutRemoval.m and demonstrate methods 1 to 4.
%Calls data file undercutdata.txt.

clear
data=load('undercutdata.txt');
xin=data(:,1);
yin=data(:,2);
figure;
for i=1:4
    [xout,yout]=undercutRemoval(xin,yin,i);
    h(i)=subplot(4,1,i);
    plot(xin,yin,'-b.',xout,yout,'-rx');
    legend('In','Out'); grid on
    titlestr=sprintf('Method %d',i);
    title(titlestr);
    xlabel('x'); ylabel('y');
end
linkaxes(h,'xy')

[William Rose]

@paul harder, Thank you for your kind comments, and thank you for the linkaxes() suggestion, which I have incorporated. I never knew about linkaxes().

Good luck,

Bill

[Star Strider]

The scapula application would be important in quantifying certain shoulder-girdle muscular dystrophies. (Not my area of expertise, however I remember them from my Neurology rotations.)

[William Rose]

@Star Strider, you are certainly correct. We collaborated with physicians at Nemours Children's Hospital and Shriners Childrens Hospital in Philadelphia. Subjects included patients with brachial plexus birth injuries and scoliosis.