Вписать четырехугольник в сложную плоскость
Имеем, например, триангулированную плоскость, где расположить четырехугольник можно только в белой области, а в серой (этой серой зоны может и не быть в принципе, просто дырка в плоскости) или за пределами плоскости нельзя и есть красный четырехугольник справа:
Координаты всех вершин есть, координаты вершин каждого отдельного триангла тоже можно получить.
Далее берем рандомные точки на плоскости в белой зоне:
Далее необходимо вписать красный четырехугольник в белой зоне плоскости, не касаясь серой зоны и не выходя за пределы самой плоскости:
Вот не хватает знаний как это описать в коде, может какая формула есть или принцип. Помогите, пожалуйста.
Ответы (3 шт):
Уменьшаете рабочую зону вокруг вырезанной части и от краев плоскости по горизонтали на W/2, по вертикали на H/2, где W и H - ширина и высота прямоугольника. По сути, это использование суммы Минковского, упомянутой в комментариях Станиславом.
После этого достаточно выбрать точку, которая будет центром прямоугольника, внутри уменьшенной рабочей зоны (области, оставшиеся белыми)
Про привязку к звездочкам (рандомные точки) - не совсем ясна суть, но похоже, что вы выбираете ближайшее к звёздочке место оставшейся зоны.
Есть классическая формула проверки вхождения точки в многоугольник, но тут она даже не понадобится. Если бы белая зона была выпуклым многоугольником, надо было бы проверять вершины красного по этой формуле, а потом проверять вершины серого относительно красного. А потом еще и пересечения сторон красного и серого.
1.Проверки пересечений
Если в задаче всё - прямоугольники надо проверить только два критерия:
- вхождение всего красного прямоугольника в белый. Для этого надо убедиться, что все его координаты по x находятся между x1 и x2 белого и аналогично по y.
- Отсутствие пересечений красного с серой областью. Для этого достаточным условием будет если оба x1 и x2 красного больше чем x2 серого, или меньше x1. Либо то же самое по y.
2.Позиционирование
- Вычисляем Xmin,Xmax,Ymin,Ymax для красного центра для ограничения смещений.
- Проверяем, что x1кр>=x1бел. Если нет - смещаем на эту дельту и переходим к Y. Если тут всё нормально, проверяем, чтобы x2кр<=x2бел. Если нет - смещаем красный на дельту. Аналогично поступаем для Y.
- Проверяем на пересечение красного с серой областью. Если не пересекаются - цель достигнута.
- Если пересекаются только по X (см.п1.2), вычисляем дельту пересечения и сдвигаемся на неё. Если не вышли за границы - цель достигнута. Если вышли - пробуем в противоположном направлении. Если пересекается только по Y - поступаем аналогично.
- Если красный и серый пересекаются по двум осям, после достижения цели по X повторяем по Y и сравниваем расстояния между центрами красного и серого. Выбираем тот, что меньше.
На входе:
- размер красного
- координаты точек
- координаты отрезков наружной границы зоны
- дырки с координатами отрезков их границ
Алгоритм
Отрезки границ нужно разделить на левые (зелёный), правые (кричневый), верхние (красный) и нижние (синий).
Для каждой точки
Сначала проверяем для вертикальной оси точки, потом идём влево (3) (как на рисунке), потом вправо (4)
Для каждой правой (3) (левой 4) границы зоны (ТГ), начиная с самой правой (3) (левой 4), которая не правее (3) (левее 4), чем половина ширины красного, от точки
Сначала проверяем для горизонтальной оси точки, потом идём вниз (1), потом вверх (2)
Для каждой нижней (1) (2 верхней) границы зоны, левый (3) (4 правый) конец которой левее (3) (4 правее), чем ТГ, а правый (3) (4 левый) конец правее (3) (4 левее) левой (3) (4 правой) границы красного , начиная с самой нижней (1) (2 верхней), которая не нижее (1) (2 выше), чем половина высоты красного, от точки
Проверяем расстояние от центра красного до точки. Если оно меньше минимума, то проверяем, что красный вмещается. Если вмещается, то обновляем минимум
конец цикла
конец цикла
конец цикла
конец цикла
Фиксируем найденное положение согласно найденному минимуму расстояния
конец цикла
