Esta página se ha traducido mediante traducción automática. Haga clic aquí para ver la última versión en inglés.

boustrophedonOptions

Opciones para el algoritmo de descomposición de polígonos de bustrofedona

Desde R2025a

Descripción

El objeto boustrophedonOptions define el comportamiento de la descomposición de polígonos utilizando el algoritmo boustrophedon y le permite generar un gráfico de conectividad de celdas de polígonos después de la descomposición. Especifique este objeto en la función polygonDecomposition para realizar la descomposición utilizando el algoritmo de descomposición de bustrofedón con las opciones especificadas [1].

Creación

Sintaxis

options = boustrophedonOptions

options = boustrophedonOptions(PropertyName=Value)

Descripción

options = boustrophedonOptions genera un objeto de opciones de descomposición de polígonos con propiedades predeterminadas. Especifique este objeto en la función polygonDecomposition para realizar la descomposición utilizando el algoritmo de descomposición de bustrofedón con las opciones especificadas.

options = boustrophedonOptions(PropertyName=Value) establece una o más propiedades para options usando argumentos de nombre-valor.

Propiedades

ReturnConnectivity — La descomposición genera y devuelve un gráfico de conectividad.

true o 1 (predeterminado) | false o 0

La descomposición genera y devuelve un gráfico de conectividad, especificado como un true (1) o false (0) lógico:

• false — No generar un gráfico de conectividad.

  Nota

  Cuando ReturnConnectivity es false, las propiedades ReconnectionMethod, ConnectedCostFcn, DisconnectedCostFcn y UserData no tienen efecto.

• true — Genera un objeto navGraph que representa la conectividad entre celdas en la salida de descomposición de polígonos y devuelve navGraph en el argumento solnInfo de la función polygonDecomposition.

ReconnectionMethod — Método a utilizar para conectar grupos de polígonos no conectados

"none" (predeterminado) | "nearest" | "all"

Método para conectar grupos de clústeres de polígonos, especificado como una de estas opciones:

• "none" — No conecte grupos de polígonos no conectados.

• "nearest" — Conecta grupos de polígonos mediante el borde de distancia mínima entre los grupos de polígonos.

• "all" — Conecta cada celda dentro de un grupo de polígonos conectados con cada celda fuera de ese grupo.

• Nota

  Las opciones "nearest" y "all" utilizan la propiedad DisconnectedCostFcn para determinar la distancia y los costos de borde resultantes entre grupos de polígonos.

Para obtener más información sobre cómo funciona ReconnectionMethod, consulte Especificar opciones para la descomposición de polígonos.

ConnectedCostFcn — Función para calcular la distancia entre conjuntos de polígonos vecinos

"boustrophedonOptions.defaultConnectedCostFcn" (predeterminado) | nombre de la función

Función para calcular la distancia y los costos de los bordes entre conjuntos de polígonos vecinos, especificados como un nombre de función. Los polígonos vecinos son polígonos que comparten bordes entre sí.

Utilizando la función predeterminada "boustrophedonOptions.defaultConnectedCostFcn", el costo de conectar polígonos adyacentes es 0.

Las funciones de costo deben tener la forma:

function cost = costFcn(polySet,i,J,userData)
    arguments (Inputs)
        polySet {mustBeA(polySet,{'polyshape','nav.decomp.internal.polyshapeMgr'})}
        i (1,1) {mustBeInteger,mustBePositive}
        J (:,1) {mustBeInteger,mustBePositive}
        userData (1,1) struct %#ok<INUSA>
    end
    arguments (Outputs)
        cost (:,1)
    end
    ...
end

Para ver un ejemplo de cómo especificar ConnectedCostFcn, consulte Definir una función de costos conectada personalizada y datos de usuario.

Tipos de datos: char | string

DisconnectedCostFcn — Función para calcular la distancia entre polígonos no vecinos

"boustrophedonOptions.defaultDisconnectedCostFcn" (predeterminado) | nombre de la función

Función para calcular el costo de distancia entre conjuntos de polígonos no vecinos, especificado como un nombre de función. Los polígonos no vecinos son polígonos que no comparten un borde entre sí.

Utilizando la función predeterminada "boustrophedonOptions.defaultDisconnectedCostFcn", el costo de conectar polígonos no vecinos es la distancia entre los centroides de los polígonos.

Las funciones de costo deben tener la forma:

function cost = costFcn(polySet,i,J,userData)
    arguments (Inputs)
        polySet {mustBeA(polySet,{'polyshape','nav.decomp.internal.polyshapeMgr'})}
        i (1,1) {mustBeInteger,mustBePositive}
        J (:,1) {mustBeInteger,mustBePositive}
        userData (1,1) struct %#ok<INUSA>
    end
    arguments (Outputs)
        cost (:,1)
    end
    ...
end

Para ver un ejemplo de cómo especificar DisconnectedCostFcn, consulte Definir función de costo desconectada.

UserData — Datos para funciones de costos

struct([]) (predeterminado) | estructura

