Построить 4 нормальные прямые в пространстве от центра фигуры

#c_sharp #unity3d #вычислительная_геометрия

Здравствуйте!
Собственно, реализую редактор поверхностей, основная проблема встала с расчётом "габаритов"
кисточки, а точнее, поверхности в пространстве, попадающей под эту самую кисточку.



Привожу максимально урезанный рабочий код сего действа:

using System;
using System.Collections.Generic;
using UnityEngine;
using UnityEditor;

namespace EngineEditor.Terrain {

    /// 

    /// Режим редактирования
    /// 
    public enum EEditorMode : int {
        ModeAdd    = 0x00, // режим добавления
        ModeDelete = 0x01, // режим удаления
        ModePick   = 0x02  // режим захвата
    };

    public class Test : EditorWindow {

        private static Color designAddColor = new Color(0.15f, 1.0f, 0.15f);
        private static Color textColor      = new Color(0.9f, 0.9f, 0.9f);
        private static float brushSize      = 1.1f;

        private EEditorMode  currentMode    = EEditorMode.ModeAdd;

        private bool selectModeOn = false;

        [MenuItem("Test/Editor")]
        public static void ShowWindow() {
            EditorWindow window = EditorWindow.GetWindow(typeof(Test));
            window.titleContent = new GUIContent("...");
        }

        void OnGUI() {

        }

        void OnFocus() {
            SceneView.onSceneGUIDelegate -= this.OnSceneGUI;
            SceneView.onSceneGUIDelegate += this.OnSceneGUI;
        }

        void OnDestroy() {
            SceneView.onSceneGUIDelegate -= this.OnSceneGUI;
        }

        /// 

        /// Метод обрабатывающий задобренный объект
        /// 
        /// 
        /// Объект, до которого дотронулись лучи добра
        private void OnRaycast(SceneView sceneView, RaycastHit hitInfo) {

            Collider collider   = hitInfo.collider;
            Vector3 cameraPoint = sceneView.camera.transform.position + sceneView.camera.transform.forward
+ sceneView.camera.transform.right;
            Quaternion startRot = Quaternion.LookRotation(hitInfo.normal);


            switch (currentMode) {
                case EEditorMode.ModeAdd:
                    Handles.color = designAddColor;
                    break;
            }

            Handles.DrawLine(hitInfo.point, cameraPoint);

                // рисуем кисточку
            Handles.CircleCap(0, hitInfo.point, startRot, brushSize);

            Handles.color = textColor;

            Handles.Label(collider.transform.position, new GUIContent(Utils.ToString(collider.transform.position)),
EditorStyles.boldLabel);
            Handles.Label(hitInfo.point, new GUIContent("\n"+Utils.ToString(hitInfo.normal)+"\n"+Utils.ToString(hitInfo.barycentricCoordinate)));
            Handles.Label(hitInfo.point, Utils.ToString(startRot));

            sceneView.Repaint();
        }

        /// 

        /// Отрисовка в окне сцены
        /// 
        /// 
        public void OnSceneGUI(SceneView sceneView) {

            Selection.activeObject = null;

            Vector3 mousePosition = new Vector3(Event.current.mousePosition.x, sceneView.camera.pixelHeight
- Event.current.mousePosition.y, 0);
            RaycastHit hitInfo = new RaycastHit();
            Ray ray = sceneView.camera.ScreenPointToRay(mousePosition); // генерируем
луч добра

            if (Physics.Raycast(ray, out hitInfo)) // одобряем всё и вся нашим лучом
                OnRaycast(sceneView, hitInfo);

        }


    }

}


Покажу схематично саму кисточку:


Собственно, что я знаю:


Известна середина фигуры point{x,y,z}
Известны углы этой фигуры rect{x,y,z} и вращение quaternion{x,y,z,w}
Известен размер кисти (в данном случае - сторона квадрата)


Сам вопрос:


Каким образом я могу вычислить координаты v1,v2,v3,v4, чтобы провести линии


от point до v1,
от point до v2,
от point до v3,
от point до v4?



Если получится их вычислить, решиться проблема с обнаружением поверхности под кисточкой
(обычными вычитаниями).

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

Ответы

Ответ 1

