Can someone propose some code that will "connect the dots" using circular arcs?

Hi,

Can someone propose some alternate or additional code (to the code proposed in my last posting here) that will automatically connect the dots (dots = center points of each triplet), as shown below, to generate the correct polygons from the given points in the attached file (fpep.mat)?

Note 1: The edges of each polygon must be circular arcs (we cannot use splines for this one) that connect all the center points.

Note 2: Each "triplet" will produce precesely 3 circular arcs (except for those along the outer borders).

Note 3: Each arc's initial and final slopes are given by the angle between the centerpoint and the corresponding endpoint for that arc (remember that the inital and final slopes of each arc must be equal-and-opposite; so, the "starting" and "landing" angles must be averaged).

The coords of each endpoint are contained in the first 6 columns of the attached file (fpep.mat) and the coords of the center points are contained in the last two columns.

Once again, I'm excited to see what you can come up with. Thanks in advance for your help!

[Steve]

It should look something like this:

[Image Analyst]

But the whole assumption that there will be one single arc is questionable. Getting an arc for a particular cell wall will have one arc if you fit points on one side of the cell wall, but an arc in the opposite direction if you consider using points on the OTHER side of the cell wall. Any way to resolve that? If they are like cell walls of air bubbles in suds/lather/foam, then is the "pressure" inside each cell the same, or does it vary with cell size, such that the cell on one side may influence the arc direction more than the cell on the other side?

[Steve]

But the whole assumption that there will be one single arc is questionable. Getting an arc for a particular cell wall will have one arc if you fit points on one side of the cell wall, but an arc in the opposite direction if you consider using points on the OTHER side of the cell wall. Any way to resolve that?

Yes, there is actually an easy way to resolve this. The arcs will always be very shallow--almost straight lines. So, the angles realized by the line connecting the correct endpoint to the a corresponding center point will always be shallow (say, less than 10 degrees).

If they are like cell walls of air bubbles in suds/lather/foam, then is the "pressure" inside each cell the same, or does it vary with cell size, such that the cell on one side may influence the arc direction more than the cell on the other side?

There is no way (that I know of) to determine the concavity of the arc (i.e., which way the arc will bend), other than to just look at the angle made by endpoints and to use this to define the "starting" and "landing" slopes of the arcs.

This should be fairly straight forward but I am just not proficient enough with Matlab to be able to create some code to do this. Would you be able to help with the code for this? Thanks in advance for your help.

[Image Analyst]

You did not answer the question. Let me try again.

1. If one arcs up, however shallowly, and one arcs down, which equation/arc do you pick?
2. And, why would you even pick either of them? Why not just say the connecting edge is a straight line?
3. Why do you think you NEED an arc rather than a straight line?

[Steve]

I actually answered both your questions; however, it's obvious that I failed to make my points clear enough for every possible member of the audience. Below I have addressed your three (technically four) new questions. This time I have included pictures for clarity:

1. If one arcs up, however shallowly, and one arcs down, which equation/arc do you pick?

I'm not sure what you mean by "which equation/arc do you pick?", because there is only one way that the arc can go--unless you do not care how shallow the arc is; in that case the other arc choice will be very bulbous (see last picture below). The path of the correct arc is determined by the starting and ending slopes (see first picture below).

2. And, why would you even pick either of them? Why not just say the connecting edge is a straight line?

You don't have to "pick" anything. The starting (and ending) slopes of the only possible arc (within a given "shallowness") for a particular endpoint are already given by the angle made by the endpoint and its corresponding center point.

We can not "just say" that the connecting edge is a straight line, because it is not a straight line. All the edges must be circular arcs.

3. Why do you think you NEED an arc rather than a straight line?

I don't just think we need circular arcs, I know we need circular arcs. We need arcs because the original, physical, edges were actually circular arcs--not straight lines. All of our research is based on this fact.

I'm pretty tight with the physics here. What I really need is some help with the MATLAB to produce the arcs and to store all their attributes (i.e., arc lengths, index/node numbers) in a variable.

Thanks again.

Answer 1

[Matt J]

