Обнаружение столкновений для 2D (выпуклых) многоугольников по заданным вершинам многоугольников - PullRequest
Новая
       46

Обнаружение столкновений для 2D (выпуклых) многоугольников по заданным вершинам многоугольников

0 голосов
/ 27 декабря 2018

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

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

Здесь я предполагаю, что все случайные многоугольники являются прямоугольниками.Затем я случайным образом создаю 8 точек на каждом шаге, которые представляют вершины прямоугольника: (x1, y1, x2, y2, x3, y3, x4, y4)

Теперь, чтобы узнать:

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

Я хочу использовать алгоритм обнаружения столкновений , которая основана на теореме о разделяющей оси и объясняется здесь . 

var rand = new Random();

var numbers = new List<int>(); // A sample of one of the rectangles

numbers.Add(rand.Next(0, 100)); // x1
numbers.Add(rand.Next(0, 100)); // y1
numbers.Add(numbers[0] + rand.Next(1, 10)); //x3
numbers.Add(numbers[1] + rand.Next(1, 10)); //y3
numbers.Add(numbers[0]); // x4
numbers.Add(numbers[3]); // y4
numbers.Add(numbers[2]); // x2
numbers.Add(numbers[1]); // y2


var numbers2 = new List<int>(); // We assume that this is the given
//original polygon board

numbers2.Add(rand.Next(70, 200)); // x1
numbers2.Add(rand.Next(70, 200)); // y1
numbers2.Add(numbers2[0] + rand.Next(1, 10)); //x3
numbers2.Add(numbers2[1] + rand.Next(1, 10)); //y3
numbers2.Add(numbers2[0]); // x4
numbers2.Add(numbers2[3]); // y4
numbers2.Add(numbers2[2]); // x2
numbers2.Add(numbers2[1]); // y2

А пока давайте забудем про цикл по ранее размещенным прямоугольникам и проверку с помощьюих.Я просто хочу знать:

  1. Как я могу определить соединительную линию между каждыми двумя 2D точками (которая представляет собой сторону прямоугольника), а затем найти перпендикулярную линию к ней?(Я в консольном приложении).

    point1 = (x1, y1), point2 = (x2, y2) и так далее.Кроме того, точка 1 должна быть подключена к точке 2, точка 2 к точке 3 и т. Д., А последняя снова к точке 1.

  2. Как проецировать все точки каждой стороныкаждого прямоугольника на перпендикулярной линии?

  3. Или, если существует совершенно другой способ решения этой проблемы, который был бы проще:)

...