Как найти расстояние между многоугольниками

I doubt there is better solution than calculating the distance between the red one and every blue one and sorting these by length.

Regarding sorting, usually QuickSort is hard to beat in performance (an optimized one, that cuts off recursion if size goes below 7 items and switches to something like InsertionSort, maybe ShellSort).

Thus I guess the question is how to quickly calculate the distance between two polygons, after all you need to make this computation 50 times.

The following approach will work for 3D as well, but is probably not the fastest one:

Minimum Polygon Distance in 2D Space

The question is, are you willing to trade accuracy for speed? E.g. you can pack all polygons into bounding boxes, where the sides of the boxes are parallel to the coordinate system axes. 3D games use this approach pretty often. Therefor you need to find the maximum and minimum values for every coordinate (x, y, z) to construct the virtual bounding box. Calculating the distances of these bounding boxes is then a pretty trivial task.

Here’s an example image of more advanced bounding boxes, that are not parallel to the coordinate system axes:

Oriented Bounding Boxes — OBB

However, this makes the distance calculation less trivial. It is used for collision detection, as you don’t need to know the distance for that, you only need to know if one edge of one bounding box lies within another bounding box.

The following image shows an axes aligned bounding box:

Axes Aligned Bounding Box — AABB

OOBs are more accurate, AABBs are faster. Maybe you’d like to read this article:

Advanced Collision Detection Techniques

This is always assuming, that you are willing to trade precision for speed. If precision is more important than speed, you may need a more advanced technique.

Re[3]: Расстояние между многоугольниками

Здравствуйте, Croc, Вы писали:

C>Здравствуйте, wvk.
C>Спасибо за отклик.

wvk>>Ты не упомянул об отбрасывании по минимальному расстоянию между охватывающими прямоугольниками.

C>Да, за истекшее время я уже нашел и реализовал такой критерий. Кстати, точнее — охватывающие параллелипипеды (у меня — 3D).

Имелись в виду прямоугольники с рёбрами параллельными линии пересечения плоскостей
(если конечно плоскости не параллельны
это несколько более точный тест, но и чуть более сложный соответственно

wvk>>И тест на пересечение, я надеюсь не порёберная проверка.
C>С этого места, пожалуйста, подробнее?
C>Единственный окончательный критерий того, что они пересекаются, который я на данный момент осознал, такой: какое-либо ребро пересекает внутренность другого многоугольника. Вы знаете лучше? Подскажите, пожалуйста.

Очевидно они могут пересекаться только по линии пересечения плоскостей
несложно для каждого найти пересечение с этой линией, и сравнивать уже их.

Расстояние между многоугольниками

Здравствуйте, уважаемые эксперты.

Есть задача определения расстояния* между двумя плоскими многоугольниками в пространстве . (плоскости произвольные).
Без потери интереса к реализации можно ограничиться выпуклыми многоугольниками.
Я пока не придумал ничего лучше, чем:
1) Измерить попарно расстояние между ребер.
2) Измерить расстояние от всех вершин до другого многоугольника.
3) Проверить, не пересекают ли ребра другой многоугольник (расстояние 0).
Соответственно, наименьшее из них и будет искомым.
Есть ли какие-то принуипиально более интересные алгоритмы?

Также интересны эффективные критерии грубой нижней оценки.
То есть, если меня интересуют только близкие расстояния (<D), при этом вероятность такого события < X (например, 5 %),
то я готов сначала провернуть нечто, в дальнейшем бесполезное, если оно, например, на 20% быстрее выяснит, что расстояние заведомо больше D.

Спасибо за Ваши ссылки и идеи.

*формально, речь о наименьшем расстоянии между произвольной парой точек, принаждлежащих этим мноугольникам.

Re: Расстояние между многоугольниками

Здравствуйте, Croc, Вы писали:

<skip>

Ты не упомянул об отбрасывании по минимальному расстоянию между охватывающими прямоугольниками.
И тест на пересечение, я надеюсь не порёберная проверка.
А так, для выпуклых, наверное только полным перебором пар вершин…

Re: Расстояние между многоугольниками

Здравствуйте, Croc, Вы писали:

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

Более тонкая оценка:
— вычитаем не радиус окружности, а проекцию его на линию, проходящую через центры (для каждого прямоугольника нужно знать нормаль плоскости)

Еще более тонкая:
— переходим в (ортонормированную) систему координат, в которой OXY совпадает с плоскостью первого многоугольника
— находим проекцию второго многоугольника на эту плоскость
— находим расстояние Df между проекцией и первым многоугольником на плоскости, а также наименьшее расстояние H до плоскости
— D >= sqrt(Df^2 + H^2)
(вместо многоугольника можно рассмотреть описывающую окружность)

Re[2]: Расстояние между многоугольниками

Здравствуйте, wvk.
Спасибо за отклик.

wvk>Ты не упомянул об отбрасывании по минимальному расстоянию между охватывающими прямоугольниками.

Да, за истекшее время я уже нашел и реализовал такой критерий. Кстати, точнее — охватывающие параллелипипеды (у меня — 3D).

wvk>И тест на пересечение, я надеюсь не порёберная проверка.
С этого места, пожалуйста, подробнее?
Единственный окончательный критерий того, что они пересекаются, который я на данный момент осознал, такой: какое-либо ребро пересекает внутренность другого многоугольника. Вы знаете лучше? Подскажите, пожалуйста.
С другой стороны, я использую дополнительные проверки, которые во многих случаях «говорят», что они заведомо не пересекаются.

wvk>А так, для выпуклых, наверное только полным перебором пар вершин…
И ребер, как я уже писал.
И для невыпуклых, мне кажется, тут ничего не меняется.

Re[2]: Расстояние между многоугольниками

Здравствуйте, Кодт, спасибо за идеи:

К>Грубейшая оценка расстояния снизу:
К>- вокруг многоугольника описываем окружность (как получится);
К>- находим расстояние между центрами окружностей искомых многоугольников, вычитаем радиусы (как бы имеем дело с описывающими сферами).
К>(для нахождения описывающей окружности можно, например, взять за ее диаметр отрезок между наиболее удаленными вершинами многоугольника)

