function candidates = findSubCandidates(polygon,pointIdx,edgeIdx,poly,radius,intersectionTol)
%FINDSUBCANDIDATES find polygon candidates on decomposing a polygon based
%on a vertex and an edge.
%polygon   NX2 vertices
%pointIdx  Vertex of polygon.
%edgeIdx   Edge of polygon.
%poly      polyshape with vertices as polygon.
%radius    radius of the ray extension for intersections.
%intersectionTol tolerance to snap to vertex decompositions.

%   Copyright 2022 The MathWorks, Inc.

candidates=cell.empty(0,2);
%Two directions the ray could go in. CastDirection captures the "forward" (1) and
%"backward" (-1) ray extension.
CastDirection=[-1,1];
numEdges=size(polygon,1);
udx=zeros(2,2);
udy=zeros(2,2);
for dir=1:1:2
    [xl,yl,udx(dir),udy(dir)]=uav.internal.coveragePlanner.createPolyRay(polygon,pointIdx,edgeIdx,radius,CastDirection(dir));
    [closestIntersection,validIntersection,vertexIndex,edgeIndex,isVertexIndex]=uav.internal.coveragePlanner.intersectInterface(poly,xl,yl);
    if(validIntersection)
        if(~isVertexIndex)
            %Intersection on an edge.
            [edgePolygons,isValidSplit]= uav.internal.coveragePlanner.splitPolygonByEdge(polygon(pointIdx,:),closestIntersection,edgeIndex,polygon);
            if(isValidSplit)
                candidates{end+1,1}=edgePolygons{1}; %#ok
                candidates{end,2}=edgePolygons{2};
            end
        elseif(isVertexIndex)
            %Intersection on a vertex.
            [prev,next] = uav.internal.coveragePlanner.findNeighbor(pointIdx,numEdges);
            isNotNeighbour=(prev~=vertexIndex)&&(next~=vertexIndex);
            %Split polygon by a vertex.
            if(isNotNeighbour)
                [vertexPolygons,isValidSplit]=uav.internal.coveragePlanner.splitPolygonByVertex(pointIdx,edgeIndex,polygon);
                if(isValidSplit)
                    candidates{end+1,1}=vertexPolygons{1}; %#ok
                    candidates{end,2}=vertexPolygons{2};
                end
            end
        end
    end
end


%Process any vertices that can be seen and that have slope approximately
%same as the ray extensions in vertex-Edge Decomposition. This helps catch
%solutions that are optimal but missed  in the previous step due to slight displacement in
%vertices.

%Optimization. Skip canSee checks to boost performance when intersectionTol
%is 0.
if(intersectionTol~=0)
    start=polygon(pointIdx,:);
    for dir=1:1:2
        for j=1:1:length(polygon)
            exit=polygon(j,:);
            line=exit-start;
            [sdx,sdy]=uav.internal.coveragePlanner.findNormalizedSlope(line(1),line(2));
            %If a point can be approximately seen by the polyRay and its slope matches within IntersectionTol.
            %Then try a decomposition there as well.
            if (pointIdx~=j)&&(uav.internal.coveragePlanner.canSee(pointIdx,j,polygon))&&(norm([sdx,sdy]-[udx(dir),udy(dir)],1)<intersectionTol)
                [vertexPolygons,isValidSplit]=uav.internal.coveragePlanner.splitPolygonByVertex(pointIdx,j,polygon);
            else
                isValidSplit=false;
            end
            if(isValidSplit)
                candidates{end+1,1}=vertexPolygons{1}; %#ok
                candidates{end,2}=vertexPolygons{2};
            end
        end
    end
end
end

