A medium complex frame finder, can get you any frame if a sign is attatched to it and validates the frame almost all around. Does not check if the frame has only air inside.

FrameTurtleExample.java

package me.fireinstallations;

import de.greensurivors.greenbook.utils.Utils;
import io.papermc.paper.math.BlockPosition;
import io.papermc.paper.math.Position;
import org.bukkit.Material;
import org.bukkit.World;
import org.bukkit.block.Block;
import org.bukkit.block.BlockFace;
import org.bukkit.block.Sign;
import org.bukkit.block.data.BlockData;
import org.bukkit.block.data.Directional;
import org.bukkit.block.data.Rotatable;
import org.bukkit.block.data.type.WallSign;
import org.bukkit.util.Vector;
import org.jetbrains.annotations.NotNull;
import org.jetbrains.annotations.Nullable;
import org.jetbrains.annotations.Range;

@SuppressWarnings("UnstableApiUsage")
public class FrameTurtleExample {

    /**
     * Retrieves the Frame associated with the given Sign, if any.
     *
     * @param sign the Sign to retrieve the Frame from
     * @return a Frame object representing the frame associated with the Sign, or null if no frame is found
     */
    private @Nullable Frame getFrame(@NotNull Sign sign) {
        final World world = sign.getWorld();

        switch (sign.getBlockData()) {
            case WallSign wallSign -> {// only wall signs can be attached to the frame
                final BlockPosition frameBlockPos = Position.block(sign.getBlock().getRelative(wallSign.getFacing().getOppositeFace()).getLocation());
                final BlockFace facing = wallSign.getFacing();
                final BlockFace opposite = facing.getOppositeFace();

                for (BlockFace toCheck : BlockFace.values()) {
                    if (toCheck.isCartesian() && toCheck != facing && toCheck != opposite) {
                        Frame frame = new FrameTurtle(world, frameBlockPos, opposite, toCheck).run();

                        if (frame != null) {
                            return frame;
                        }
                    }
                }
                // no frame
            }
            case Rotatable rotatable -> {
                if (Utils.isCardinal(rotatable)) {
                    final Block block = sign.getBlock();
                    final BlockFace facing = rotatable.getRotation();

                    BlockPosition frameBlockPos = Position.block(block.getRelative(BlockFace.UP).getLocation());
                    Frame frame = new FrameTurtle(world, frameBlockPos, facing, BlockFace.UP).run();

                    if (frame == null) {
                        frameBlockPos = Position.block(block.getRelative(BlockFace.DOWN).getLocation());
                        frame = new FrameTurtle(world, frameBlockPos, facing, BlockFace.DOWN).run();
                    }

                    return frame; // may be null
                } // can't work with wrong rotations
            }
            // this matches some hanging signs.
            // Note that wall signs ARE Directional too, but since the order of cases matters in pattern matching switches,
            // having a directional behind wall sign should be fine.
            case Directional directional -> {
                final Block block = sign.getBlock();
                final BlockFace facing = directional.getFacing();

                BlockPosition frameBlockPos = Position.block(block.getRelative(BlockFace.UP).getLocation());
                Frame frame = new FrameTurtle(world, frameBlockPos, facing, BlockFace.UP).run();

                if (frame == null) {
                    frameBlockPos = Position.block(block.getRelative(BlockFace.DOWN).getLocation());
                    frame = new FrameTurtle(world, frameBlockPos, facing, BlockFace.DOWN).run();
                }

                return frame; // may be null
            }
            default -> plugin.getComponentLogger().warn("Got a sign that isn't a Rotatable nor a Directional. Seems like the plugin version was not written for this Minecraft version.");
        } // end switch

        return null;
    }


    private class FrameTurtle { // todo I'm sure you can still clean this class up; java docs; cache everything we fetch from the config since a change from another thread will result in not defined behavior
        private final @NotNull World world;
        private final @NotNull Vector rotationAxis;
        private final @NotNull Vector lengthRun = new Vector(0, 0, 0);
        private final @NotNull Vector workVector;
        private @NotNull Vector direction;
        private @NotNull Vector orthogonalDirection;
        private @Nullable FrameTurtleExample.Frame result = null;
        private @Range(from = 0, to = 4) int cornersFound = 0;
        private int lengthSinceLastCorner = 0;
        private @NotNull TurtleState state = TurtleState.STARTING;

