Математика:
Вычислительная геометрия:
Работа с многоугольниками.

Найти пересечение и объединение двух выпуклых многоугольников. Многоугольники задаются координатами вершин в порядке обхода по контуру.

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

Объединение делается аналогично.

Вверх по странице, к оглавлению и навигации.