Это, все же, на порядок сложней описывающего параллелипипида, при приблизительно той же эффективности.

К>Более тонкая оценка:
К>- вычитаем не радиус окружности, а проекцию его на линию, проходящую через центры (для каждого прямоугольника нужно знать нормаль плоскости)

К>Еще более тонкая:
К>- переходим в (ортонормированную) систему координат, в которой OXY совпадает с плоскостью первого многоугольника
К>- находим проекцию второго многоугольника на эту плоскость
К>- находим расстояние Df между проекцией и первым многоугольником на плоскости, а также наименьшее расстояние H до плоскости
К>- D >= sqrt(Df^2 + H^2)
К>(вместо многоугольника можно рассмотреть описывающую окружность)

А вот это уже по выч. мощности близко к точному расчету расстояния.

Еще раз спасибо за мысли.

Re[3]: Расстояние между многоугольниками

Здравствуйте, Croc, Вы писали:

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

C>Это, все же, на порядок сложней описывающего параллелипипида, при приблизительно той же эффективности.

Я исходил из того, что если нужно находить расстояния «каждый с каждым», то можно предварительно найти центры и радиусы (O(N*V), N — число многоугольников, V — число вершин), а затем быстро-быстро…

Хотя с параллелепипедами будет быстрее… Но искать расстояние между параллелепипедами — более сложная задача; впрочем, можно сделать объединение подходов:
— центр параллелепипеда находим элементарно
— радиус = половине макс.габарита

К>>Еще более тонкая:
К>>- переходим в (ортонормированную) систему координат, в которой OXY совпадает с плоскостью первого многоугольника
К>>- находим проекцию второго многоугольника на эту плоскость
К>>- находим расстояние Df между проекцией и первым многоугольником на плоскости, а также наименьшее расстояние H до плоскости
К>>- D >= sqrt(Df^2 + H^2)
К>>(вместо многоугольника можно рассмотреть описывающую окружность)

C>А вот это уже по выч. мощности близко к точному расчету расстояния.

Но опять же, если мы для каждого многоугольника проведем предварительную работу по нахождению нормали его плоскости…

Между прочим, гарантировать что многоугольник плоский можно только для треугольников.
Ты это как-то фиксируешь?

Re[4]: Расстояние между многоугольниками

Здравствуйте, wvk, Вы писали:

wvk>>>И тест на пересечение, я надеюсь не порёберная проверка.
…
wvk>Очевидно они могут пересекаться только по линии пересечения плоскостей
wvk>несложно для каждого найти пересечение с этой линией, и сравнивать уже их.

Да, кстати, я пока все еще вожусь с невыпуклыми Пересечения получатся многосвязанные …
А сейчас я сначала проверяю, пересекает ли ребро плоскость, и если да, то тогда уже смотрю, оно внутри или снаружи.
Думаю, что вычислительно это сравнимо, хотя из обоих подходов можно сварить что-то более шустрое.

В любом случае мысль хороша, спасибо.

Re[4]: Расстояние между многоугольниками

Здравствуйте, Кодт, Вы писали:

К>Я исходил из того, что если нужно находить расстояния «каждый с каждым», то можно предварительно найти центры и радиусы (O(N*V), N — число многоугольников, V — число вершин), а затем быстро-быстро…

К>Хотя с параллелепипедами будет быстрее… Но искать расстояние между параллелепипедами — более сложная задача;

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

К>Между прочим, гарантировать что многоугольник плоский можно только для треугольников.
К>Ты это как-то фиксируешь?

Ну это уже издержки

Луогу P2742

Найти окружность выпуклой оболочки

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e4+1;
const double eps=1e-8;
struct point
{
    double x,y;
    point(){}
    point(double a,double b)
    {
        x=a;y=b;
    }
         оператор точки (const point & a) const // разность векторов
    {
        return point(x-a.x,y-a.y);
    }
         двойной оператор ^ (const point & a) const // Векторное перекрестное произведение
    {
        return x*a.y-y*a.x;
    }
         двойной оператор * (const point & a) const // Векторное произведение точек
    {
        return x*a.x+y*a.y;
    }
}p[MAX],b[MAX];
int top,n;
 двойное пересечение (точка a, точка b, точка c) // перекрестное произведение (площадь треугольника * 2
{
    return (b-a)^(c-a);
}
 double dis (точка a, точка b) // Расстояние между двумя точками sqrt (dis)
{
    return (a-b)*(a-b);
}
bool cmp(point a,point b)
{
    double tmp=cross(p[0],a,b);
    if(tmp>eps||(fabs(tmp)<eps&&dis(p[0],a)-dis(p[0],b)>eps)) return 1;
    return 0;
}
void graham()
{
    int u=0;top=0;
    for(int k=1;k<n;k++)
        if(p[u].y-p[k].y>eps||(fabs(p[u].y-p[k].y)<eps&&p[u].x-p[k].x>eps))
            u=k;
    swap(p[u],p[0]);
    sort(p+1,p+n,cmp);
    if(n>0) {b[0]=p[0];top++;}
    if(n>1) {b[1]=p[1];top++;}
    if(n<3) return ;
    for(int i=2;i<n;i++)
    {
        while(top>1&&cross(b[top-2],b[top-1],p[i])<eps) top--;
        b[top++]=p[i];
    }
}
int main()
{
    double sum=0;
    scanf("%d",&n);
    for(int k=0;k<n;k++)
        scanf("%lf%lf",&p[k].x,&p[k].y);
    graham();
    b[top]=b[0];
    for(int k=1;k<=top;k++)
        sum+=sqrt(dis(b[k],b[k-1]));
    printf("%.2fn",sum);
    return 0;
}

POJ3348 Cows

Найти площадь выпуклой оболочки