Datos para funciones de costo, especificados como una estructura. Almacene cualquier dato que necesite para las funciones de costo como campos de esta estructura.

Para ver un ejemplo de cómo especificar UserData, consulte Definir una función de costos conectada personalizada y datos de usuario.

Ejemplos

Especificar opciones para la descomposición de polígonos

Cargue un polyshape y grafíquelo.

load("exampleComplexPolyshape.mat","p")
plot(p)
title("Original Polygon")

Descomponga el polígono utilizando cada método de reconexión.

bOpts1 = boustrophedonOptions(ReconnectionMethod="nearest");
[polySet1,info1] = polygonDecomposition(p,bOpts1);
bOpts2 = boustrophedonOptions(ReconnectionMethod="none");
[polySet2,info2] = polygonDecomposition(p,bOpts2);
bOpts3 = boustrophedonOptions(ReconnectionMethod="all");
[polySet3,info3] = polygonDecomposition(p,bOpts3);

Muestre la descomposición poligonal con una superposición de gráfico de conectividad para cada método de reconexión.

plot(polySet1)
hold on
exampleHelperShowGraphConnectionsOnPolyset(polySet1,info1.Connectivity,0.5);
title("Polygon Decomposition with Connection Graph");
subtitle("ReconnectionMethod=''nearest''")
hold off

plot(polySet2)
hold on
exampleHelperShowGraphConnectionsOnPolyset(polySet2,info2.Connectivity,0.5);
title("Polygon Decomposition with Connection Graph");
subtitle("ReconnectionMethod=''none''");
hold off

plot(polySet3)
hold on
exampleHelperShowGraphConnectionsOnPolyset(polySet3,info3.Connectivity,0.5);
title("Polygon Decomposition with Connection Graph");
subtitle("ReconnectionMethod=''all''");
hold off

Esta es la función auxiliar para trazar la descomposición del polígono y superponer el gráfico de conectividad.

function gHandle = exampleHelperShowGraphConnectionsOnPolyset(polySet,connectionGraph,lineWidth)

    % Get the current axes
    ax = gca;
    ax.ColorOrderIndex = 1; % Reset the color order index

    % Overlay the connectivity graph
    gHandle = show(connectionGraph);
    gHandle.EdgeAlpha = 0.75;
    gHandle.LineWidth = lineWidth; % Set the line width for the graph edges

    % Calculate and plot the centroids
    [cx,cy] = centroid(polySet);

    % Set the xy-positions of the connectivity graph to the centroids of 
    % the polygons
    gHandle.XData = cx';
    gHandle.YData = cy';
end

Definir una función de costos conectada personalizada y datos de usuario

Cargue un polígono rectangular con múltiples agujeros como un objeto polyshape.

load("exampleRectangleWithHolesPolyshape.mat","p")

Defina una función de costo conectada que utilice datos del terreno y asigne costos a los bordes en función de la magnitud del cambio de pendiente.

function cost = terrainConnectedCostFcn(polySet,i,J,userData)
    arguments
        polySet {mustBeA(polySet,{'polyshape','nav.decomp.internal.polyshapeMgr'})}
        i (1,1) {mustBeInteger,mustBePositive}
        J (:,1) {mustBeInteger,mustBePositive}
        userData (1,1) struct
    end

    % Extract dx, dy, and the coordinate bounds from userData
    dx = userData.XSlope;
    dy = userData.YSlope;
    xBounds = userData.XBounds;
    yBounds = userData.YBounds;

    % Calculate the slope magnitude
    slope_magnitude = sqrt(dx.^2 + dy.^2);

    % Define the coordinates for the slope map based on the provided bounds
    x = linspace(xBounds(1),xBounds(2),size(slope_magnitude,1));
    y = linspace(yBounds(1),yBounds(2),size(slope_magnitude,2));

    % Initialize the cost array
    cost = zeros(size(J));

    % Calculate the average slope for the starting polyshape
    avgSlope_i = calculateAverageSlope(polySet(i),slope_magnitude,x,y);

    for idx = 1:numel(J)
        % Calculate the average slope for each target polyshape
        avgSlope_j = calculateAverageSlope(polySet(J(idx)),slope_magnitude,x,y);

        % Define a cost function that includes the average slope difference
        % For example, prioritize smaller slope differences
        cost(idx) = abs(avgSlope_i-avgSlope_j);
    end
end

function avgSlope = calculateAverageSlope(poly,slope_magnitude,x,y)
    % Find the bounding box of the polyshape
    [x_lim,y_lim] = boundingbox(poly);

    % Determine the indices in the slope map that correspond to this
    % polyshape
    x_indices = find(x >= x_lim(1) & x <= x_lim(2));
    y_indices = find(y >= y_lim(1) & y <= y_lim(2));

    % Extract the relevant portion of the slope map
    slopesInPoly = slope_magnitude(y_indices,x_indices);

    % Compute the average slope for the polyshape
    avgSlope = mean(slopesInPoly(:));
end

Defina datos personalizados para las funciones de costo a utilizar. Crea una membrana L para representar el terreno y calcula la pendiente en cada punto.

