does convex hull intersect?

Hello. The codes shown produces two convhull. I want to generate a parameter p such that

if convhull intersect, p=false

else, p=true. Any help or suggetions regarding this. Thanks in advance.

figure
for ii=1:2
    rand_theta(ii,:) = sort(rand(1,10)).*2*pi;
    rand_beta(ii,:) = sort(rand(1,10)).*pi - pi/2;
    radius = 5;
    [x(ii,:), y(ii,:), z(ii,:)] = sph2cart(rand_theta(ii,:), rand_beta(ii,:),radius);
    %[X, Y, Z] = meshgrid(x,y,z);
    k = convhull(x(ii,:), y(ii,:), z(ii,:));
    trisurf(k, x(ii,:), y(ii,:), z(ii,:));
    hold on;
    
end

Answer 1

[Matt J]

You can use intersectionHull() from

https://www.mathworks.com/matlabcentral/fileexchange/30892-analyze-n-dimensional-convex-polyhedra?s_tid=srchtitle

for ii=1:2
V{ii}=[x(ii,:); y(ii,:); z(ii,:)]';
end

S=intersectionHull('vert',V{1},'vert',V{2});

If S.vert is empty, there is no intersection.

[CHANDRABHAN Singh]

@Matt J

I am getting some error. Can you please help me to rectify this?

Error using matlab.internal.math.qhull

qhull precision warning:

The initial hull is narrow (cosine of min. angle is 1.0000000000000002).

A coplanar point may lead to a wide facet. Options 'QbB' (scale to unit box)

or 'Qbb' (scale last coordinate) may remove this warning. Use 'Pp' to skip

this warning. See 'Limitations' in qh-impre.htm.

QH6227

qhull precision error: Only 4 facets remain. Can not merge another

pair. The input is too degenerate or the convexity constraints are

too strong.

While executing: | qhull Qt

Options selected for Qhull 2010.1 2010/01/14:

run-id 139442447 Qtriangulate _pre-merge _zero-centrum _max-width 11

Error-roundoff 8.1e-15 _one-merge 5.7e-14 _near-inside 2.8e-13

Visible-distance 1.6e-14 U-coplanar-distance 1.6e-14 Width-outside 3.2e-14

_wide-facet 9.7e-14 _narrow-hull -2.2e-16

Last point added to hull was p9. Last merge was #3.

At error exit:

Convex hull of 24 points in 3-d:

Number of vertices: 4

Number of facets: 4

Statistics for: | qhull Qt

Number of points processed: 5

Number of hyperplanes created: 9

Number of distance tests for qhull: 24

Number of distance tests for merging: 15

Number of distance tests for checking: 0

Number of merged facets: 3

Maximum distance of merged vertex below facet: -1.8 (27040992886468.4x)

Error in convhulln (line 64)