        /**
         * @param world
         * @param startPositionOnFrame
         * @param rotationAxisFace     is looking in the direction the turtle will never turn
         * @param orthogonalFace       is looking away from the start block, in the direction the turtle will turn next
         */
        public FrameTurtle(final @NotNull World world, @NotNull BlockPosition startPositionOnFrame, final @NotNull BlockFace rotationAxisFace, final @NotNull BlockFace orthogonalFace) { // todo
            this.world = world;
            this.workVector = startPositionOnFrame.toVector();

            this.rotationAxis = rotationAxisFace.getDirection();
            this.orthogonalDirection = orthogonalFace.getDirection();
            this.direction = rotateCorrect90DEGAroundAxis(rotationAxisFace.getDirection(), orthogonalDirection);

            // check first gate block since we will look ahead of the frame blocks later
            final @NotNull Block gateBlock = world.getBlockAt(
                workVector.getBlockX() + orthogonalDirection.getBlockX(),
                workVector.getBlockY() + orthogonalDirection.getBlockY(),
                workVector.getBlockZ() + orthogonalDirection.getBlockZ());

            if (!isValidGate(gateBlock.getBlockData())) {
                // sad, died before it lived
                state = TurtleState.DEAD;
            }
        }

        public @Nullable FrameTurtleExample.Frame run() {
            while (state != TurtleState.DEAD && state != TurtleState.DONE) {
                step();
            }

            if (state == TurtleState.DONE) {
                return result;
            } else {
                return null;
            }
        }

        private boolean isValidGate(@NotNull BlockData data) { // todo make water configurable
            return data.getMaterial().isAir() || data.getMaterial() == Material.WATER || getConfig().isAllowedBlock(data);
        }

        // we don't validate the inside nor the bit left between the startPositionOnFrame and the end position since we won't enforce a perfect frame
        // and the players are free to change the frame after construction. For us do only the two Blockpostions in Frame matter, the rest is mostly
        // fluff to teach players how a gate will be expected to be.
        private @NotNull TurtleState step() {
            if (state == TurtleState.DONE || state == TurtleState.DEAD) {
                // in the life of every turtle, they can only turtle once.
                return state;
            }

            final @NotNull Block frameBlock = world.getBlockAt(workVector.getBlockX(), workVector.getBlockY(), workVector.getBlockZ());

            if (!isValidGate(frameBlock.getBlockData())) {
                // gate block is one block ahead of frame, so we can find corners
                final @NotNull Block gateBlock = world.getBlockAt(
                    workVector.getBlockX() + orthogonalDirection.getBlockX() + direction.getBlockX(),
                    workVector.getBlockY() + orthogonalDirection.getBlockY() + direction.getBlockY(),
                    workVector.getBlockZ() + orthogonalDirection.getBlockZ() + direction.getBlockZ());

                if (isValidGate(gateBlock.getBlockData())) {
                    boolean validArea;
                    switch (cornersFound) {
                        case 0 ->
                            validArea = lengthSinceLastCorner <= getConfig().getMaxArea(); // estimate just part of dimension
                        case 1 ->
                            validArea = lengthSinceLastCorner * (int) Math.abs(lengthRun.getX() + lengthRun.getY() + lengthRun.getZ()) <= getConfig().getMaxArea(); // estimate with one dimension and a part of
                        case 2 ->
                            validArea = lengthSinceLastCorner * (int) Math.abs(lengthRun.getX() + lengthRun.getY() + lengthRun.getZ()) <= getConfig().getMaxArea(); // both dimensions
                        case 3 -> { // area size was already checked and did fit. Now just check we stay in the area
                            // get the recorded length of the opposite direction; sign does not matter because we will take the absolute value
                            Vector temp = lengthRun.clone().multiply(direction);

                            // +1 for the look ahead
                            validArea = lengthSinceLastCorner + 1 <= Math.abs(temp.getX() + temp.getY() + temp.getZ());
                        }
                        default -> { // should never happen
                            state = TurtleState.DEAD;
                            return state;
                        }
                    }

                    if (validArea) {
                        lengthSinceLastCorner++;

                        // prepare next step in same direction
                        workVector.add(direction);

                        //check world height
                        int newHeight = workVector.getBlockY() + orthogonalDirection.getBlockY() + direction.getBlockY();

                        state = (world.getMaxHeight() - 2) > newHeight && world.getMinHeight() < newHeight ? TurtleState.RUNNING : TurtleState.DEAD;
                    } else { // area too big

                        state = TurtleState.DEAD;
                    }

                    return state;
                } else {// reached corner
                    cornersFound++;

                    // force a step forward to get the frame around the corner
                    workVector.add(direction);

                    switch (cornersFound) {
                        case 1 -> {
                            // gone one step back to set the result corner - we are already in the frame
                            result = new Frame(Position.block(gateBlock.getLocation().add(direction.clone().multiply(-1))));

                            // this is just part of the length in this direction and is set for a rough estimation about the max area
                            lengthRun.add(direction.clone().multiply(lengthSinceLastCorner));
                            lengthSinceLastCorner = 1;

                            direction = rotateCorrect90DEGAroundAxis(direction, rotationAxis);
                            orthogonalDirection = rotateCorrect90DEGAroundAxis(orthogonalDirection, rotationAxis);

                            // another step in the new direction
                            workVector.add(direction);

                            state = TurtleState.RUNNING;
                            return state;
                        }
                        case 2 -> {
                            // remove the part between start and fist corner
                            lengthRun.multiply(orthogonalDirection);
                            lengthRun.add(direction.clone().multiply(lengthSinceLastCorner));
                            lengthSinceLastCorner = 1;

                            direction = rotateCorrect90DEGAroundAxis(direction, rotationAxis);
                            orthogonalDirection = rotateCorrect90DEGAroundAxis(orthogonalDirection, rotationAxis);

                            // another step in the new direction
                            workVector.add(direction);

                            state = TurtleState.RUNNING;
                            return state;
                        }
                        case 3 -> {
                            // replace estimation with actual length
                            if (direction.getX() != 0) {
                                lengthRun.setX(lengthSinceLastCorner);
                            } else if (direction.getY() != 0) {
                                lengthRun.setY(lengthSinceLastCorner);
                            } else {
                                lengthRun.setZ(lengthSinceLastCorner);
                            }

                            lengthSinceLastCorner = 1;
                            // go one step back to set the result
                            result.setCorner2(Position.block(gateBlock.getLocation().add(direction.clone().multiply(-1))));

                            direction = rotateCorrect90DEGAroundAxis(direction, rotationAxis);
                            orthogonalDirection = rotateCorrect90DEGAroundAxis(orthogonalDirection, rotationAxis);

                            // another step in the new direction
                            workVector.add(direction);

                            state = TurtleState.RUNNING;
                            return state;
                        }
                        case 4 -> {
                            state = TurtleState.DONE;
                            return state;
                        }
                        default -> { // should never happen
                            // if we ever get here please push the next local cow of your area over.
                            state = TurtleState.DEAD;
                            return state;
                        }
                    } // end switch
                } // end reached corner
            } else { // invalid frame
                state = TurtleState.DEAD;
                return state;
            }
        }