VladD


  Хм. А почему не так: вектор MV1 = quaternion * (-d/2, 0, 0), отсюда V1
  = M + MV1 (M — центр, d — сторона). –  VladD 4 мин. назад


Дал самое простое и понятное решение! Огромное спасибо, я просто не знал что в unity
перегружены операции кватернионов с векторами (facepalm), пинать меня за это надо.

Ещё раз Спасибо!

Вычисление координат в матрице

#c_sharp #алгоритм #математика #геометрия #вычислительная_геометрия

Есть 5x5 матрица квадратов в произвольной части экрана. Как найти координаты (x,
y) в центре каждого квадрата?


    

Ответы

Ответ 1

координатные оси вправо и вниз

l, t, r, b = координаты матрицы
s = ширина разделительной линии (отступы по краям ей тоже равны)
n, m = количество прямоугольников по вертикали и горизонтали

w = (r-l - s * (m+1)) / m
h = (t-b - s * (n+1)) / n

x0 = l + s + w / 2
y0 = t + s + h / 2

i, j = номера строки и столбца в 0-индексации

x = x0 + (w+s)*i
y = y0 + (h+s)*j


PS: Если значения (даже промежуточные) дробные, то при реализации алгоритма имеет
смысл сделать всё одной формулой, чтобы умножение что до деления.

PPS: Если отступов по краям нет, то вместо +1 надо использовать -1.

Структура данных для упорядочения двумерных точек

#cpp #алгоритм #вычислительная_геометрия

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

Подскажите, какую структуру данных использовать, чтоб не перебирать все точки подряд.
Не могу даже сообразить, как правильно проГУГЛяться, что именно искать - как запрос
сформулировать.

Рабочий язык - С++.
    

Ответы

Ответ 1

Можно разбить плоскость на квадраты размера L. Для каждого квадрата сохраняем список
попавших в него точек. Для новой точки находим ее квадрат и перебираем содержимое этого,
а также соседних квадратов. Как это сделать эффективно по памяти описано, например,
здесь: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.2471&rep=rep1&type=pdf


Ответ 2

Если задача массовая, т.е. если исходный набор точек стабилен и к этому стабильному
набору точек делается относительно большое количество запросов, то хороший вариант:
евклидова диаграмма Вороного для исходного набора плюс какой-нибудь алгоритм для быстрого
point-location.

Когда на вход приходит точка-запрос, то мы выполняем point-location, чтобы определить,
в какой регион диаграммы Вороного попала точка-запрос. После этого рассматриваем этот
регион Вороного и обходим поиском ширину соседние регионы Вороного до тех пор, пока
мы заведомо не выйдем за радиус L.

Понятное дело, что построение диаграммы Вороного и подготовка к point-location -
это относительно "тяжелый" препроцессинг, по каковой причине, как я сказал выше, такой
подход имеет смысл при стабильном входном наборе и относительно большом количестве
запросов к нему, т.е. когда результаты препроцессинга сохраняют свою актуальность "долго".

Другой вариант - k-d-tree.

Подсчитать число пересечений прямоугольников (кубов)

#массивы #алгоритм #сортировка #геометрия #вычислительная_геометрия

Для простоты будем рассматривать задачу про прямоугольники (для кубов -- аналогично).

Задача состоит в том, чтобы подсчитать суммарную площадь пересечений прямоугольников
(или любую другую аддитивную функцию от площади пересечений), которые ориентированы
по осям стандартной системы координат (СК). Кажется, что задача решается быстрее чем
брутфорсом, т.е. быстрее, чем за O(n2). 

Решение можно построить так:


Переберём все упорядоченные пары прямоугольников (их C2n).
Для каждой пары посчитаем площадь пересечений.


Предложим решение задачи для случая двух прямоугольников. 



Будем обозначать проекции точек на оси как Ax, Bx, Cx, Dx, Ay, By... и т.д.

Тогда, запишем все проекции и отсортируем их согласно возрастанию значению координат.
Чтобы не дублировать координаты, для оси X будем брать только точки A, B, E, F:

Ax, Ex, Bx, Fx

Для оси y соответственно:

Hy, Dy, Ey, Ay

