# Can someone propose some code that will "connect the dots" to produce the correct geometric shapes (i.e., hexagons, pentagons, rectangles) from these points?

10 views (last 30 days)
Steve on 1 Nov 2019
Commented: Matt J on 5 Nov 2019
Hi,
I'm wondering if someone could propose some clever code that will automatically connect the dots (as shown in the fabricated images below) to make the correct geometric shapes below from the given points in the file (fpep.mat)? Note: the edges are actually arcs that emanate from the center points (coordinates for these center points are contained in the last two colomns of fpep.mat). Important note: these arcs must also pass through the endpoints of the triplets (triplets = the 3 points surrounding each center point).The coords of each endpoint are contained in the first 6 columns of fpep.mat). I'm excited to see what you can come up with. Thanks in advance for your help!
Center points (shown with red crosshairs in image above) are connected to each neighboring center point to produce the geometric shapes as shown in the image below:

Matt J on 1 Nov 2019
Edited: Matt J on 2 Nov 2019
This seems to do it. For the display part, it uses plotpts2d, which you've seen before.
maxDistLine=10; %User tolerance settings
maxLineLength=1500;
P=reshape(fpep(:,7:8).',2,1,[])/1000; P(3,:)=1;
V=reshape(fpep(:,1:6).',2,3,[])/1000; V(3,:)=1;
DT=delaunayTriangulation(P(1:2,:).');
E=edges(DT);
P1=P(:,:,E(:,1));
P2=P(:,:,E(:,2));
V1=V(:,:,E(:,1));
V2=V(:,:,E(:,2));
L=cross(P1,P2,1);
L=L./vecnorm(L(1:2,:,:),2,1);
sdot=@(a,b) squeeze(sum(a.*b,1));
dL=abs( sdot(L,[V1,V2]) ) ;
dL1=dL(1:3,:); dL2=dL(4:6,:);
D=1000*vecnorm(P1(1:2,:)-P2(1:2,:),2,1).';
d=maxDistLine/1000;
Q1=sdot(P2-P1,V1-P1);
Q2=sdot(P1-P2,V2-P2);
C1=dL1<d & Q1>0;
C2=dL2<d & Q2>0;
keep=sum(C1)==1 & sum(C2)==1 & (D<maxLineLength).';
E=E(keep,:);
P1=P1(:,:,keep); P2=P2(:,:,keep);
V1=V1(:,:,keep); V2=V2(:,:,keep);
dL1=dL1(:,keep); dL2=dL2(:,keep);
Q1=Q1(:,keep); Q2=Q2(:,keep);
D=D(keep,:);
EdgeTable=table(E,D,'VariableNames',{'EndNodes','Weights'});
G=graph(EdgeTable);
cut=cell(1,numel(J));
for k=1:numel(J)
j=J(k);
ej=find(any(E==j,2));
Ej=E(ej,:);
dj=dL1(:,ej).*(Ej(:,1)==j).' + dL2(:,ej).*(Ej(:,2)==j).';
qj=Q1(:,ej).*(Ej(:,1)==j).' + Q2(:,ej).*(Ej(:,2)==j).';
dj(qj<=0)=inf;
[val,keep]=min(dj,[],2);
keep=keep(isfinite(val));
ej(keep)=[];
cut{j}=ej(:).';
end
G=G.rmedge([cut{:}]);
N=size(P,3);
h=plot(G,'XData',P(1,:)*1000,'YData',P(2,:)*1000,...
'Marker','o','MarkerSize',5,'NodeColor','k','NodeLabel',(1:N));
hold on
plotpts2d([],reshape(V(1:2,:)*1000,2,[]))
hold off

Matt J on 3 Nov 2019
Think of the arc being fit through any three of the four points, then it will automatically fit through any other three points of the four.
That is only apparent now that we know the center-to-endpoint distance can be assumed the same for all triplets. Were this not the case, it would not be true in general. Four arbitrary points will not generally be fit by a circle.
There is still the question though of what output you are still looking for from the code. If it is the listing of connected center points, you already have that. That does not change, regardless of whether we are connecting things with lines or circular arcs.
Steve on 3 Nov 2019
There is still the question though of what output you expect from the code. If it is the listing of connected center points, you already have that. That does not change, regardless of whether we are connecting things with lines or circular arcs.
How would I actually go about connecting the dots with circular arcs instead of straight lines? In addition, I would really love to see comments in your code so I could follow along. I am still amazed at how well it works and how quickly you whipped it up. Thanks again Matt!
Steve on 4 Nov 2019
Hi Matt,
If it's not too much trouble could you possibly apply comments to your code (above)? I am having trouble figuring out what was done and I would really like to learn.
Thanks,
Steve

Matt J on 5 Nov 2019
Edited: Matt J on 5 Nov 2019
Here is a refinement of my earlier answer which I think performs better. It uses the attached classdef file to create objects representing these special kinds of triplet graphs. You will find the code commenting more detailed than the earlier version.
For display purposes, the class contains methods that will plot the graph joining the center points with either lines or arcs. The usage is simple,
obj=TripletGraph(fpep);
figure(1);
obj.plotarcs;
figure(2);
obj.plotlines;
The plotarcs method joins the points using cubic spline fitting. I think you will find this gives essentially the same as what you would get with circular arc fitting. The 4th and higher order Taylor expansion terms of the circular arcs should be negligibly small for such large radii of curvature as we see here.

Steve on 5 Nov 2019
Looks amazing Matt! Truly, a big thanks to you for all your help and effort. I wish there was a way (on this site) to commend you properly--not only for your stellar MATLAB skills, but also for your willingness to go above and beyond when helping others. You are (by far) the most knowledgeable and helpful MATLAB expert I have ever come across, here, or anywhere. If you ever need a job recommendation, I would be happy to give you one. Please feel free to contact me anytime.
All the best,
Steve D.
Matt J on 5 Nov 2019
You're very kind. Just so you know, if you like a particular answer, you can award it extra points by up-voting it.

Sherif Omran on 1 Nov 2019
Yes, i propose using the least square root used for shortest distance, see the Dijkstra algorithm to connect your dots
Implementation is not that difficult, i am sure you can do it.

#### 1 Comment

Steve on 1 Nov 2019
Thank you Sherif. I don't think that this would work though because these connector lines are not necessarily the shortest distances. Also, they are actually arcs, not straight lines. However, perhaps you can run some code on this to show otherwise. I would be curious to see what comes of it.