Рассчитать площадь пересечения полигонов с помощью GPC или Clipper
У меня есть двумерная система частиц, где частицы представлены в виде эллипсов. Мне нужно вычислить эллипс — области перекрытия эллипса, но это сложная аналитическая проблема Эллипс-Эллипс Перекрытие. Теперь я представляю свои эллипсы как 20-угольники, так что они «полигонизированы», и я использую Boost.Geometry сделать необходимые расчеты.
Однако очень часто я получаю исключение от Boost.Geometry : boost.geometry overlay invalid input exception, Я искал и обнаружил, что это известная ошибка boost.Geometry и нет исправления с версии 1.53. Даже документация о готовящемся v1.54 ничего не говорит об исправлении этой проблемы.
Я наткнулся на клипер а также GPC — Общая библиотека многоугольников. Кажется, они делают то, что я хочу, но они выводят только логические результаты. Кто-нибудь знает, есть ли способ вывести площадь рассчитанных пересечений с этими библиотеками? Я предполагаю, что, поскольку пересечение хранится в памяти как некий многоугольник, я мог бы использовать триангуляцию или какой-то другой метод для вычисления площади.
Любые указатели будут по достоинству оценены!
Boost overlay Это исключение в MSVC 2010 и 2012 для Win7 x64, MinGW и Qt 4.8.1 для Linux Mint 14.
Решение
Кажется, вы ошибаетесь насчет Clipper и GPC «они только выводят логические результатыMsgstr «Обе библиотеки вычисляют полигон пересечения — например, посмотрите на фрагмент кода с изображением на странице Clipper.
Другие решения
Можете ли вы отправить билет в систему заявок Boost? Включая образец пары геометрии, дающей недопустимые входные исключения? Ошибка может иметь несколько причин: либо она действительно недействительна, либо является ошибкой в библиотеке. Некоторые из этих проблем исправлены в 1.54.
В тесте Ангуса «Клипер» с другими библиотеками у него есть метод расчета площади многоугольника. Я использовал это и изменил его метод эллипса. Результат следующий:
void Ellipse2Poly(double theta, double A1, double B1, double H1, double K1, Poly& p)
{
const double pi = 3.1415926535898, tolerance = 0.125;
const int n = 30;
double step = pi/(double)n;
double a = A1; // Long semi-axis length
double b = B1; // short semi-axis length
double xc = H1; // current X position
double yc = K1; // current Y position
double sintheta = sin(theta);
double costheta = cos(theta);
double t = 0;
p.resize(2*n+1);
for (int i = 0; i < 2*n+1; i++)
{
p[i].x = xc + a*cos(t)*costheta - b*sin(t)*sintheta;
p[i].y = yc + a*cos(t)*sintheta + b*sin(t)*costheta;
t += step;
}
}
И расчет площади:
double OverlapArea(Poly poly1, Poly poly2)
{
Poly clip;
Polys polys_poly1, polys_poly2, polys_clip;
polys_poly1.resize(1);
polys_poly2.resize(1);
polys_clip.resize(1);
polys_poly1[0] = poly1;
polys_poly2[0] = poly2;
polys_clip[0] = clip;
Polygons clipper_polys_poly1, clipper_polys_poly2, clipper_polys_clip;
LoadClipper(clipper_polys_poly1,polys_poly1);
LoadClipper(clipper_polys_poly2,polys_poly2);
ClipType op = ctIntersection;
Clipper cp;
cp.AddPolygons(clipper_polys_poly1,ptSubject);
cp.AddPolygons(clipper_polys_poly2,ptClip);
cp.Execute(op,clipper_polys_clip,pftEvenOdd,pftEvenOdd);
if(clipper_polys_clip.size() != 0)
{
UnloadClipper(polys_clip,clipper_polys_clip);
return Area(polys_clip[0]);
}
else
return 0.0;
}
Это медленнее, чем Boost.Geometry но очень стабильно Я запускаю его за 2 * 10 ^ 5 временных шагов за ночь, и он не падает. Это заняло 6 часов 12 минут, в то время как повышение — около 4 часов, но я счастлив.
РЕДАКТИРОВАТЬ:
Я переписал некоторые другие функции, поэтому сравнение с Clipper было несправедливым! Для той же конфигурации и шагов по 100 КБ Clipper завершил операцию за 2 часа 36 минут, что мне очень приятно! Boost завершил бы ту же операцию примерно через 2 часа 15 минут, поэтому я считаю, что они очень сопоставимы для этих длинных пробежек!