algorithm - computational - ¿Cómo calcular el OBB de múltiples curvas?

cgal

Question

Dadas varias curvas, incluidos segmentos de línea y arcos circulares, ¿cómo calcular el OBB total de todas las curvas?

Parece que la unión de cada OBB de las curvas individuales no es correcta, no es la cobertura mínima.

Mira esta imagen, ¿cómo calcular el cuadro rojo?

Answer 1

también debe agregar la entrada en forma de vector para que podamos probar sus datos ... Me acercaría así:

1. encontrar el centro del eje alineado bbox O(n)

2. calcular la distancia máxima en cada ángulo O(n)

   solo cree una tabla para ángulos m suficientes (como un paso de 5 grados, entonces m = 360/5 ) donde para cada sección de ángulo recuerde solo la distancia máxima del punto distante.

3. calcular la distancia perpendicular máxima para cada rotación O(m^2)

   así que para cada valor de cálculo de la sección de ángulo que es:

   value[actual_section] = max(distance[i]*cos(section_angle[i]-section_angle[actual_section]))

   donde cubro +/- 90 deg alrededor del ángulo de sección real, así que ahora tienes distancias perpendiculares máximas para cada ángulo ...

4. escoja la mejor solución O(m)

   así que mire todas las rotaciones de 0 a 90 grados y recuerde la que tiene un área mínima de OBB . Solo para asegurarse de que el OBB esté alineado con el ángulo de sección y el tamaño de los ejes es el value de ese ángulo y todos los incrementos de 90 grados ... alrededor del centro

Esto no dará como resultado una solución óptima, sino muy cercana. Para mejorar la precisión, puede usar más secciones de ángulo o incluso buscar de forma recursiva la solución encontrada con un ángulo de ángulo cada vez más pequeño (no es necesario calcular las otras áreas de ángulo después de la primera ejecución)

[Editar1]

Traté de codificar esto en C ++ como prueba de concepto y usar su imagen (manejada como un conjunto de puntos) como entrada, así que aquí el resultado para que tenga algo con lo que comparar (para fines de depuración)

gris son puntos detectados de su imagen, rectángulo verde está alineado a los ejes BBox el rectángulo rojo se encuentra OBBox . Los puntos aqua se encuentran a una distancia máxima por intervalo de ángulo y los puntos verdes son una distancia perpendicular máxima para intervalos de ángulo +/-90deg grados. Utilicé 400 ángulos y, como pueden ver, el resultado está bastante cerca ... 360/400 deg precisión, por lo que este enfoque funciona bien ...

Aquí la fuente de C ++:

//---------------------------------------------------------------------------
struct _pnt2D
    {
    double x,y;
    // inline
    _pnt2D()    {}
    _pnt2D(_pnt2D& a)   { *this=a; }
    ~_pnt2D()   {}
    _pnt2D* operator = (const _pnt2D *a) { *this=*a; return this; }
    //_pnt2D* operator = (const _pnt2D &a) { ...copy... return this; }
    };
struct _ang
    {
    double  ang;    // center angle of section
    double  dis;    // max distance of ang section
    double pdis;    // max perpendicular distance of +/-90deg section
    // inline
    _ang()  {}
    _ang(_ang& a)   { *this=a; }
    ~_ang() {}
    _ang* operator = (const _ang *a) { *this=*a; return this; }
    //_ang* operator = (const _ang &a) { ...copy... return this; }
    };
