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

5 views (last 30 days)
Steve on 1 Nov 2019
Commented: Steve on 8 Sep 2020
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 Steve on 8 Sep 2020
By the way, one very important concept that needs to be in the code is that there should never be allowed, a polygon that has edges that turn outward (see attached images) at any point. In other words, all of the polygons must never have edges that (depending upon the direction one traverses along the edges of the polygon) make an angle greater than 180 degrees with any of its conjoined edges (i.e., having a common vertex). If anyone could provide any input on how to do this, that would be great.   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. ##### 2 CommentsShow 1 older commentHide 1 older comment
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.
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.

### Categories

Find more on Images in Help Center and File Exchange

R2019a

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!