Заведём сет и будем поочередно класть точки в него. Если одновременно в сете есть
две точки одного и того же прямоугольника, то удалим их. Если одновременно в сете есть
точки различных прямоугольников по каждой из координат, то фиксируем пересечение.

Пример. 


Sx = {} // Сет Sx -- по оси х
Sy = {} // Сет Sy -- по оси y
Добавим в сет первые точки по каждой из координат: 
Sx = {Ax}, Sy = {Hy}
Добавим ещё по одной точке:
Sx = {Ax, Ex}, Sy = {Hy, Dy}. Фиксируем пересечение
Sx = {Ax, Ex, Bx}, Sy = {Hy, Dy, Ey}. Вычисляем значение пересечения:
(Bx - Ax) * (Hy - Ey)
Удаляем точки из сетов: Sx = {Ex}, Sy = {Dy}
Добавляем точки в сеты: Sx = {Ex, Fx}, Sy = {Dy, Ay}
Удаляем точки одинаковых прямоугольников: Sx = {}, Sy = {}


Вопросы: 


Будет ли работать подобный алгоритм для 3 измерений?
Помогите обобщить его на случай n прямоугольнков (кубов). Никак не соображу.


Для случая двойных пересечений требует вычислить суммарную площадь. Пусть есть 3
прямоугольника ABCD, EFGH, IJKL. Требуется вычислить либо площадь S(INMO) + S(EOPQ)
+ S(OSKL), либо S(INMO) + 2S(EOPQ) + S(OSKL), в зависимости от того, что проще посчитать.



Замечание

Для случая двух прямоугольников (кубов) задача решается легко. Пусть у нас заданы
прямоугольники как левые нижние углы и размеры их сторон:

x0, y0, z0, dx, dy, dz


Тогда посмотрим, какой из прямоугольников лежит правее по каждой оси. Затем проверим
условия пересечений и вычислим площадь. Напишем код (на golang):

type Box struct {
    dx, dy, dz int
    x, y, z    int
}

func (c *Box) isLineIntersection(p00, p01, p10, p11 int) int {
    if p00 > p10 {
        p00, p01, p10, p11 = p10, p11, p00, p01
    }
    if (p10 >= p01) && (p01 <= p11) {
        return p01 - p10
    } else if (p10 <= p01) && (p11 <= p01) {
        return p11 - p10
    }
    return 0
}


func (c *Box) isIntersection(box1 Box, box2 Box) (intersection int) {
    dx := c.isLineIntersection(box1.x, box1.x+box1.dx, box2.x, box2.x+box2.dx)
    dy := c.isLineIntersection(box1.y, box1.y+box1.dy, box2.y, box2.y+box2.dy)
    dz := c.isLineIntersection(box1.z, box1.z+box1.dz, box2.z, box2.z+box2.dz)
    return dx * dy * dz
}

    

Ответы

Ответ 1

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

В "простейшем" применении этого подхода: 

Мы представляем каждый из наших прямоугольников парой вертикальных ребер: левым и
правым ребром. Эти ребра мы будем рассматривать в лексикографическом порядке, отсортированными
по нижнему Y, а затем - по X.

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

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

Для каждого уровня сканирования мы анализируем покрытие плоскости непосредственно
над сканирующей прямой.

Просматривая список активных ребер слева-направо, мы легко узнаем, на каком вертикальном
ребре X1 начинается множественное покрытие "территории" прямоугольниками и на каком
ребре X2 оно заканчивается. Таких пар начало-конец на каждом уровне сканирования может
быть несколько. Если следующая сканирующая прямая будет располагаться на уровне NEXT_Y,
то каждая пара X1-X2 будет добавлять в искомую площадь слагаемое (X2 - X1) * (NEXT_Y - Y). 

Просканировав снизу-вверх весь вход мы вычислим искомую площадь.



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

Вот, например, простейшая реализация этого алгоритма (С++) с входными данными взятыми
из вашей картинки с тремя прямоугольниками. Получаем именно S(INMO) + S(EOPQ) + S(OSKL),
т.е. 22

#include 
#include 
#include 
#include 

struct Edge
{
  int x, yb, yt;
  bool is_left;
};