The spline plotting that we came up with in our previous conversation looked like this

            for i=1:N
                
                C1=AP(:,1,i); C2=AP(:,4,i);  %Center points
                V1=AP(:,2,i); V2=AP(:,3,i);  %Triplet end points
                
                L=norm(C2-C1);
                U=(C2-C1)/L;
                
                s=[0,  dot(V1-C1,U)/L ,  dot(V2-C1,U)/L  , 1];
                
                APi=interp1(s.',AP(:,:,i).',sq.','spline');
                
                X(:,i)=APi(:,1);  %x coordinates on connecting curve
                Y(:,i)=APi(:,2);  %y coordinates on connecting curve
                
                
            end

It is this section of code (and nothing else) that you need to modify to connect C1 and C2 (the center points of the i-th arc) with a different curve of your choosing.You simply must fill X(:,i) and Y(:,i) with the x and y coordinates of the points that form the desired connecting curve (based on C1,V1,V2, and C2).

[Steve]

Thanks for your input Matt! Please excuse my ignorance, but how would I do this exactly?

[Steve]

Alternatively Matt, can we just use the straight chords/edges found in your first code, along with starting/ending slopes defined by the corresponding endpoints to create the arcs? Thanks again!

[Matt J]

That is not an alternative. That is exactly what I'm saying you would do. For example C2-C1 is the vector from C1 to C2, and similarly V1-C1 is the vector from C1 to V1. The angle between those two vectors is theta1. In a similar way you can find theta2. Then you average them, and so on...

[Steve]

I gotcha now. Sounds great! How would the code look for this? Thank you again!

[Steve]

Matt, I'm still stumped on how to modify the code as you've described. Any help you could offer would be greatly appreciated.

[Matt J]

Well, before code can be written down, decisions need to be made (by you) about how you want to approximate the circular arc. In our last conversation, I recommended a spline approximation because the fomula for an exact circular arc has numerical instability issues. For example, the circular arc between two points [-D,0] and [+D,0] on the x-axis has the formula,

where θ is your initial slope angle. But here, will often be a very large number and the subtraction of two large numbers in the formula above can leave you with floating point junk.

[Steve]

Matt, I should have mentioned this earlier, but in this case, the arcs do not need to pass through the endpoints. We are only using the endpoints (in this case) to define the slopes of the lines that are tangent to the arc at each end (i.e., at each center point). I believe this should not require any approximations then. I think your suggestion for using the splines was perfect for the previous case (where we wanted the arcs to pass through the endpoints). Please let me know what you think. Thanks again!

[Matt J]

I believe this should not require any approximations then.

No, the equation in my last comment is precisely that for the circular arc you say you want. It has not been constructed to pass through any other points than the two centers. So, the problems are still there.

[Matt J]

You might wish to give this version a try. It is a quadratic approximation, but it is constrained to run symmetrically from C1 to C2, and with the slope constraints you have stipulated.

            for i=1:N
                
                C1=AP(:,1,i); C2=AP(:,4,i);
                V1=AP(:,2,i); V2=AP(:,3,i);
                
                L=norm(C2-C1);
                U=(C2-C1)/L;
                dV1=(V1-C1)/norm(V1-C1);
                dV2=(V2-C2)/norm(V2-C2);
                theta1=acosd(dot( dV1, U) );
                theta2=acosd(dot( dV2, -U) );
                theta=(theta1+theta2)/2;

                
                
                W=cross( cross([U;0],[dV1;0]), [U;0]); 
                W=W(1:2)/norm(W);
                D=L/2;
                a=-tand(theta)/2/D;
                
                t=2*D*sq;
                s=polyval([a,0,-a*D^2],t);
                
               XY=(C1+C2)/2+U*t+W(1:2)*s;
               X(:,i)=XY(1,:);
               Y(:,i)=XY(2,:);
                
                
            end

[Steve]

Thanks again for your input Matt. Below is a screenshot of the plot for the latest snippet of code you proposed:

Any idea of what may be going wrong?

[Matt J]

No idea, but the updated version of TripletGraph that I attached shouldn't have that problem.

Answer 2

[Steven Lord]

Are you trying to do something like path planning for an autonomous vehicle, passing through waypoints along the way? If so consider the functions for that purpose in Automated Driving Toolbox.

[Steve]

Steven,

Thanks for your response. We are actually just looking to connect the dots with circular arcs and to store the data of all the connections (i.e., length of circular arcs) for analysis--just some fundamental research we are doing. Do you have an idea on how we could do this?

Thanks again,

Steve

[Steve]

Is there not one Matlab expert out there that can help with this one?

Answer 3

[Matt J]

I have attached a version of TripletGraph.m which implements methods of joining the points with ideal circular arcs, as well as with the spline and quadratic approximations discussed previously. The code below plots your data with circular and quadratic arcs super-imposed. To my eye, there is no visible difference, so it seems like it should be sufficient to use the quadratic approximation, which as I have said is numerically a lot safer.

load fpep
obj=TripletGraph(fpep);
figure(1);
obj.plotcirc; %join with ideal circular arc formula
hold on;
obj.plotquad; %join with quadratic approximation
hold off

[Steve]

Thanks again, so much, for all your help Matt. I ran your latest code. The circle and quadratic approximations are very similar (as you said). I must have failed again however, to make known what is really needed here though. What we really need is a single, continuous, circular arc that starts at one center point and ends on the next (for all center points). No "approximated" curves will suffice for this part of the study.

Isn't there an easy way to just replace your original straight edges/chords with continuous circular arcs using the fact that slope of the circular arc (y' = -x/y) is known at the center points?