[k,vv] = matlab.internal.math.qhull(x', opt);

Error in lcon2vert>con2vert (line 453)

k = convhulln(D);

Error in lcon2vert (line 252)

[Zt,nr]=con2vert(AAA,bbb,TOL,checkbounds);

Error in intersectionHull (line 132)

[V,nr,nre]=lcon2vert(A,b,Aeq,beq,TOL);

Error in meso_model_3d (line 58)

S=(intersectionHull('vert',V{1},'vert',V{2}));

%% Generation of a aggregate particle and fixing the boundries
volume = 0;
number = randi([6 10]);
theta_m = zeros(200,11); beta_m = zeros(200,11); 
radius = zeros(1,200);centre = zeros(200,3); 
x_plot = zeros(200,10); y_plot = zeros(200,10); z_plot = zeros(200,10);
x_max = 145; x_min = 5;
y_max = 145; y_min = 5;
z_max = 145; z_min = 5;
centre(1,:) = x_min + rand(1,3).*(x_max - x_min);
[radius(1),theta,beta] = aggregate(number);
theta_m(1,1) = number; beta_m(1,1) = number; 
theta_m(1,2:number+1) = theta; beta_m(1,2:number+1) = beta;% these are for saving the theta and beta matices for each aggregate
[x,y,z] = sph2cart(theta,beta,radius(1));
x_plot(1,1:number) = x + centre(1,1); y_plot(1,1:number) = y + centre(1,2);  z_plot(1,1:number) = z + centre(1,3);
[~,av]= convhull(x_plot(1,1:theta_m(1,1)), y_plot(1,1:theta_m(1,1)), z_plot(1,1:theta_m(1,1)));
volume = volume + av;
%%
format long
jj= 2;
while(volume<1518570)

     
    while_outer_loop = true; while_inner_loop = true;
    while( while_outer_loop == true)
        number = randi([6 10]);
        centre(jj,:) = x_min + rand(1,3).*(x_max - x_min);
        centre_refrence = centre(jj,:);
        [radius(jj),theta,beta] = aggregate(number);
        theta_m(jj,1) = number; beta_m(jj,1) = number;
        theta_m(jj,2:number+1) = theta; beta_m(jj,2:number+1) = beta;
        [x,y,z] = sph2cart(theta,beta,radius(jj));
        x_plot(jj,1:number) = x + centre(jj,1); y_plot(jj,1:number) = y + centre(jj,2);  z_plot(jj,1:number) = z + centre(jj,3);
    
         centre_increse = centre(jj,:)+7;
         centre_decrase = centre(jj,:)-7;
        for check=1:jj-1
            checking_centre(1,:) = centre(check,:)> centre_decrase;
            checking_centre(2,:) = centre(check,:)< centre_increse;
            if all(checking_centre(:))==true
                agg_num = check;
                 while_inner_loop = false;
                 break
            end
        end
       
        while( while_inner_loop==false )
           
            for ii= 1:numel(agg_num)
                V{1}=[x_plot(agg_num(ii),1:theta_m(agg_num(ii),1)); y_plot(agg_num(ii),1:theta_m(agg_num(ii),1)); z_plot(agg_num(ii),1:theta_m(agg_num(ii),1))]';
                V{2}=[x_plot(jj,1:theta_m(jj,1)); y_plot(jj,1:theta_m(jj,1)); z_plot(jj,1:theta_m(jj,1))]';
                S=(intersectionHull('vert',V{1},'vert',V{2}));
                s=isempty(S.vert);
                while_inner_loop  = s;
                 
            end
            if (while_inner_loop==false)
                radius(jj)=radius(jj)-1;
                [x,y,z] = sph2cart(theta,beta,radius(jj));
                x_plot(jj,1:number) = x + centre(jj,1); y_plot(jj,1:number) = y + centre(jj,2);  z_plot(jj,1:number) = z + centre(jj,3);
            elseif (radius(jj<2.25))
                break
            end
            if(radius(jj)<2.25 )
                while_outer_loop = true;
                break
             end
        end
        if while_inner_loop == true
            while_outer_loop = false;
        end
        
    end 
    [~, av] = convhull(x_plot(jj,1:theta_m(jj,1)), y_plot(jj,1:theta_m(jj,1)), z_plot(jj,1:theta_m(jj,1)));
    %trisurf(k,x_plot(jj,1:theta_m(jj,1)), y_plot(jj,1:theta_m(jj,1)), z_plot(jj,1:theta_m(jj,1)))
    volume = volume+av 
    jj=jj+1
end

[Matt J]

I cannot see where, in this code, you call intersectionHull().

[CHANDRABHAN Singh]

@Matt J

I have specified piece of code using intersectionhull below. Line 58 of the code.

 for ii= 1:numel(agg_num)
                V{1}=[x_plot(agg_num(ii),1:theta_m(agg_num(ii),1)); y_plot(agg_num(ii),1:theta_m(agg_num(ii),1)); z_plot(agg_num(ii),1:theta_m(agg_num(ii),1))]';
                V{2}=[x_plot(jj,1:theta_m(jj,1)); y_plot(jj,1:theta_m(jj,1)); z_plot(jj,1:theta_m(jj,1))]';
                S=(intersectionHull('vert',V{1},'vert',V{2}));
                s=isempty(S.vert);
                while_inner_loop  = s;

Answer 2

[Bjorn Gustavsson]

You should have two file-exchange packages that solves your problem:

fast-and-robust-curve-intersections

curve-intersections

They should be able to return the intersection-points of your conv-hull curves. I don't know how they behave for peculiar edge-cases like osculating curves and potentially similar corners (and how you want to solve those considering our finite precision...)

HTH