Складывание выбора точек на 3D-кубе

Question

Я пытаюсь найти эффективный алгоритм для следующей задачи 3D Cube Selection:

Представьте двумерный массив точек (давайте сделаем его квадрат размером x размер) и назовем его стороной.

Для простоты вычислений давайте объявим max как размер-1. Создайте куб с шестью сторонами, сохраняя 0,0 в левой нижней части и max,max в правом верхнем углу. Используя z, чтобы отследить сторону, расположен один куб, y вверх и x справа

public class Point3D {
    public int x,y,z;

    public Point3D(){}
    public Point3D(int X, int Y, int Z) {
        x = X;
        y = Y;
        z = Z;
    }
}

Point3D[,,] CreateCube(int size)
{
    Point3D[,,] Cube = new Point3D[6, size, size];
    for(int z=0;z<6;z++)
    {           
        for(int y=0;y<size;y++)
        {
            for(int x=0;x<size;x++)
            {
                Cube[z,y,x] = new Point3D(x,y,z);
            }
        }
    }
    return Cube;
}

Теперь, чтобы выбрать случайную единственную точку, мы можем просто использовать три случайных числа, такие что:

Point3D point = new Point(
Random(0,size), // 0 and max
Random(0,size), // 0 and max
Random(0,6));   // 0 and 5

Чтобы выбрать плюс, мы могли бы определить, будет ли данное направление соответствовать текущей стороне. В противном случае мы находим куб, расположенный на стороне, касающейся центральной точки.

Использование 4 функций с чем-то вроде:

private T GetUpFrom<T>(T[,,] dataSet, Point3D point) where T : class {
    if(point.y < max)
        return dataSet[point.z, point.y + 1, point.x];
    else {
        switch(point.z) {
            case 0: return dataSet[1, point.x, max];      // x+
            case 1: return dataSet[5, max, max - point.x];// y+
            case 2: return dataSet[1, 0, point.x];        // z+
            case 3: return dataSet[1, max - point.x, 0];  // x-
            case 4: return dataSet[2, max, point.x];      // y-
            case 5: return dataSet[1, max, max - point.x];// z-
        }
    }
    return null;
}

Теперь я хотел бы найти способ выбора произвольных форм (например, предопределенных случайных объектов) в произвольной точке. Но согласился бы приспособить его к квадратному или зазубренному кругу.

Фактическая площадь поверхности будет искривляться и складываться на углы, что хорошо и не требует компенсации (представьте, что наклейка наклейка на угол куба, если угол совпадает с центром наклейки, потребуется четверть наклейки). быть удаленным для этого, чтобы придерживаться и свернуться на углу). Опять же, это желаемый эффект.

Дублирование не допускается, поэтому кубы, которые будут выбраны дважды, необходимо как-то отфильтровать (или рассчитать так, чтобы дублирования не возникало). Что может быть простым, например использование HashSet или List и использование вспомогательной функции для проверки уникальности записи (что хорошо, так как выбор всегда будет намного ниже 1000 кубов максимум).

Делегат для этой функции в классе, содержащем Стороны Куба, выглядит следующим образом: делегат T[] SelectShape(Point3D point, int size);

В настоящее время я думаю о проверке каждой стороны куба, чтобы увидеть, какая часть выделения находится на этой стороне.

Вычисление того, какая часть выделения находится на той же стороне выбранного Point3D, будет тривиальным, поскольку нам не нужно переводить позиции, только границу. Далее будет 5 переводов с последующей проверкой 5 других сторон, чтобы увидеть, находится ли часть выбранной области на этой стороне.

Я становлюсь ржавым в решении подобных проблем, поэтому мне было интересно, есть ли у кого-нибудь лучшее решение для этой проблемы.

@arghbleargh запросил дополнительное объяснение:

Мы будем использовать куб с 6 сторонами и использовать размер 16. Каждая сторона имеет 16x16 точек. Сохраненный в виде трехмерного массива, я использовал z для стороны, y, x так, чтобы массив начинался с: new Point3D[z, y, x], он работал бы почти одинаково для зубчатых массивов, которые по умолчанию сериализуемы (поэтому это тоже было бы неплохо) [z][y][x], но потребовало бы отдельной инициализации каждого подмассива.