Thanks again,

Steve

[Matt J]

I must have failed again however, to make known what is really needed here though. What we really need is a single, continuous, circular arc that starts at one center point and ends on the next (for all center points).

I am confused. The plotcirc() command does exactly that. What are you saying is 'discontinuous' about the circular arcs that it is drawing?

[Steve]

Sorry about the confusion Matt. Below is a screenshot of (Figure 1), which shows that there are actually individual points plotted all along each arc. This is why I believe that the arcs are created as piecewise sections, just as in the case with the splines. Can you make sense of this? Thanks again.

[Matt J]

Well, yes, any plot on a digital computer is a joining of discrete points, just like any digital image is composed of discrete pixels. But the difference here, as compared to the spline approximation from before, is that here the discrete points are derived from the exact equation of, and lie on, an actual circle, as opposed to some cubic polynomial curve. Are you saying that when you zoom the plot, you want Matlab to resample the ideal circle more finely?

[Steve]

No resampling needed really. We just need a continuous circular arc (for each center point pair) that we can call to later. The discrete points mentioned above do not show up along the continuous straight chords (from your first code run). Is there any way to do this with the circular arcs? We really can't have any modular or approximated curves here. Thanks for your continued help.

[Matt J]

It's possible to write a function to return any continuous query point on a specified arc, but you need to decide on some way of parametrizing the arcs, so you can tell the function where along the arc you want to evaluate the point. In the code as it is now, these lines

                s=sqrt(Dcot.^2-(t.^2-D.^2))-Dcot;
                
               XY=(C1+C2)/2+U*t+W*s;

compute the XY coordinate located at a (signed) distance t from the center of the chord. If you like that parameterization, you can easily reuse those calculations in a separate query function.

[Steve]

Matt, it looks good. Can that arc later be defined by just the two points and a radius? Thanks again!

[Matt J]

The radius is

norm(C1-C2)/(2*sind(theta));

[Steve]

That is awesome! Could you send me the final rendition of the code? Thanks so much Matt!

[Matt J]

You already have it. I’ve made no real changes.

[Steve]

Matt,

I apologize. I thought you had changed the code again to produce the "continuous" arcs (with no discrete points along the arc) we spoke about. By the way, we will never need to evaluate a particular point on the arc (other than at the endpoints). What we really need from the code (besides a plot), is a single output file that contains the following information on the arcs:

1. arc lengths
2. radii
3. starting/ending points (triplet center points)
4. thetas (w/ corresponding theta1, theta2 angles) for each arc.

Also, the code I have still also generates arcs via spline and quadratic approximations as well. Would it be too much to ask for a version of the code that just generates the arcs using only the ideal circular arcs method? Thanks again!

Best,

Steve

[Steve]

Matt, in other words, you provided a bunch of extra snippets of code to be added to the original code. I am unsure of where these are to be placed. Also, after running the version of the code that I have, I wasn't able to find the output information mentioned above. Can you help with this? Thanks again Matt; I really appreciate all your help.

[Steve]

If anyone could propose some code mods that will let me extract and store the information listed above (as described in my new post here), it would be greatly appreciated.

[Steve]

I have attached a screenshot of an Excel file that I created, which contains the data I manually extracted from running the aforementioned code. We would really like to have Matlab generate it automatically. If anyone can help with this, we would realy appreciate it. Thanks in advance for any help you could offer.