struct Rect
{
  int xl, yb, xr, yt;
};

int main()
{
  const std::vector rects = 
  {
    { 0, 6, 5, 11 },
    { 3, 4, 7, 10 },
    { 2, 0, 9, 8 }
  };

  using Edges = std::vector; 
  Edges edges;
  for (const Rect &r : rects)
  {
    edges.push_back({ r.xl, r.yb, r.yt, true });
    edges.push_back({ r.xr, r.yb, r.yt, false });
  }

  std::sort(edges.begin(), edges.end(), 
    [](const Edge &lhs, const Edge &rhs) { return lhs.yb != rhs.yb ? lhs.yb < rhs.yb
: lhs.x < rhs.x; });

  unsigned area = 0;

  auto less_x = [](const Edge &lhs, const Edge &rhs) { return lhs.x < rhs.x; };
  using SweepLine = std::set;
  SweepLine sweep_line(less_x);

  Edges::const_iterator it_e = edges.begin();
  for (int sweep_y = it_e->yb, next_sweep_y; sweep_y != std::numeric_limits::max();
sweep_y = next_sweep_y)
  {
    for (; it_e != edges.end() && it_e->yb == sweep_y; ++it_e)  
      sweep_line.insert(*it_e);

    next_sweep_y = it_e != edges.end() ? it_e->yb : std::numeric_limits::max();

    int prev_x;
    unsigned inside_counter = 0;
    unsigned covered_x = 0;

    for (SweepLine::iterator it_swe = sweep_line.begin(); it_swe != sweep_line.end(); )
    {
      if (it_swe->yt == sweep_y)
      {
        it_swe = sweep_line.erase(it_swe);
        continue;
      }

      next_sweep_y = std::min(next_sweep_y, it_swe->yt);

      unsigned prev_inside_counter = inside_counter;
      inside_counter += it_swe->is_left ? +1 : -1;

      if (prev_inside_counter == 1 && inside_counter == 2)
        prev_x = it_swe->x;
      else if (prev_inside_counter == 2 && inside_counter == 1)
        covered_x += it_swe->x - prev_x;

      ++it_swe;
    }

    area += covered_x * (next_sweep_y - sweep_y);
  }

  std::cout << area << std::endl;
}


http://coliru.stacked-crooked.com/a/bb0023433d9395be

Элементарной модификацией условия во внутреннем if можно заставить эту реализацию
вычислять площадь объединения прямоугольников

if (prev_inside_counter == 0 && inside_counter == 1)
  prev_x = it_swe->x;
else if (prev_inside_counter == 1 && inside_counter == 0)
  covered_x += it_swe->x - prev_x;


площадь как минимум тройного пересечения 

if (prev_inside_counter == 2 && inside_counter == 3)
  prev_x = it_swe->x;
else if (prev_inside_counter == 3 && inside_counter == 2)
  covered_x += it_swe->x - prev_x;


площадь строго двойного пересечения

if (prev_inside_counter != 2 && inside_counter == 2)
  prev_x = it_swe->x;
else if (prev_inside_counter == 2 && inside_counter != 2)
  covered_x += it_swe->x - prev_x;


площадь, покрытая нечетным количеством прямоугольников

if ((prev_inside_counter % 2) == 0 && (inside_counter % 2) != 0)
  prev_x = it_swe->x;
else if ((prev_inside_counter % 2) != 0 && (inside_counter % 2) == 0)
  covered_x += it_swe->x - prev_x;


и т.д. и т.п.

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


Ответ 2

Вижу так. Суммируем общую площадь. По - очереди добавляем объект к сумме. Сумма это
список обыкновенных прямоугольников (кубов). Например сумма это пока один прямоугольник.
К нему добавляется ещё один. Следующая сумма это будет ТРИ прямоугольника. (Ⅰ + Ⅱ + Ⅲ).


Дальше берём из списка ещё один (третий). И пересекаем с этими тремя. В сложном случае
в сумме будет уже много прямоугольников. К линейности никак задача не сводится. Думайте,
господа присяжные заседатели....