const int    angs=400;  // must be divisible by 4
const int    angs4=angs>>2;
const double dang=2.0*M_PI/double(angs);
const double dang2=0.5*dang;
_ang ang[angs];
List<_pnt2D> pnt;
_pnt2D bbox[2],obb[4],center;
//---------------------------------------------------------------------------
void compute_OBB()
    {
    _pnt2D ppp[4];
    int i,j; double a,b,dx,dy;
    _ang *aa,*bb;
    _pnt2D p,*pp; DWORD *q;
    // convert bmp -> pnt[]
    pnt.num=0;
    Graphics::TBitmap *bmp=new Graphics::TBitmap;
    bmp->LoadFromFile("in.bmp");
    bmp->HandleType=bmDIB;
    bmp->PixelFormat=pf32bit;
    for (p.y=0;p.y<bmp->Height;p.y++)
     for (q=(DWORD*)bmp->ScanLine[int(p.y)],p.x=0;p.x<bmp->Width;p.x++)
      if ((q[int(p.x)]&255)<20)
       pnt.add(p);
    delete bmp;
    // axis aligned bbox
    bbox[0]=pnt[0];
    bbox[1]=pnt[0];
    for (pp=pnt.dat,i=0;i<pnt.num;i++,pp++)
        {
        if (bbox[0].x>pp->x) bbox[0].x=pp->x;
        if (bbox[0].y>pp->y) bbox[0].y=pp->y;
        if (bbox[1].x<pp->x) bbox[1].x=pp->x;
        if (bbox[1].y<pp->y) bbox[1].y=pp->y;
        }
    center.x=(bbox[0].x+bbox[1].x)*0.5;
    center.y=(bbox[0].y+bbox[1].y)*0.5;
    // ang[] table init
    for (aa=ang,a=0.0,i=0;i<angs;i++,aa++,a+=dang)
        {
        aa->ang=a;
        aa-> dis=0.0;
        aa->pdis=0.0;
        }
    // ang[].dis
    for (pp=pnt.dat,i=0;i<pnt.num;i++,pp++)
        {
        dx=pp->x-center.x;
        dy=pp->y-center.y;
        a=atan2(dy,dx);
        j=floor((a/dang)+0.5); if (j<0) j+=angs; j%=angs;
        a=(dx*dx)+(dy*dy);
        if (ang[j].dis<a) ang[j].dis=a;
        }
    for (aa=ang,i=0;i<angs;i++,aa++) aa->dis=sqrt(aa->dis);
    // ang[].adis
    for (aa=ang,i=0;i<angs;i++,aa++)
     for (bb=ang,j=0;j<angs;j++,bb++)
        {
        a=fabs(aa->ang-bb->ang);
        if (a>M_PI) a=(2.0*M_PI)-a;
        if (a<=0.5*M_PI)
            {
            a=bb->dis*cos(a);
            if (aa->pdis<a) aa->pdis=a;
            }
        }
    // find best oriented bbox (the best angle is ang[j].ang)
    for (b=0,j=0,i=0;i<angs;i++)
        {
        dx =ang[i].pdis; i+=angs4; i%=angs;
        dy =ang[i].pdis; i+=angs4; i%=angs;
        dx+=ang[i].pdis; i+=angs4; i%=angs;
        dy+=ang[i].pdis; i+=angs4; i%=angs;
        a=dx*dy; if ((b>a)||(i==0)) { b=a; j=i; }
        }
    // compute endpoints for OBB
    i=j;
    ppp[0].x=ang[i].pdis*cos(ang[i].ang);
    ppp[0].y=ang[i].pdis*sin(ang[i].ang); i+=angs4; i%=angs;
    ppp[1].x=ang[i].pdis*cos(ang[i].ang);
    ppp[1].y=ang[i].pdis*sin(ang[i].ang); i+=angs4; i%=angs;
    ppp[2].x=ang[i].pdis*cos(ang[i].ang);
    ppp[2].y=ang[i].pdis*sin(ang[i].ang); i+=angs4; i%=angs;
    ppp[3].x=ang[i].pdis*cos(ang[i].ang);
    ppp[3].y=ang[i].pdis*sin(ang[i].ang); i+=angs4; i%=angs;
    obb[0].x=center.x+ppp[0].x+ppp[3].x;
    obb[0].y=center.y+ppp[0].y+ppp[3].y;
    obb[1].x=center.x+ppp[1].x+ppp[0].x;
    obb[1].y=center.y+ppp[1].y+ppp[0].y;
    obb[2].x=center.x+ppp[2].x+ppp[1].x;
    obb[2].y=center.y+ppp[2].y+ppp[1].y;
    obb[3].x=center.x+ppp[3].x+ppp[2].x;
    obb[3].y=center.y+ppp[3].y+ppp[2].y;
    }
//---------------------------------------------------------------------------

Usé la plantilla de lista dinámica mía, así que:

List<double> xxx; es lo mismo que double xxx[];
xxx.add(5); agrega 5 al final de la lista
Elemento de matriz de acceso xxx[7] (seguro)
xxx.dat[7] matriz de acceso xxx.dat[7] (acceso directo inseguro pero rápido)
xxx.num es el tamaño real utilizado de la matriz
xxx.reset() borra la matriz y establece xxx.num=0
xxx.allocate(100) preasigna espacio para 100 elementos

Puede ignorar la parte // convert bmp -> pnt[] VCL ya que ya tiene sus datos.