Z = membrane(1,3);
[dx,dy] = gradient(Z);

Almacene los datos de pendiente y límites en una estructura.

terrainData.XSlope = dx;
terrainData.YSlope = dy;
terrainData.XBounds = [1 8];
terrainData.YBounds = [1 8];

Cree un objeto de opciones de bustrofedón y especifique la función de costo conectada personalizada y los datos del terreno.

bOpts = boustrophedonOptions(ConnectedCostFcn="terrainConnectedCostFcn",UserData=terrainData);

Descomponga el polígono y grafique el conjunto de polígonos resultantes.

[polySet,info] = polygonDecomposition(p,bOpts);
plot(polySet)
axis equal
hold on

Superponga el gráfico de conectividad y resalte los bordes para mostrar los costos de borde entre los polígonos descompuestos. Tenga en cuenta que el pico de la membrana L está alrededor de los polígonos 8, 11 y 13, por lo que los bordes que conectan estos polígonos con los polígonos en la parte superior izquierda tienen un costo de borde mayor.

gHandle = exampleHelperShowGraphConnectionsOnPolyset(polySet,info.Connectivity,2);
exampleHelperVisualizeConnectionGraphWeights(info.Connectivity,gHandle);
title("Connection Graph with Cost Visualized")
customLinkInfo = info.Connectivity.Links

customLinkInfo=44×2 table
    EndStates     Weight 
    _________    ________

     1    2      0.090406
     1    3      0.026001
     1    4       0.27418
     2    1      0.090406
     2    5             0
     3    1      0.026001
     3    5       0.11641
     3    6       0.29335
     4    1       0.27418
     4    6       0.04517
     5    2             0
     5    3       0.11641
     5    7      0.062287
     5    8        0.4142
     6    3       0.29335
     6    4       0.04517
      ⋮

hold off

Definir función de costo desconectada

Cargar un polyshape complejo.

load exampleComplexPolyshape.mat

Defina una función de costo desconectada personalizada que priorice la reconexión de los polígonos desconectados utilizando el borde más largo posible.

function cost = longEdgeDisconnectedCostFcn(polySet,i,J,userData)
    arguments
        polySet {mustBeA(polySet,{'polyshape','nav.decomp.internal.polyshapeMgr'})}
        i (1,1) {mustBeInteger,mustBePositive}
        J (:,1) {mustBeInteger,mustBePositive}
        userData (1,1) struct %#ok<INUSA>
    end
    c1 = [0 0];
    c2 = zeros(numel(J),2);

    % Calculate the centroid of the current polygon
    [c1(1),c1(2)] = polySet(i).centroid;

    % Get the centroids of possible polygons connections
    for i = 1:numel(J)
        [c2(i,1),c2(i,2)] = polySet(J(i)).centroid;
    end

    % Calculate the centroid distances between the current polygon and
    % other polygons
    distances = vecnorm(c2-c1,2,2);

    % Calculate the inverse distance cost. Add a small number to avoid
    % division by zero
    cost = 1./(distances + 1e-6);
end

Cree un objeto de opciones de descomposición de polígonos de bustrofedona y especifique la función de costo desconectada.

bOpts = boustrophedonOptions(DisconnectedCostFcn="longEdgeDisconnectedCostFcn", ...
    ReconnectionMethod="nearest");

Descomponga el polígono y visualice la conexión gráfica.

[polySet,info] = polygonDecomposition(p,bOpts);
plot(polySet)
hold on
gHandle = exampleHelperShowGraphConnectionsOnPolyset(polySet,info.Connectivity,0.5);
info.Connectivity.Links

ans=16×2 table
    EndStates    Weight 
    _________    _______

     1    3            0
     1    6      0.26465
     1    9      0.14884
     2    3            0
     3    1            0
     3    2            0
     4    7            0
     5    7            0
     6    1      0.26465
     7    4            0
     7    5            0
     7    8            0
     7    9            0
     8    7            0
     9    1      0.14884
     9    7            0

c = colororder;

Resalte los bordes entre los conjuntos de polígonos previamente desconectados. Nótese que el polígono 6 también está desconectado, porque no comparte ningún borde aunque sus vértices están en contacto con otros bordes.

highlight(gHandle,Edges=[3 15],EdgeColor=c(2,:),LineWidth=2) % Edge from Polygon 1 to Polygon 9
highlight(gHandle,Edges=[2 9],EdgeColor=c(4,:),LineWidth=2)  % Edge from Polygon 1 to Polygon 6
title(["Long Edge Between Previously","Disconnected Sets of Polygons"])
hold off

Referencias

[1] Choset, Howie. "Coverage of Known Spaces: The Boustrophedon Cellular Decomposition." Autonomous Robots 9 no. 3, (2000): 247–53. https://doi.org/10.1023/A:1008958800904.

Capacidades ampliadas

Generación de código C/C++
Genere código C y C++ mediante MATLAB® Coder™.

Historial de versiones

Introducido en R2025a

Consulte también

polygonDecomposition | navGraph