int main()
{
    double sum=0;
    scanf("%d",&n);
    for(int k=0;k<n;k++)
        scanf("%lf%lf",&p[k].x,&p[k].y);
    graham();
    for(int k=1;k<top-1;k++)
        sum + = fabs (cross (b [0], b [k], b [k + 1])); // Сумма произведений креста треугольника в выпуклой оболочке
    printf("%dn",(int)(sum/100));
    return 0;
}

POJ2187 Beauty Contest

Поверните держатель карты, чтобы найти самую дальнюю точку

double rotating()
{
    double ans=0;
    b[top]=b[0];
    for(int k=0,i=1;k<=top;k++)
    {
        while(fabs(cross(b[k],b[i+1],b[k+1]))-fabs(cross(b[k],b[i],b[k+1]))>eps)
            i=(i+1)%top;
        ans=max(ans,dis(b[i],b[k]));
    }
    return ans;
}

Поверните держатель карты, чтобы найти минимальную ширину выпуклой оболочки

double rotating()
{
    double ans=0x3f3f3f3f;
    b[top]=b[0];
    for(int k=0,i=1;k<=top;k++)
    {
        while(fabs(cross(b[k],b[i+1],b[k+1]))-fabs(cross(b[k],b[i],b[k+1]))>eps)
            i=(i+1)%top;
        ans=min(ans,fabs(cross(b[k],b[k+1],b[i])/sqrt(dis(b[k],b[k+1]))));
    }
    return ans;
}

HDU2202 самый большой треугольник

Поверните держатель карты, чтобы найти самый большой треугольник в плоскости

double rotating()
{
    double ans=0;
    for(int k=0;k<top;k++)
    {
        int i=(k+1)%top;
        int j=(i+1)%top;
        while(i!=k&&j!=k)
        {
            ans=max(ans,fabs(cross(b[k],b[i],b[j])));
            while(fabs(cross(b[k],b[i+1],b[j]))-fabs(cross(b[k],b[i],b[j]))>eps)
                i=(i+1)%top;
            j=(j+1)%top;
        }
    }
    return ans;
}

POJ3608 Bridge Across Islands

Поверните держатель карты, чтобы найти кратчайшее расстояние между двумя выпуклыми корпусами (мин) / наибольшее расстояние (макс.)

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int MAX=1e4+5;
const double eps=1e-8;
const double INF=1e99;
struct point
{
    double x,y;
    point(){}
    point(double a,double b)
    {
        x=a;y=b;
    }
         оператор точки (const point & a) const // разность векторов
    {
        return point(x-a.x,y-a.y);
    }
         двойной оператор ^ (const point & a) const // Векторное перекрестное произведение
    {
        return x*a.y-y*a.x;
    }
         двойной оператор * (const point & a) const // Векторное произведение точек
    {
        return x*a.x+y*a.y;
    }
}p[MAX],b1[MAX],b2[MAX];
int top1,top2;
double min(double a,double b)
{
    return a-b<-eps?a:b;
}
 двойное пересечение (точка a, точка b, точка c) // перекрестное произведение (площадь треугольника * 2
{
    return (b-a)^(c-a);
}
 двойное мульти (точка a, точка b, точка c) // точка произведения
{
    return (b-a)*(c-a);
}
 double dis (точка a, точка b) // Расстояние между двумя точками sqrt (dis)
{
    return (a-b)*(a-b);
}
 double dist (точка a, точка b, точка c) // Кратчайшее расстояние отрезка точечной линии a  bc
{
    point d;
    double t=multi(b,a,c)/dis(b,c);
    if(t>-eps&&t-1<eps) d=point(b.x+(c.x-b.x)*t,b.y+(c.y-b.y)*t);
    else
    {
        if(dis(a,b)-dis(a,c)<-eps) d=b;
        else d=c;
    }
    return dis(a,d);
}
 // двойное расстояние (точка a, точка b, точка c) // sqrt (dis)
//{
//    if(dis(b,c)<eps) return dis(a,c);
//    if(multi(b,c,a)<-eps) return dis(a,b);
//    if(multi(c,b,a)<-eps) return dis(a,c);
//    return fabs(cross(b,c,a)/dis(b,c));
//}
 двойное расстояние (точка a, точка b, точка c, точка d) // расстояние между двумя отрезками линии ab  cd
{
    return min(min(dist(a,c,d),dist(b,c,d)),min(dist(c,a,b),dist(d,a,b)));
}
bool cmp(point a,point b)
{
    double tmp=cross(p[0],a,b);
    if(tmp>eps||(fabs(tmp)<eps&&dis(p[0],a)-dis(p[0],b)>eps)) return 1;
    return 0;
}
void graham(point *b,int n,int &top)
{
    int u=0;top=0;
    for(int k=1;k<n;k++)
        if(p[u].y-p[k].y>eps||(fabs(p[u].y-p[k].y)<eps&&p[u].x-p[k].x>eps))
            u=k;
    swap(p[u],p[0]);
    sort(p+1,p+n,cmp);
    if(n>0) {b[0]=p[0];top++;}
    if(n>1) {b[1]=p[1];top++;}
    if(n<3) return ;
    for(int i=2;i<n;i++)
    {
        while(top>1&&cross(b[top-2],b[top-1],p[i])<eps) top--;
        b[top++]=p[i];
    }
}
double rotating(point *a,int n,point *b,int m)
{
    int i1=0,i2=0;
    for(int k=0;k<n;k++)
        if(a[k].y-a[i1].y<-eps) i1=k;
    for(int k=0;k<m;k++)
        if(b[k].y-b[i2].y>eps) i2=k;
    a[n]=a[0];b[m]=b[0];
    double tmp,ans=INF;
    for(int k=0;k<n;k++)
    {
        while((tmp=cross(a[i1+1],b[i2+1],a[i1])-cross(a[i1+1],b[i2],a[i1]))>eps)
            i2=(i2+1)%m;
        if(tmp<-eps) ans=min(ans,dist(b[i2],a[i1],a[i1+1]));
        else ans=min(ans,distence(a[i1],a[i1+1],b[i2],b[i2+1]));
        i1=(i1+1)%n;
    }
    return ans;
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m)&&(n||m))
    {
        for(int k=0;k<n;k++) scanf("%lf%lf",&p[k].x,&p[k].y);
        graham(b1,n,top1);
        for(int k=0;k<m;k++) scanf("%lf%lf",&p[k].x,&p[k].y);
        graham(b2,m,top2);
                 // Double и float могут выводиться только с% f, когда G ++ компилируется, float конвертируется в double, C ++ не влияет, обычно G ++ преобладает во время игры
        printf("%0.5fn",sqrt(min(rotating(b1,top1,b2,top2),rotating(b2,top2,b1,top1))));
    }
    return 0;
}

