3 views (last 30 days)

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

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);

J=find(sum(adjacency(G),2)>3).';

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.

Sign in to comment.

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.

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.

Sign in to answer this question.

Opportunities for recent engineering grads.

Apply Today
## 0 Comments

Sign in to comment.