Кубический вариант.
Берётся список координат X всех кубов. Записывается в список X-ов (LZ). Все Y в список
Y-ов(LY). Все Z координаты в список Z-ов(LZ). Сортируются эти три списка (X,Y,Z). Создаётся
кубовый массив с элементами int размера Size(LX)xSize(LY)xSize(LZ). Заполняется пока
0. Это будем называть индексированный куб. Где элемент (i,j,k) это признак заполнености
по координатам (LX(i)..LX(i+1),LY(j)..LY(j+1),LZ(k)..LZ(k+1)). Каждый 3D-прямоугольник
должен добавить своё присутствие к индексированному кубу добавлением единицы елементам
где он свой след оставил. Общий объём считаем суммой всех объёмов индексированного
куба, где элемент больше одного (т.е. где было хотя-бы два перекрытия).

Задача о покрытии отрезка

#java #алгоритм #геометрия #вычислительная_геометрия

Задача в общем виде формулируется так: По данным n отрезкам необходимо найти множество
точек минимального размера, для которого каждый из отрезков содержит хотя бы одну из точек.

Вполне понятно, что достаточно рассматривать только правые концы каждого из отрезков,
но вот этот факт я использовать никак и не могу(
Мое решение, на данный момент, заключается вот в чем:


Я считываю эти n отрезков(сами по себе они хранятся в массиве), беру правый конец
каждого из них в отдельный массив
Далее задаю простое условие о принадлежности правого конца некоторого отрезка другим
отрезкам, которые есть; если условие выполнено - в еще одном массиве кладу в соответствующий
индекс инкремент.
В результате я получаю правые точки и то, скольким еще отрезкам они принадлежат,
однако это совсем не приближает меня к решению, ибо полученной информации недостаточно.


Помогите молодому разобраться в проблеме, как ее исправить и вообще в каком направлении
думать. Понимаю, что решение детское привел, но надеюсь на help)
при необходимости, код добавлю=) 

    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();


        int[] array = new int[2 * n];
        ArrayList right_bounds = new ArrayList();


        for (int i = 0; i < array.length; i += 2) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            right_bounds.add(b);
            array[i] = a;
            array[i + 1] = b;
        }
        int[] right_bounds_count = new int[right_bounds.size()];
        Arrays.fill(right_bounds_count, 0);
        for (int i = 0; i < array.length; i += 2) {
            for (int j = 0; j < right_bounds.size(); j++) {
                if (right_bounds.get(j) >= array[i] && right_bounds.get(j) <= array[i
+ 1])
                    right_bounds_count[j]++;
            }
        }    

    }

    

Ответы

Ответ 1

Вот решение:

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] data = new int[n][];
        int i = 0;
        while (scanner.hasNext()) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            data[i++] = new int[]{a,b};
        }
        Arrays.sort(data,(o1, o2) -> {
            int v = o1[1] - o2[1];
            return v != 0 ? v : o1[0] - o2[0];
        });
        //System.out.println(Arrays.deepToString(data));
        String[] res = cover(data);
        System.out.println(res.length);
        for (int j = 0; j < res.length; j++) {
            System.out.print(res[j] + " ");
        }
    }

    public static String[] cover(int[][] arr){
        StringBuilder sb = new StringBuilder();
        for (int i = 0, l = arr.length; i < l ; i++ ) {
            int point = arr[i][1];
            for (int j = i ; j < l && point <= arr[j][1] && point >= arr[j][0] ; j++) {
                i = j;
            }
            sb.append(point).append(" ");

        }
        return sb.toString().split(" ");
    }


Возьмём все точки-концы отрезков (как левые, так и правые) и отсортируем их. При
этом для каждой точки сохраним вместе с ней номер отрезка, а также то, каким концом
его она является (левым или правым). Кроме того, отсортируем точки таким образом, что,
если есть несколько точек с одной координатой, то сначала будут идти левые концы, и
только потом - правые. Заведём стек, в котором будут храниться номера отрезков, рассматриваемых
в данный момент; изначально стек пуст. Будем двигаться по точкам в отсортированном
порядке. Если текущая точка - левый конец, то просто добавляем номер её отрезка в стек.
Если же она является правым концом, то проверяем, не был ли покрыт этот отрезок (для
этого можно просто завести массив булевых переменных). Если он уже был покрыт, то ничего
не делаем и переходим к следующей точке (забегая вперёд, мы утверждаем, что в этом
случае в стеке текущего отрезка уже нет). Если же он ещё не был покрыт, то мы добавляем
текущую точку в ответ, и теперь мы хотим отметить для всех текущих отрезков, что они
становятся покрытыми. Поскольку в стеке как раз хранятся номера непокрытых ещё отрезков,
то будем доставать из стека по одному отрезку и отмечать, что он уже покрыт, пока стек
полностью не опустеет. По окончании работы алгоритма все отрезки будут покрыты, и притом
наименьшим числом точек (повторимся, здесь важно требование, что при равенстве координат
сначала идут левые концы, и только затем правые).


