Вычисление разности Минковского для кругов и выпуклых многоугольников

Мне нужно реализовать функцию суммы Минковского, которая может вернуть сумму Минковского либо из двух кругов, либо из двух выпуклых многоугольников, либо из круга, и из выпуклого многоугольника. Я нашел этот поток, который объяснил, как это сделать для выпуклых полигонов, но я не уверен, как это сделать для круга и многоугольника. Кроме того, как бы я даже представлял ответ?! Я бы хотел, чтобы алгоритм работал в O (n) времени, но попрошайки не могут быть выборами.

1 ответ

Круг тривиален - просто добавьте центральные точки и добавьте радиусы. Circle + ConvexPoly почти так же прост: переместите каждый отрезок перпендикулярно наружу радиусом окружности и соедините смежные сегменты с круговыми дугами, центрированными в исходных поли вершинах. Переведите всю точку центра круга.

Что касается того, как вы представляете ответ: ну, это зависит от того, что вы хотите с ним делать. Вы можете преобразовать его в NURBS, если хотите просто нарисовать его с помощью библиотеки векторного рисования. Вы можете аппроксимировать круговые дуги полилиниями, если вы просто хотите использовать многоугольное приближение. Или вы можете сохранить его как есть - "этот многоугольник, расширенный таким-то радиусом". Это был бы лучший выбор для таких вещей, как raycasting, например. Или как компромисс, вы можете связать смежные сегменты линейно, а не с круговыми дугами, и сохранить его как объединение (нового) выпуклого многоугольника и список окружностей в вершинах.

О, о ConvexPoly + ConvexPoly. Это самый хитрый, но все же простой. Основная идея заключается в том, что вы берете список сегментных векторов для каждого многоугольника (начиная с какой-то определенной экстремальной точки, как точка на каждом поли с наименьшей координатой X), а затем объединяют два списка вместе, сохраняя его отсортированным по углу. Суммируйте две точки, с которых вы начали, затем примените каждый вектор из объединенного списка векторов для создания других точек.

licensed under cc by-sa 3.0 with attribution.