        /**
         * {@link Vector#rotateAroundAxis(Vector, double)} is really useless for our case of blackface precision (1 or 0 not more, not less) since it is really sloppy with its precision
         * I removed the sin/cos approximation since we always want to rotate around 90° ala pi/2 anyways.
         *
         * @param toRotate
         * @param axis
         * @return
         */
        public static Vector rotateCorrect90DEGAroundAxis(@NotNull Vector toRotate, @NotNull Vector axis) {
            double x = toRotate.getX(), y = toRotate.getY(), z = toRotate.getZ();
            double x2 = axis.getX(), y2 = axis.getY(), z2 = axis.getZ();

            double dotProduct = toRotate.dot(axis); // x * x2 + y * y2 + z * z2;

            double xPrime = x2 * dotProduct + (-z2 * y + y2 * z);
            double yPrime = y2 * dotProduct + (z2 * x - x2 * z);
            double zPrime = z2 * dotProduct + (-y2 * x + x2 * y);

            return toRotate.setX(xPrime).setY(yPrime).setZ(zPrime);
        }

        private enum TurtleState {
            STARTING,
            RUNNING,
            DONE,
            DEAD
        }
    }

    private static class Frame {
        private final @NotNull BlockPosition corner1;
        private @Nullable BlockPosition corner2;

        private Frame(@NotNull BlockPosition corner1, @NotNull BlockPosition corner2) {
            this.corner1 = corner1;
            this.corner2 = corner2;
        }

        private Frame(@NotNull BlockPosition corner1) {
            this.corner1 = corner1;
        }

        protected void setCorner2(@NotNull BlockPosition corner2) {
            this.corner2 = corner2;
        }

        public @NotNull BlockPosition corner1() {
            return corner1;
        }

        public @Nullable BlockPosition corner2() {
            return corner2;
        }

        /**
         * Calculates the area of the frame, spanned by the two corner points.
         *
         * @return the area of the rectangle, or -1 if corner2 is null.
         */
        public int getArea () {
            if (corner2 == null) {
                return -1;
            } else {
                return
                    (corner1.blockX() - corner2.blockX()) *
                    (corner1.blockY() - corner2.blockY()) *
                    (corner1.blockZ() - corner2.blockZ());
            }
        }
    }
}