Ответ 2

Брать лишь правый конец отрезка - немного не верный подход, так как так возможен
лишний учёт некоторых точек.
Тестовый пример:
[1 5]
[2 6]
[4 7]
Верный ответ здесь 1, но по вашему алгоритму, если я его верно, понял выдаст 3.
Так как нужно найти минимальное число точек, то нужно для начала заменить все отрезки
на их взаимные пересечения, если таковые есть. Если нет их, то оставить как есть. Тогда
ответом будет число таких отрезков.
Для данного примера сначала произойдёт замена [1 5] [2 6] на [2 5], затем [2 5] и
[4 7] на [4 5]. В конце остался один отрезок, поэтому правильный ответ - 1.

По-другому задачу можно интерпретировать так: имеется бесконечная доска и на ней
расположены дощечки. Сколько минимум гвоздей нужно вбить для того, чтобы ни одну из
дощечек не вытащить?

Схематическое решение

Отсортировать массив по началу отрезка, в случае совпадения по концу O(n log n)
Сравнить отрезок со следующим: если конец первого больше или равен началу второго,
то заменить эти отрезки на один, с началом, совпадающим с началом второго отрезка,
с концом, равным min(конец первого, конец второго). В противном случае ничего не менять.
Повторять для полученного ту же самую операцию со следующим и так, пока не будет достигнут
конец массива. Число оставшихся элементов массива и будет искомым числом точек. O(n)

UPD

Для нахождения искомого множества точек нужно взять по одной точке из каждого оставшегося
отрезка.


Ответ 3

Ну вот такой вариант:


Положим что два отрезка эквивалентны, если они пересекаются хотя бы в одной точке
Создадим класс отрезок и напишем соответствующий компаратор, в случае если он возвращает
0 будем пересекать наш текущий отрезок с тем которому он эквивалентен
Поочерёдно сложим всё это счастье в Set(т.е. у нас там будут лежать пересечения эквивалентных
в нашем смысле отрезков)
Пробежимся по Set'у и из каждого лежащего там отрезка возьмём по любой одной точке


Вроде должно работать(надеюсь у вас есть тесты)


Ответ 4

Если я правильно понял, речь идёт о пересечении отрезков.
Пересечением нескольких одномерных отрезков является отрезок, левый конец которого
является максимумом левых концов отрезков, а правый - минимумом правых концов.
Если полученный левый конец находится справа от полученного правого конца, результат
- пустое множество.
P.S. Поскольку "множество точек минимального размера" есть пустое множество, условие
требуется подправить.

Построить 4 нормальные прямые в пространстве от центра фигуры

Здравствуйте! Собственно, реализую редактор поверхностей, основная проблема встала с расчётом "габаритов" кисточки, а точнее, поверхности в пространстве, попадающей под эту самую кисточку.