* Замечания по компиляции G ++ (ming32 / linux) C ++ в конкурсе ACM

HDU5251 прямоугольная зона

Поверните держатель карты, чтобы найти минимальную площадь описанного прямоугольника

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int MAX=1e4+5;
const double eps=1e-8;
const double INF=1e99;
struct point
{
    double x,y;
    point(){}
    point(double a,double b)
    {
        x=a;y=b;
    }
         оператор точки (const point & a) const // разность векторов
    {
        return point(x-a.x,y-a.y);
    }
         двойной оператор ^ (const point & a) const // Векторное перекрестное произведение
    {
        return x*a.y-y*a.x;
    }
         двойной оператор * (const point & a) const // Векторное произведение точек
    {
        return x*a.x+y*a.y;
    }
}p[MAX],b[MAX];
int top,n;
double min(double a,double b)
{
    return a-b<-eps?a:b;
}
 двойное пересечение (точка a, точка b, точка c) // перекрестное произведение (площадь треугольника * 2
{
    return (b-a)^(c-a);
}
 двойное мульти (точка a, точка b, точка c) // точка произведения
{
    return (b-a)*(c-a);
}
 double dis (точка a, точка b) // Расстояние между двумя точками sqrt (dis)
{
    return (a-b)*(a-b);
}
bool cmp(point a,point b)
{
    double tmp=cross(p[0],a,b);
    if(tmp>eps||(fabs(tmp)<eps&&dis(p[0],a)-dis(p[0],b)>eps)) return 1;
    return 0;
}
void graham()
{
    int u=0;top=0;
    for(int k=1;k<n;k++)
        if(p[u].y-p[k].y>eps||(fabs(p[u].y-p[k].y)<eps&&p[u].x-p[k].x>eps))
            u=k;
    swap(p[u],p[0]);
    sort(p+1,p+n,cmp);
    if(n>0) {b[0]=p[0];top++;}
    if(n>1) {b[1]=p[1];top++;}
    if(n<3) return ;
    for(int i=2;i<n;i++)
    {
        while(top>1&&cross(b[top-2],b[top-1],p[i])<eps) top--;
        b[top++]=p[i];
    }
}
double rotating()
{
    int r=1,u=1,l;
    double ans=INF;
    b[top]=b[0];
    for(int k=0;k<top;k++)
    {
        while(cross(b[k],b[k+1],b[u+1])-cross(b[k],b[k+1],b[u])>-eps) u=(u+1)%top;
        while(multi(b[k],b[k+1],b[r+1])-multi(b[k],b[k+1],b[r])>eps) r=(r+1)%top;
        l=k==0?r:l;
        while(multi(b[k],b[k+1],b[l+1])-multi(b[k],b[k+1],b[l])<eps) l=(l+1)%top;
        ans=min(ans,fabs(cross(b[k],b[k+1],b[u]))*fabs(multi(b[k],b[k+1],b[r])-multi(b[k],b[k+1],b[l]))/dis(b[k],b[k+1]));
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int tc=1;tc<=t;tc++)
    {
        scanf("%d",&n);n*=4;
        for(int k=0;k<n;k++) scanf("%lf%lf",&p[k].x,&p[k].y);
        graham();
        printf("Case #%d:n%dn",tc,(int)(rotating()+0.5));
    }
    return 0;
}

