Determine the intersection Point of the two Diagonals in a quadrilateral

Hey people,

is there an easy way of dermining the intersection points of two diagonals in a quadriliteral??

Doing it by hand is quite hard since there are many special cases to consider. maybe there is already a function that helps solving the problem?

With best regards, John

[Ryan Cho]

If you are doing this on a graph get the x values of the coordinates and average them, then get the y values of the coordiantes and averagae them and then there you go (I've only tried this with parralellograms so far bu good luck)

Answer 1

[Image Analyst]

Calculate the equation of the two lines and set them equal, and solve for x, and then plug in x into either equation and get y. Just basic math

m1*x+b1 = m2*x+b2

and so on to solve for x. m is just the slope deltaY/deltaX you get from using your two diagonal points. You can use

coeffs = polyfit(x,y,1); % coeffs(1) = m, coeffs(2) = b

if you want.

[John]

Thanks for your Answer,

yes, this is the way i wanted to avoid^^ My aim is to write a function that determines the intersection of the two diagonals, of 4 random points!

The problem is, that one has to figure out the right lines, because the order of the points is not known in advance. There are many special cases to consider (i.e. m=inf, or the two lines are parallel to each other, the two lines may intersect in a point that is outside the polygon of the 4 points)

My idea is now, to try all 3 possible combinations, as the diagonals represent one version of 3 possible combinations, from the perfect matching of 4 points.

greetz

[Image Analyst]

Yes there will be special case of infinite slope. I don't see how diagonals can ever be parallel though - perhaps you can give coordinates where that's true.

Your quads area all convex aren't they? If not, then how does it make sense to talk about a diagonal if your quad is shaped like a "V"?

And I don't know why you wanted to avoid simple algebra or polyfit() - what's wrong with those methods? It's not like I'm asking you to perform rocket surgery. ;-)

[John]

Hi Image Analyst, i dont know in advance what pointconnections build the diagonals, so i have to try all 3 kombinations..

i have to add the examnination if the resulting points actually lie in the konvex hull of the four points...i dont know how to implement that right now...

     function [ Steinerpunkt4 ] = Steineropt4( Vektor1, Vektor2, Vektor3, Vektor4 )

B=zeros(2,3);

%Testing, if line from point 1 to 3 and line from 2 to 4 is a   %Steinerpoint

%Derminition of the line-equations

m1=(Vektor1(2)-Vektor3(2))/(Vektor1(1)-Vektor3(1));
b1=Vektor3(2)-m1*Vektor3(1);

m2=(Vektor2(2)-Vektor4(2))/(Vektor2(1)-Vektor4(1));
b2=Vektor4(2)-m2*Vektor4(1);

if isequal(m1,m2)          % in case of parallel lines
     a=1;
else a=0;
end

%to avoid zu high slope so that there is no zero-division

if (( m1 < -(10^(10)) || m1 > 10^(10)) && a==0 )   
        Steinerpunkty=m2*Vektor1(1)+b2;                              
        Steinerpunkt4=[Vektor1(1), Steinerpunkty];
        B(:,1)=Steinerpunkt4;

elseif (( m2 < -(10^(10)) || m2 > 10^(10)) && a==0 )  
        Steinerpunkty=m1*Vektor2(1)+b1;
        Steinerpunkt4=[Vektor2(1), Steinerpunkty];
        B(:,1)=Steinerpunkt4;

elseif a==0
        A=[-m1 ,1; -m2, 1 ];
        b=[b1;b2];
        Steinerpunkt4 = A\b;
        B(:,1)=Steinerpunkt4;

else B(:,1)=[0,0];

end

%Now testing if 1 and 4 and line 2 to 3 form a Steinerpoint

m1=(Vektor1(2)-Vektor4(2))/(Vektor1(1)-Vektor4(1));
b1=Vektor4(2)-m1*Vektor4(1);

m2=(Vektor2(2)-Vektor3(2))/(Vektor2(1)-Vektor3(1));
b2=Vektor3(2)-m2*Vektor3(1);

if isequal(m1,m2)
     a=1;
else a=0;
end

if (( m1 < -(10^(10)) || m1 > 10^(10)) && a==0 )              
        Steinerpunkty=m2*Vektor1(1)+b2;
        Steinerpunkt4=[Vektor1(1), Steinerpunkty];
        B(:,2)=Steinerpunkt4;

elseif (( m2 < -(10^(10)) || m2 > 10^(10)) && a==0 )
        Steinerpunkty=m1*Vektor2(1)+b1;
        Steinerpunkt4=[Vektor2(1), Steinerpunkty];
        B(:,2)=Steinerpunkt4;

elseif a==0
        A=[-m1 ,1; -m2, 1 ];
        b=[b1;b2];
        Steinerpunkt4 = A\b;
        B(:,2)=Steinerpunkt4;

else B(:,2)=[0,0];

end

%No testing if 1 and 2 with line 3 to 4 intersect at a Steinerpoint

m1=(Vektor1(2)-Vektor2(2))/(Vektor1(1)-Vektor2(1));
b1=Vektor2(2)-m1*Vektor2(1);

m2=(Vektor3(2)-Vektor4(2))/(Vektor3(1)-Vektor4(1));
b2=Vektor4(2)-m2*Vektor4(1);

if isequal(m1,m2)
     a=1;
else a=0;
end

if (( m1 < -(10^(10)) || m1 > 10^(10)) && a==0 )         
        Steinerpunkty=m2*Vektor1(1)+b2;                 
        Steinerpunkt4=[Vektor1(1), Steinerpunkty];
        B(:,3)=Steinerpunkt4;

elseif (( m2 < -(10^(10)) || m2 > 10^(10)) && a==0 ) 
        Steinerpunkty=m1*Vektor2(1)+b1;
        Steinerpunkt4=[Vektor2(1), Steinerpunkty];
        B(:,3)=Steinerpunkt4;

elseif a==0 
    A=[-m1 ,1; -m2, 1 ];
    b=[b1;b2];
    Steinerpunkt4 = A\b; 
    B(:,3)=Steinerpunkt4;

else B(:,3)=[0,0];

end

B(:,~any(B))=[];
length(B)

%Making sure that input Vektors/points are not returned

for i=1:length(B)-1
    if  B(1,i)==Vektor1(1) & B(2,i)==Vektor1(2)
        B(:,i)=[]
    end
    if  B(1,i)==Vektor2(1) & B(2,i)==Vektor2(2)
        B(:,i)=[]
    end
    if B(1,i)==Vektor3(1) & B(2,i)==Vektor3(2)
        B(:,i)=[]
    end
    if B(1,i)==Vektor4(1) & B(2,i)==Vektor4(2)
        B(:,i)=[]
    end
i=i+1;
end

end

[Image Analyst]

You HAVE to know the order of the points going around the quadrilateral. If you don't know the order, then there are multiple possible quadrilaterals you could build from the same set of points. So, because you must know the order, your diagonals are always points 1 and 3, and points 2 and 4. Always.

Answer 2

[Sean de Wolski]

Don't try and reinvent the wheel:

FEX:Query:line+intersect