Привожу максимально урезанный рабочий код сего действа:
using System; using System.Collections.Generic; using UnityEngine; using UnityEditor;
namespace EngineEditor.Terrain {
///

/// Режим редактирования ///

public enum EEditorMode : int { ModeAdd = 0x00, // режим добавления ModeDelete = 0x01, // режим удаления ModePick = 0x02 // режим захвата };
public class Test : EditorWindow {
private static Color designAddColor = new Color(0.15f, 1.0f, 0.15f); private static Color textColor = new Color(0.9f, 0.9f, 0.9f); private static float brushSize = 1.1f;
private EEditorMode currentMode = EEditorMode.ModeAdd;
private bool selectModeOn = false;
[MenuItem("Test/Editor")] public static void ShowWindow() { EditorWindow window = EditorWindow.GetWindow(typeof(Test)); window.titleContent = new GUIContent("..."); }
void OnGUI() {
}
void OnFocus() { SceneView.onSceneGUIDelegate -= this.OnSceneGUI; SceneView.onSceneGUIDelegate += this.OnSceneGUI; }
void OnDestroy() { SceneView.onSceneGUIDelegate -= this.OnSceneGUI; }
///

/// Метод обрабатывающий задобренный объект ///

/// /// Объект, до которого дотронулись лучи добра private void OnRaycast(SceneView sceneView, RaycastHit hitInfo) {
Collider collider = hitInfo.collider; Vector3 cameraPoint = sceneView.camera.transform.position + sceneView.camera.transform.forward + sceneView.camera.transform.right; Quaternion startRot = Quaternion.LookRotation(hitInfo.normal);
switch (currentMode) { case EEditorMode.ModeAdd: Handles.color = designAddColor; break; }
Handles.DrawLine(hitInfo.point, cameraPoint);
// рисуем кисточку Handles.CircleCap(0, hitInfo.point, startRot, brushSize);
Handles.color = textColor;
Handles.Label(collider.transform.position, new GUIContent(Utils.ToString(collider.transform.position)), EditorStyles.boldLabel); Handles.Label(hitInfo.point, new GUIContent("
"+Utils.ToString(hitInfo.normal)+"
"+Utils.ToString(hitInfo.barycentricCoordinate))); Handles.Label(hitInfo.point, Utils.ToString(startRot));
sceneView.Repaint(); }
///

/// Отрисовка в окне сцены ///

/// public void OnSceneGUI(SceneView sceneView) {
Selection.activeObject = null;
Vector3 mousePosition = new Vector3(Event.current.mousePosition.x, sceneView.camera.pixelHeight - Event.current.mousePosition.y, 0); RaycastHit hitInfo = new RaycastHit(); Ray ray = sceneView.camera.ScreenPointToRay(mousePosition); // генерируем луч добра
if (Physics.Raycast(ray, out hitInfo)) // одобряем всё и вся нашим лучом OnRaycast(sceneView, hitInfo);
}
}
}
Покажу схематично саму кисточку:
Собственно, что я знаю:
Известна середина фигуры point{x,y,z} Известны углы этой фигуры rect{x,y,z} и вращение quaternion{x,y,z,w} Известен размер кисти (в данном случае - сторона квадрата)
Сам вопрос:
Каким образом я могу вычислить координаты v1,v2,v3,v4, чтобы провести линии
от point до v1, от point до v2, от point до v3, от point до v4?
Если получится их вычислить, решиться проблема с обнаружением поверхности под кисточкой (обычными вычитаниями).
Возможно ли, что я не правильно подхожу к задаче, и данные точки можно не вычислять, а каким то чудесным образом получить единичные вектора direction из центра к каждой из этих точек?

Ответ

VladD
Хм. А почему не так: вектор MV1 = quaternion * (-d/2, 0, 0), отсюда V1 = M + MV1 (M — центр, d — сторона). – VladD 4 мин. назад
Дал самое простое и понятное решение! Огромное спасибо, я просто не знал что в unity перегружены операции кватернионов с векторами (facepalm), пинать меня за это надо.
Ещё раз Спасибо!

Структура данных для упорядочения двумерных точек

Столкнулся с задачей - имеется достаточно много (ну, скажем, десятки тысяч) точек на плоскости (возможно, позже будут в трехмерном пространстве, но пока вопрос о плоскости). Требуется много раз решать подзадачу - выбирать для итераций точки множества, находящиеся на расстоянии не более чем L от некоторой точки (вообще говоря, не входящей в это множество точек).
Подскажите, какую структуру данных использовать, чтоб не перебирать все точки подряд. Не могу даже сообразить, как правильно проГУГЛяться, что именно искать - как запрос сформулировать.
Рабочий язык - С++.

Ответ

Можно разбить плоскость на квадраты размера L. Для каждого квадрата сохраняем список попавших в него точек. Для новой точки находим ее квадрат и перебираем содержимое этого, а также соседних квадратов. Как это сделать эффективно по памяти описано, например, здесь: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.2471&rep=rep1&type=pdf

Задача о покрытии отрезка

Задача в общем виде формулируется так: По данным n отрезкам необходимо найти множество точек минимального размера, для которого каждый из отрезков содержит хотя бы одну из точек.
Вполне понятно, что достаточно рассматривать только правые концы каждого из отрезков, но вот этот факт я использовать никак и не могу( Мое решение, на данный момент, заключается вот в чем:
Я считываю эти n отрезков(сами по себе они хранятся в массиве), беру правый конец каждого из них в отдельный массив Далее задаю простое условие о принадлежности правого конца некоторого отрезка другим отрезкам, которые есть; если условие выполнено - в еще одном массиве кладу в соответствующий индекс инкремент. В результате я получаю правые точки и то, скольким еще отрезкам они принадлежат, однако это совсем не приближает меня к решению, ибо полученной информации недостаточно.
Помогите молодому разобраться в проблеме, как ее исправить и вообще в каком направлении думать. Понимаю, что решение детское привел, но надеюсь на help) при необходимости, код добавлю=)
public static void main(String [] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt();
int[] array = new int[2 * n]; ArrayList right_bounds = new ArrayList();
for (int i = 0; i < array.length; i += 2) { int a = sc.nextInt(); int b = sc.nextInt(); right_bounds.add(b); array[i] = a; array[i + 1] = b; } int[] right_bounds_count = new int[right_bounds.size()]; Arrays.fill(right_bounds_count, 0); for (int i = 0; i < array.length; i += 2) { for (int j = 0; j < right_bounds.size(); j++) { if (right_bounds.get(j) >= array[i] && right_bounds.get(j) <= array[i + 1]) right_bounds_count[j]++; } }
}