Подробное объяснение выпуклой оболочки (переиздание）

1. Справочник

Немного истории:

В 1978 году докторская диссертация М.И. Шамоса «Вычислительная геометрия» ознаменовала зарождение этой области информатики. В то время он опубликовал очень простой алгоритм определения диаметра выпуклого многоугольника, который определялся по максимальному расстоянию между парой точек многоугольника.
Позже диаметр определялся парой точек противодействия пятке. Шамос предложил простой O (n) временной алгоритм для определения выпуклой пары контрапунктов. Поскольку они имеют не более 3n / 2 пар, диаметр можно рассчитать за время O (n).
Как позже предложил Туссен, алгоритм Шамоса похож на вращение пары заклинивающих оболочек вокруг многоугольника. Отсюда и термин «вращающийся джем». В 1983 году Туссен опубликовал статью, в которой использовался тот же метод для решения многих задач. С тех пор был создан новый алгоритм на основе этой модели, решающий многие проблемы.
Они включают в себя:

• Рассчитать расстояние
  • Выпуклый диаметр многоугольника
  • Ширина выпуклого многоугольника
  • Максимальное расстояние между выпуклыми многоугольниками
  • Минимальное расстояние между выпуклыми полигонами
• Ограничительный прямоугольник
  • Минимальная площадь прямоугольника
  • Минимальный периметр описанного прямоугольника
• Триангуляция
  • Луковая триангуляция
  • Спиральная триангуляция
  • Четырехсторонний раскол
• Свойства выпуклого многоугольника
  • Объединить выпуклый корпус
  • Найти котангенс
  • Выпуклое пересечение многоугольника
  • Критическая касательная
  • Выпуклая многоугольная векторная сумма
• Самый тонкий раздел
  • Тончайшее поперечное сечение

Во-вторых, рассчитать расстояние

1. Выпуклый диаметр многоугольника

Простой пример диаметра многоугольника показан слева. Пары точек диаметра показаны на рисунке в виде черных точек, пересекаемых параллельными линиями (пара параллельных линий красного цвета), диаметр которых выделен голубым цветом.

Очевидно, что невозможно определить пару точек выпуклого многоугольника с диаметром внутри многоугольника. Поэтому поиск следует проводить на границе. На самом деле, поскольку диаметр определяется наибольшим расстоянием параллельных касательных многоугольника, нам нужно только запросить контрапункт. Shamos (1978) предлагает алгоритм сложности времени (O) для вычисления n точек пар выпуклой оболочки и пар пятки. Диаметр может быть получен путем обхода списка вершин, чтобы получить максимальное расстояние. Ниже приводится псевдокод алгоритма Шамоса, опубликованный в «Препарате и Шамосе» в 1985 году.
На входе используется многоугольник P = {p1, …, pn}.

begin
     p0:=pn;
     q:=NEXT[p];
     while (Area(p,NEXT[p],NEXT[q]) > Area(p,NEXT[p],q)) do
          q:=NEXT[q];
          q0:=q;
          while (q != p0) do
               begin
                    p:=NEXT[p];
                    Print(p,q);
                    while (Area(p,NEXT[p],NEXT[q]) > Area(p,NEXT[p],q) do
                         begin
                              q:=NEXT[q];
                              if ((p,q) != (q0,p0)) then Print(p,q)
                              else return
                         end;
                    if (Area(p,NEXT[p],NEXT[q]) = Area(p,NEXT[p],q)) then
                      if ((p,q) != (q0,p0)) then Print(p,NEXT[q])
                      else Print(NEXT[p],q)
               end
end.

ВотPrint(p,q)Указывает, что (p, q) выводится в качестве контрапункта,Area(p,q,r)Представляет направленную площадь треугольника pqr.
Хотя этот процесс интуитивно отличается от обычного алгоритма заклинивания с вращением, он, по сути, одинаков, и все вычисления углов исключаются.

Ниже приведен более интуитивный алгоритм:

1. Рассчитать многоугольникyКонечная точка в направлении. Мы называем этоymin с ymax 。
2. Проходитьymin с ymaxПостроить две горизонтальные касательные. Поскольку они уже являются парой контрапунктов, рассчитайте расстояние между ними и сохраните его как текущий максимум.
3. Вращайте обе линии одновременно, пока одна из них не совпадет с одной стороной многоугольника.
4. В это время генерируется новый контрапункт. Рассчитайте новое расстояние, сравните его с текущим максимальным значением и обновите его, если оно больше текущего максимального значения.
5. Повторите процесс шага 3 и шага 4, пока пара контрпунктов не будет сгенерирована снова(ymin,ymax) 。
6. Выход определяет максимальный диаметр пары пяточных точек.

Пока что описанный выше процесс (в псевдокоде) очень полезен. Мы можем получить другую информацию из пар контрапунктов, например, ширину многоугольника.

2. Ширина выпуклого многоугольника

Принципиальная схема ширины выпуклого многоугольника. Пары диаметра показаны в виде черных точек, пересекаемых параллельными касательными (красные линии). Диаметр показан светлой синей линией.

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

1. Рассчитать многоугольникyКонечная точка в направлении. Мы называем этоymin с ymax。
2. Проходитьymin с ymaxПостроить две горизонтальные касательные. Если линия (или две) линии совпадают с ребром, то создается пара «точка-точка-край» или пара «ребро-край». В это время расстояние между двумя линиями рассчитывается и сохраняется как текущее минимальное расстояние.
3. Вращайте обе линии одновременно, пока одна из них не совпадет с одной стороной многоугольника.
4. В это время генерируется новая пара «противоположная точка-кромка» (или пара «кромка-кромка», когда обе линии совпадают с кромкой). Рассчитайте новое расстояние, сравните его с текущим минимальным значением и обновите, если оно меньше текущего минимального значения.
5. Повторяйте шаги 3 и 4 (застрявшие), пока начальная параллельная позиция края не будет достигнута снова.
6. Пара полученного минимального значения выводится как пара определенной ширины.

Более интуитивно понятныйалгоритмОпять же, из-за необходимости введения угловых расчетов, это показывает его недостатки. Однако, как и в задаче о максимальном расстоянии между выпуклыми многоугольниками, иногда в расчет необходимо ввести более простой и интуитивно понятный алгоритм заклинивания вращения.

3. Максимальное расстояние между выпуклыми многоугольниками

1. расчетP yВершина с наименьшим значением координаты (называетсяyminP ) с Q yВершина с наибольшим значением координаты (называетсяymaxQ）。
2. Для полигоновyminP с ymaxQДве касательные построеныLP с LQТак что соответствующие им полигоны находятся справа от них. на данный момент LPс LQЕсть разные направления, иyminP с ymaxQСтаньте контрапунктом между полигонами.
3. Рассчитать расстояние (yminP,ymaxQ) И поддерживать его на текущем максимуме.
4. Вращайте параллельные линии по часовой стрелке одновременно, пока одна из них не совпадет с краем многоугольника, на котором она находится.
5. Создается новая пара контрапунктов. Новое расстояние вычисляется, сравнивается с текущим максимальным значением и обновляется, если оно больше текущего максимального значения. Если две линии совпадают с ребром в одно и то же время, необходимо рассмотреть в общей сложности три пары точек пятки (комбинацию предыдущей и новой вершин).
6. Повторите шаги 4 и 5, пока новая пара точек не будет (yminP,ymaxQ)。
7. Максимальное выходное расстояние.

4. Минимальное расстояние между выпуклыми многоугольниками

1. «Вертекс-Вертекс» ситуация
2. Чехол «Vertex-edge»
3. Ситуация «бок о бок»

Другими словами, пара точек, определяющая минимальное расстояние, не обязательно должна быть вершиной. Следующие три легенды иллюстрируют вышеприведенные выводы:
   
Учитывая результат, естественным образом возникает алгоритм, основанный на вращающихся заклинивших пластинах:
Рассмотрим следующий алгоритм: вход в алгоритм — два выпуклых многоугольника P и Q с m и n по заданным вершинам по часовой стрелке соответственно.

1. расчетP yВершина с наименьшим значением координаты (называетсяyminP ) с Q yВершина с наибольшим значением координаты (называетсяymaxQ）。
2. Для полигоновyminP с ymaxQДве касательные построеныLP с LQТак что соответствующие им полигоны находятся справа от них. на данный момент LPс LQЕсть разные направления, иyminP с ymaxQСтаньте контрапунктом между полигонами.
3. Рассчитать расстояние (yminP,ymaxQ) И поддерживать его до текущего минимального значения.
4. Вращайте параллельные линии по часовой стрелке одновременно, пока одна из них не совпадет с краем многоугольника, на котором она находится.
5. Если с ребром совпадает только одна линия, то необходимо рассчитать только расстояние между парой точек пятки «вершина-край» и парой точек пятки «вершина-вершина». Оба сравнивают их с текущим минимальным значением, а также заменяют и обновляют, если оно меньше текущего минимального значения. Если обе касательные совпадают с ребрами, ситуация усложняется. Если ребра «перекрываются», то есть вы можете построить общую вертикальную линию, которая пересекает оба ребра (но не в вершине), а затем рассчитать расстояние «ребро-ребро». В противном случае вычислите расстояние между тремя новыми парами «вершина-вершина» точек пятки. Все эти расстояния сравниваются с текущим минимальным значением, и если оно меньше текущего минимального значения, замена обновляется.
6. Повторите шаги 4 и 5, пока новая пара точек не будет (yminP,ymaxQ)。
7. Максимальное выходное расстояние.

В-третьих, внешний прямоугольник

1. Выпуклый многоугольник, минимальная площадь описанного прямоугольника

Приведенный выше вывод показан на рисунке: четыре касательных (красного цвета), одна из которых совпадает с одной стороной многоугольника, определяют ограниченный прямоугольник (синий цвет).

1. Рассчитайте конечные точки всех четырех полигонов и назовите этоxminP， xmaxP， yminP， ymaxP。
2. Построен через четыре точкиPЧетыре касательных. Они определили два набора «застрял».
3. Если одна (или две) линии совпадают с ребром, то площадь прямоугольника, определяемая четырьмя линиями, вычисляется и сохраняется как текущее минимальное значение. В противном случае текущее минимальное значение определяется как бесконечность.
4. Вращайте линию по часовой стрелке, пока один из них не совпадет с одной стороной многоугольника.
5. Рассчитайте площадь нового прямоугольника и сравните его с текущим минимальным значением. Если оно меньше текущего минимального значения, оно обновляется, и информация о прямоугольнике, определяющая минимальное значение, сохраняется.
6. Повторяйте шаги 4 и 5 до тех пор, пока угол поворота линии не станет больше 90 градусов.
7. Минимальная площадь выходного прямоугольника.

2. Выпуклый многоугольник с минимальным периметром описанного прямоугольника

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

Поскольку эта проблема эквивалентна проблеме ее площади, эту проблему можно решить с помощью аналогичного алгоритма, основанного на вращающемся заклинивании.
Ввод подчиненного алгоритма представляет собой выпуклый многоугольник, заданный по часовой стрелкеnВершина.

1. Рассчитайте конечные точки всех четырех полигонов и назовите этоxminP， xmaxP， yminP， ymaxP。
2. Построен через четыре точкиPЧетыре касательных. Они определили два набора «застрял».
3. Если одна (или две) линии совпадают с ребром, то площадь прямоугольника, определяемая четырьмя линиями, вычисляется и сохраняется как текущее минимальное значение. В противном случае текущее минимальное значение определяется как бесконечность.
4. Вращайте линию по часовой стрелке, пока один из них не совпадет с одной стороной многоугольника.
5. Рассчитайте периметр нового прямоугольника и сравните его с текущим минимальным значением. Если оно меньше текущего минимального значения, оно обновляется, и информация о прямоугольнике, определяющая минимальное значение, сохраняется.
6. Повторяйте шаги 4 и 5 до тех пор, пока угол поворота линии не станет больше 90 градусов.
7. Минимальный периметр выходного прямоугольника.

4. Триангуляция

1. Луковая триангуляция

Набор луковых шкур. Обратите внимание, что в дополнение к выпуклому многоугольнику самая внутренняя структура может быть отрезком или одной точкой. На этом рисунке представлена ​​иерархическая информация о точках, например, какая из них находится относительно «глубже» между точками.

1. Вставьте край выпуклой оболочки как треугольный край.
2. расчетP с QизxТочки с наименьшими координатами называютсяxmin(P) с xmin(Q) 。
3. Вxmin(P) с xmin(Q)Есть две вертикальные касательные линии, называемыеLP с LQ 。
4. Будет (xmin(P), xmin(Q)) Вставьте как треугольный край.
5. ТекущийLP с LQсоответствующийp с qОчкиxmin(P) с xmin(Q)。
6. Поверните нить по часовой стрелке, пока один из них не совпадет с ребром. Таким образом, новая вершина «вычеркивается» линией.
   • Если он принадлежитP(Известный как)p’), Вставить (p’, q) В триангуляцию. Обновить текущую точку доp’ с p’ 。
   • Если он принадлежитQ(Называется q ‘), вставьте (p, q’) В триангуляцию. Обновить текущую точку доp с q’ 。
   • Для случая параллельных ребер обе касательные совпадают с ребрами, и две новые вершины являются «хитами» (назовите их «p’ с q’). Затем вставьте (p’, q’) , а также (p, q’) с (p’, q) В триангуляцию. Обновить текущую точку доp’ с q’ 。
7. Повторите вышеуказанные шаги, пока не будет достигнута начальная минимальная точка.

Триангуляция изменения лица выглядит следующим образом:

2. Спиральная триангуляция

Спиральная триангуляция наборов точек представляет собой диаграмму триангуляции, основанную на спиральной выпуклой оболочке набора.
Выпуклая спираль может быть построена следующим способом:

1. Начните с определенной конечной точки (например, минимальной точки в заданном направлении), где берется минимумxКоординатные точки.
2. Постройте отвесную линию через эту точку.
3. Вращайте линию в заданном направлении (всегда держите ее по часовой стрелке или против часовой стрелки), пока линия не «ударит» другую вершину.
4. Соедините две точки отрезком.
5. Повторите шаги 3 и 4, но всегда игнорируйте точки, которые были поражены.

В общем, этот процесс похож на алгоритм обтекания объема для расчета выпуклых оболочек, но разница в том, что его цикл никогда не останавливается. Для выпуклой оболочки естьhНабор точек, существует2hВыпуклая спираль: для каждой начальной точки есть спирали по часовой стрелке и против часовой стрелки.

Набор точек (слева) и его выпуклая спираль по часовой стрелке с наименьшимxКоординатная точка используется в качестве начальной точки.

1. Вставьте край выпуклой спирали как треугольный край.
2. От p1В начале ищите последнюю точку на выпуклой спирали множества точекph 。
3. Расширить последний край выпуклой спирали [p(n-1),pn] Пока не пересекает выпуклую спираль. Отметить пересечение какq’ 。
4. Структура иCВырезать в точкуq’Tangent. Поверните эту линию против часовой стрелки, пока он иCПересечь в одной точкеqИ параллельно с [p(n-1),pn] 。
5. Будет [p(n-1), q] Вставьте в триангуляцию.
6. После этой операции выпуклая спиральная цепь делится на две части: часть вне цепи и многоугольная область внутри цепи. Предполагать Co = { p1 , … , qА такжеCi = { ph , … , q , … , pn}. Процесс строительства показан ниже:  

   Верхний левый угол: процесс строительства. Верхний правый угол: многоугольная область снаружи и внутри спирали. Внизу: внешние и внутренние выпуклые цепиCo сCi 。

7. Внешняя спиральная область может быть триангулирована как тор.Co с CiВ это время его можно рассматривать как вложенную выпуклую оболочку.
8. Внутренняя многоугольная область может быть легкоpnЗвездные деления образуют триангуляцию.
9. Комбинация этих двух триангуляций составляет всю структуру спиральной триангуляции.

Пример спиральной выпуклой оболочки и ее триангуляции показаны ниже:

Вышеупомянутый алгоритм имеет линейную временную сложность, и время алгоритма зависит от времени работы тора.

3. Четырехсторонний раскол

Пять выпуклых свойств многоугольника

1. Слияние выпуклых оболочек

Два выпуклых многоугольника, которые не пересекаются. Объединенная выпуклая оболочка содержит выпуклую цепь корпуса из двух многоугольников (толстая синяя сплошная линия на пути), соединенная мостом между многоугольниками (синяя пунктирная линия на пути)

Учитывая два непересекающихся многоугольника, между многоугольниками есть два моста. Когда полигоны пересекаются, они имеют такое же количество мостов, что и количество вершин, как показано на следующем рисунке:

Два выпуклых многоугольника, которые пересекаются. Объединенный выпуклый корпус содержит только мосты между многоугольниками (показаны пунктирными линиями). Есть восемь мостов, соединяющих восемь вершин.

Суть операции объединения — метод разделяй и властвуй. Он также используется в полигонах. Очень простой способ получить выпуклую оболочку состоит в том, чтобы разделить набор точек на две части, вычислить выпуклые оболочки двух меньших наборов точек по отдельности и объединить их. Каждый набор снова делится до тех пор, пока количество элементов не станет достаточно маленьким (скажем, три или меньше), чтобы можно было легко получить выпуклый корпус.
Туссен предложил использовать вращающуюся карточную оболочку, чтобы найти мост между двумя выпуклыми многоугольниками. Основным преимуществом этого метода является то, что он использует возвратный путь, и полигоны могут перекрываться (другие алгоритмы требуют, чтобы полигоны не пересекались). Следующий вывод является основным процессом его алгоритма:
Для заданного выпуклого многоугольника P = {{p (1), …, p (m)} и Q = = {q (1), …, q (n)}, Пара точек (p (i), q (j)) образует мост между P и Q тогда и только тогда, когда:

1. (p(i), q(j)) Формируем пару параллельных точек.
2. p(i-1), p(i+1), q(j-1), q(j+1) расположены (p(i), q(j)) Та же сторона составленной линии.

Предполагая, что многоугольники заданы в стандартной форме, а вершины расположены по часовой стрелке, алгоритм выглядит следующим образом:

1. Рассчитать отдельноP с QИмеет самый большойyВершины координат. Если таких точек более одного, возьмитеxСамая большая координата.
2. Построить плоскую касательную этих точек, с многоугольником на правой стороне в качестве положительного направления (поэтому они указывают наx(Ось положительное направление).
3. Одновременно вращайте две касательные по часовой стрелке, пока одна из них не пересекает край. Получить новую пару параллельных точек (p(i), q(j)). Для случая параллельных сторон получаются три пары параллельных пяточных точек.
4. Для всех действительных пар параллельных пяток (p(i), q(j)): Решениеp(i-1), p(i+1), q(j-1), q(j+1) все находятся в точке подключения (p(i), q(j)) На той же стороне образовалась линия. Если это так, эта пара параллельных каблуков образует мост и отмечает его.
5. Повторяйте шаги 3 и 4, пока касательная не вернется в исходное положение.
6. Все возможные мосты были определены в это время. Объединенная выпуклая оболочка создается путем непрерывного соединения соответствующих выпуклых цепочек корпусов между мостами.

Приведенные выше выводы определяют правильность алгоритма. Время работы ограничено шагами 1, 5 и 6. Все они имеют O (N) время выполнения (N — общее количество вершин). Следовательно, алгоритм имеет сложность текущего времени.
 

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

2. Найти котангенс

Общая касательная — это простая прямая линия, которая касается многоугольника одновременно, и оба многоугольника находятся на одной стороне линии. Другими словами, общая касательная — это линия, которая касается обоих многоугольников. Пример показан ниже:
 

Два непересекающихся выпуклых многоугольника и общая касательная

3. Выпуклое пересечение многоугольника

Учитывая два многоугольника, наш первый вопрос для обсуждения должен быть: «Они пересекаются?». Chazelle и Dobkin опубликовали алгоритм логарифмического времени в своей статье под названием «Обнаружение легче, чем вычисление» в 1980 году (название статьи очень уместно). Для пересечения многоугольников многие алгоритмы могут вычислять пересечение. Что интересно, так это вывод (предложенный Guibas), который доказывает, что существует взаимно-однозначное соответствие между точками пересечения многоугольников и мостами между ними.

Два многоугольника (светло-красный и синий) и их пересечение (светло-фиолетовый). Пересечение отмечено красным. Каждое пересечение связано с мостом между полигонами (отмечен красной пунктирной линией).

4. Критическая касательная

1. p (i), q (j) составляют пары контрапунктов между полигонами.
2. p (i-1), p (i + 1) находится на стороне линии (p (i), q (j)), а q (j-1), q (j + 1) на другой стороне.

Используя этот вывод, линия CS может быть легко определена. Только пары контрпунктов между полигонами должны быть проверены. Поэтому Туссен рекомендует использовать вращающиеся клетки. Предполагая, что многоугольник задан в стандартной форме, а вершины расположены по часовой стрелке, рассмотрим следующий процесс:

1. Вычислите вершину с наименьшим значением координаты на P (называемую yminP) и вершину с наибольшим значением координаты на Q (называемую yymaxQ).
2. Постройте две касательные линии LP и LQ для многоугольников в yyminP и ymaxQ так, чтобы их соответствующие многоугольники были справа от них. В это время LP и LQ имеют разные направления, а yminP и ymaxQ становятся контрпунктом между полигонами.
3. Пусть p (i) = yminP, q (j) = ymaxQ. (p (i), q (j)) образует пару точек пятки между полигонами. Проверьте, есть ли одна сторона p (i-1), p (i + 1) на линии (p (i), q (j)) и q (j-1), q (j + 1) на другой стороне , Если оно выполнено, (p (i), q (j)) определяет линию CS.
4. Вращайте эти две линии, пока одна из них не совпадет с краем соответствующего многоугольника.
5. Новый контрапункт подтвержден. Если обе линии совпадают с ребром, необходимо рассмотреть три пары точек пятки (комбинация исходной вершины и новой вершины). Для всех пар контрпунктов выполните вышеуказанный тест.
6. Повторяйте шаги 4 и 5, пока новая пара точек не станет (yminP, ymaxQ).
7. Выходная линия CS.

5. Векторная сумма выпуклых многоугольников

Для двух выпуклых многоугольников P и Q на данной плоскости векторная сумма P и Q, обозначенная как P + Q, определяется следующим образом:

P + + Q = {p + + q} Все принадлежат P и Q соответственно.

1. P + Q — выпуклый многоугольник.
2. Множество вершин P + Q является суммой множеств вершин P и Q.
3. Множество вершин P + Q является параллельной точкой, установленной между P и Q.
4. Учитывая, что есть P и Q вершин, соответственно, нет больше вершин, чем P + Q.

Наконец, подчиненный вывод не только описывает проблему, но также предоставляет метод для постепенного вычисления векторной суммы вершин.
Учитывая, что k-й вектор z (k) множества P + Q удовлетворяет z (k) = p (i) + q (j). Построение Постройте две параллельные касательные линии в точках p (i) и q (j), чтобы многоугольник находился справа от соответствующей линии. Две линии определяют углы в тета (i) и фи (j) в p (i) и q (j) соответственно (как показано на рисунке ниже)

Таким образом, следующий вектор z (k + 1) равен:

• p (i + 1) + q (j), если theta (i) <ph (j)
• p (i) + q (j + 1), если тета (i)> фи (j)
• p (i + 1) + q (j + 1), если theta (i) = phi (j)

Следующие полигоны и их векторные суммы служат примером.

Два выпуклых многоугольника. Край первого многоугольника отмечен красным, а второй — синим.

Векторная сумма вышеуказанных полигонов. Цвет его стороны такой же, как у оригинального многоугольника.

6. Самый тонкий раздел

1. Самое тонкое сечение

• Пересечение P и Hu (l1) находится на l1.
• Пересечение Q и Hl (l2) находится на l2.

Основной вывод: минимальная ширина полосы (в заданном направлении) множества выпуклых многоугольников семейства F определяется l1 и l2
l1 = tl (CH (UP (F, thethe)), thethe) и
l2 = tu (CH (LP (F, Thethe)), thethe) установлено.

Семейство выпуклых наборов многоугольников и минимальная полоса пропускания под заданным углом. Выпуклая оболочка нижней вершины и верхней вершины, приведенное выше заключение показано на рисунке. Обратите внимание, что пересечение двух многоугольников и полосы появляется только в одной вершине.

1. Найдите вершину с наименьшими и самыми большими координатами. Отметьте их как p и q и постройте горизонтальный касательный через них.
2. Вращайте касательную против часовой стрелки через тета, пока один из них не будет параллелен стороне одного из многоугольников.
3. Если вершина снимается после (в направлении против часовой стрелки), то p является следующей вершиной между углом 0 (включительно) и углом тета (не включено). Если вершина снимается после q, то q является верхней вершиной в том же диапазоне углов. Эти две ситуации могут также возникнуть, когда стороны параллельны.
4. Обновите текущую точку до новой вершины и обновите текущий угол.
5. Повторите шаги с 2 по 4 одновременно с новым угловым интервалом, зная, что новый угол равен 180 градусам (в какой момент вы сначала вернулись в исходное положение, но порядок изменился).

Как быстрее всего найти кратчайшее декартово расстояние между двумя многоугольниками

Ответы
13

upper bound of min distance = min {distance(red's center, current blue's center) + current blue's radius}

for every blue polygon where distance(red's center, current blue's center) - current blue's radius < upper bound of min distance
    check distance of edges and vertices

Другие вопросы по теме

Уважаемый пользователь! Для получения полного доступа ко всем функциями сайта, пожалуйста, пополните счёт