Давайте выберем квадрат размером 5х5 с центром в выбранной точке. Чтобы найти такой квадратный вычитание 5x5 и добавить 2 к рассматриваемой оси: от x-2 до x+2 и от y-2 до y+2.

Произвольно выбираем сторону, мы выбираем точку z = 0 (сторона куба x +), y = 6, x = 6.

И 6-2, и 6+2 находятся в пределах 16х16 массива стороны и их легко выбрать.

Смещение точки выбора на x=0 и y = 6, однако, оказалось бы немного более сложным. Поскольку x - 2, потребуется поиск стороны слева от выбранной нами стороны. К счастью, мы выбрали сторону 0 или x+, потому что, пока мы не находимся сверху или снизу и не переходим к верхней или нижней части куба, все оси имеют форму x+ = вправо, y+ = вверх. Таким образом, чтобы получить координаты на стороне слева, потребуется только вычитание max (размер - 1) - x. Запомните size = 16, max = 15, x = 0-2 = -2, max - x = 13. Таким образом, подраздел на этой стороне будет x = 13-15, y = 4-8. Добавив это к части, которую мы мог выбрать на оригинальной стороне дал бы весь выбор.

Сдвиг выделения на 0,6 оказался бы более сложным, так как теперь мы не можем прятаться за безопасностью, зная, что все оси легко выровнены. Некоторое вращение может потребоваться. Есть только 4 возможных перевода, так что все еще можно управлять.

Переход на 0,0 - вот где проблемы действительно начинают появляться. Как теперь и левый, и нижний требуют обтекания на другие стороны. Более того, так как даже у подразделенной части будет область вне. Единственная мазь на этой ране в том, что мы не заботимся о перекрывающихся частях выбора. Поэтому мы можем либо пропустить их, когда это возможно, либо отфильтровать их по результатам позже.

Теперь, когда мы переходим со стороны "нормальной оси" на нижнюю, нам нужно будет повернуть и сопоставить правильные координаты, чтобы точки правильно обернулись вокруг края.

Поскольку оси каждой стороны сложены в кубе, может потребоваться перевернуть или повернуть некоторую ось, чтобы выбрать правильные точки.

Остается вопрос, если есть лучшие решения для выбора всех точек на кубе, которые находятся внутри области. Возможно, я мог бы дать каждой стороне матрицу перевода и проверить координаты в мировом пространстве?

Answer 1

Нашли довольно хорошее решение, которое не требует особых усилий для реализации.

Создайте хранилище для полого куба размером n + 2, где n - это размер куба, содержащегося в данных. Это удовлетворяет: стороны соприкасаются, но не пересекаются и не разделяют определенные моменты.

Это упростит вычисления и переводы, создав массив поиска, который использует декартовы координаты. С помощью одной функции перевода, чтобы получить координаты выбранной точки, получить "мировую позицию".

Используя эту функцию, мы можем сохранить каждую точку в декартовом массиве поиска.

При выборе точки мы можем снова использовать ту же функцию (или использовать сохраненные данные) и вычесть (чтобы получить AA или минимальную позицию) и добавить (чтобы получить BB или максимальную позицию).

Затем мы можем просто найти каждую запись между координатами AA.xyz и BB.xyz. Каждая пустая запись должна быть пропущена.

Оптимизируйте, если требуется, используя тип массива, который возвращает нуль, если z не равно 0 или размеру 1, и, следовательно, не нужно хранить нулевые ссылки на "полый куб" в середине.

Теперь, когда куб может выбирать трехмерные кубы, другие фигуры являются тривиальными, учитывая трехмерную точку, определяют трехмерную фигуру и проверяют каждую часть в форме с помощью массива поиска, если не равен нулю, добавьте его в выборку. Каждая точка выбирается только один раз, поскольку мы проверяем каждую позицию только один раз.

Немного затрат на вычисления из-за тестирования на пустое внутри и снаружи куба, но доступ к массиву настолько быстр, что это решение подходит для моего текущего проекта.