Ответ

Вот решение:
public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[][] data = new int[n][]; int i = 0; while (scanner.hasNext()) { int a = scanner.nextInt(); int b = scanner.nextInt(); data[i++] = new int[]{a,b}; } Arrays.sort(data,(o1, o2) -> { int v = o1[1] - o2[1]; return v != 0 ? v : o1[0] - o2[0]; }); //System.out.println(Arrays.deepToString(data)); String[] res = cover(data); System.out.println(res.length); for (int j = 0; j < res.length; j++) { System.out.print(res[j] + " "); } }
public static String[] cover(int[][] arr){ StringBuilder sb = new StringBuilder(); for (int i = 0, l = arr.length; i < l ; i++ ) { int point = arr[i][1]; for (int j = i ; j < l && point <= arr[j][1] && point >= arr[j][0] ; j++) { i = j; } sb.append(point).append(" ");
} return sb.toString().split(" "); }
Возьмём все точки-концы отрезков (как левые, так и правые) и отсортируем их. При этом для каждой точки сохраним вместе с ней номер отрезка, а также то, каким концом его она является (левым или правым). Кроме того, отсортируем точки таким образом, что, если есть несколько точек с одной координатой, то сначала будут идти левые концы, и только потом - правые. Заведём стек, в котором будут храниться номера отрезков, рассматриваемых в данный момент; изначально стек пуст. Будем двигаться по точкам в отсортированном порядке. Если текущая точка - левый конец, то просто добавляем номер её отрезка в стек. Если же она является правым концом, то проверяем, не был ли покрыт этот отрезок (для этого можно просто завести массив булевых переменных). Если он уже был покрыт, то ничего не делаем и переходим к следующей точке (забегая вперёд, мы утверждаем, что в этом случае в стеке текущего отрезка уже нет). Если же он ещё не был покрыт, то мы добавляем текущую точку в ответ, и теперь мы хотим отметить для всех текущих отрезков, что они становятся покрытыми. Поскольку в стеке как раз хранятся номера непокрытых ещё отрезков, то будем доставать из стека по одному отрезку и отмечать, что он уже покрыт, пока стек полностью не опустеет. По окончании работы алгоритма все отрезки будут покрыты, и притом наименьшим числом точек (повторимся, здесь важно требование, что при равенстве координат сначала идут левые концы, и только затем правые).