以最少的步数绘制立方体顶点 [英] Draw cube vertices with fewest number of steps

查看：189
本文介绍了以最少的步数绘制立方体顶点的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

如何绘制所有立方体的顶点所需的最少步数是多少？ /i.stack.imgur.com/9Aq87.gifalt =显示立方体坐标的图表>



到目前为止，我已将其缩小到16个步骤：

  0,0,0 
 0,0,1 
 0,1,1 
 1， 1,1 
 1,1,0 
 0,1,0 
 0,0,0 
 1,0,0 
 1,0,1 
 0,0,1 
 0,1,1 
 0,1,0 
 1,1,0 
 1,0,0 
 1,0，0 ，1 
 1,1,1

我认为它可以减少少于16步因为只有12个顶点需要绘制



你可以在这里查看一个可以在three.js javascript中使用的示例：
http://jsfiddle.net/kmturley/5aeucehf/show/

解决方案

我为这个


  • 编写了一个小型强力求解器，它是最好的解决方案n有16个顶点

  • 用了大约11.6秒来计算

  • 所有内容都在C ++中（OpenGL可视化）


首先是立方体表示： 

  // ---- -------------------------------------------------- --------------------- 
 #define a 0.5 
 double pnt [] = 
 {
 -a， -a，-a，//指向0 
 -a，-a，+ a，
 -a，+ a，-a，
 -a，+ a，+ a，
 + a，-a，-a，
 + a，-a，+ a，
 + a，+ a，-a，
 + a，+ a，+ a ，//指向7 
 1e101,1e101,1e101，//结束标记
}; 
 #undef a 
 int lin [] = 
 {
 0,1，
 0,2，
 0,4，
 1 ，3，
 1,5，
 2,3，
 2,6，
 3,7，
 4,5，
 4,6 ，
 5,7，
 6,7，
 -1，-1，//结束标记
}; 
 // int solution [] = {0,1,3,1,5,4,0,2,3,7,5,4,6,2,6,7，-1}; //找到折线解决方案
 // --------------------------------------- ------------------------------------ 
 void draw_lin（double * pnt，int * lin ）
 {
 glBegin（GL_LINES）; 
 for（int i = 0; lin [i]> = 0;）
 {
 glVertex3dv（pnt +（lin [i] * 3））;我++; 
 glVertex3dv（pnt +（lin [i] * 3））;我++; 
} 
 glEnd（）; 
} 
 // --------------------------------------- ------------------------------------ 
 void draw_pol（double * pnt，int * pol ）
 {
 glBegin（GL_LINE_STRIP）; 
 for（int i = 0; pol [i]> = 0; i ++）glVertex3dv（pnt +（pol [i] * 3））; 
 glEnd（）; 
} 
 // --------------------------------------- ------------------------------------
$ b $现在是求解器：

$ $ p $ // ----- -------------------------------------------------- --------------------
struct _vtx // vertex
{
List< int>一世; //连接到（顶点...）
_vtx（）{}; _vtx（_vtx& a）{* this = a; }; 〜_vtx（）{}; _vtx * operator =（const _vtx * a）{* this = * a;返回这个; }; / * _ vtx * operator =（const _vtx& a）{... copy ... return this; }; * /
};
const int _max = 16; //知道解决方案的大小（不用费时寻找更长的解决方案）
int use [_max]，uses = 0; //临时行使用标志
int pol [_max]，pols = 0; // temp解决方案
int sol [_max + 2]，sols = 0; //最好找到解决方案
List< _vtx> VTX; //模型顶点+连接信息
// ------------------------------------- --------------------------------------
void _solve（int a）
{
_vtx * v; int i，j，k，l，a0，a1，b0，b1;
//添加点到实际折线
pol [pols] = a;政客++; V =&安培; VTX [A];
//测试解
for（l = 0，i = 0; i< uses; i ++）use [i] = 0; （a0 = pol [0]，a1 = pol [1]，i = 1; i 为（j = 0） ，k = 0; k <使用; k ++）
{
b0 = lin [j]; J ++;
b1 = lin [j]; J ++; （（a0 == b0）&&（a1 == b1））||（（a0 == b1）&&（a1 == b0）
if（！use [k]）if ）））{use [k] = 1;升++; }
}
if（l == uses）//找到更好的解法
if（（pols （sols = 0; sols pols; sols ++）sol [sols] = pol [sols];
//仅当pol不太大时递归
if（pols + 1 i.num; i ++）_solve（v-> i .DAT [I]）;
//返回到之前的状态
pols--; POL [政客] = - 1;
}
// --------------------------------------- ------------------------------------
void solve（double * pnt，int * lin ）
{
int i，j，a0，a1;
//初始化大小
for（i = 0; i <_max; i ++）{use [i] = 0; POL [I] = - 1;溶胶[I] = - 1; （i = 0，j = 0; pnt [i] <1e100; i + = 3，j ++）;}
; vtx.allocate（J）; vtx.num = j的;
for（i = 0; i //初始化连接
for（uses = 0，i = 0; lin [i]> = 0; uses ++）
{
a0 = lin [i]我++;
a1 = lin [i];我++;
vtx [a0] .i.add（a1）;
vtx [a1] .i.add（a0）;
}
//开始真正的解决方案（无论哪个顶点在立方体上都是第一个）
pols = 0;溶胶= _MAX + 1; _solve（0）;
sol [sols] = - 1;如果（sol [0] <0）sols = 0;
}
// --------------------------------------- ------------------------------------

用法：

  solve（pnt，lin）; //调用一次来计算解决方案
 
 glColor3f（0.2,0.2,0.2）; draw_lin（PNT，林）; //绘制灰色轮廓
 glColor3f（1.0,1.0,1.0）; draw_pol（PNT，溶胶）; //通过解决方案覆盖以直观检查正确性（Z缓冲区也必须以相同的值传递!!!）

列表




  • 只是我的动态数组模板

  • List< ; INT> x 相当于 int x []

  • x.add（5 ） ...将5添加到列表的最后

  • x.num 列表中的条目

  • x.allocate（100）将列表大小预先分配到100个条目（以避免重定位速度变慢） b

    $ b解决（pnt，lin）算法


    1. 首先准备顶点数据


      • 每个顶点 vtx [i] 对应于点i-第一点在 pnt 表中

      • i [] list包含连接到这个顶点的每个顶点的索引

        • 以顶点0开始（在立方体上与开始点无关）


          • 否则会有循环遍历每个顶点作为开始点


        • _solve（a）




          • 它为顶点索引添加实际解决方案 pol [pols]

          • 然后测试实际sol中有多少行如果所有来自lin []的行都被绘制出来，并且解决方案比已经找到的小

          • ，则将其复制为新解决方案

          • 如果实际解决方案不是太长，递归地添加下一个顶点

          • 作为连接到上一个顶点的顶点之一
          • 限制组合数目


        • 结束sol [sols]保存解决方案顶点索引列表




          • sols是所使用顶点的数量（第1行）


    [注意]




    • 代码不是很干净，它工作（对不起）

    • 希望我没有忘记复制一些东西


    What's the fewest number of steps needed to draw all of the cube's vertices, without picking up the pen from the paper?

    So far I have reduced it to 16 steps:

    0, 0, 0
0, 0, 1
0, 1, 1
1, 1, 1
1, 1, 0
0, 1, 0
0, 0, 0
1, 0, 0
1, 0, 1
0, 0, 1
0, 1, 1
0, 1, 0
1, 1, 0
1, 0, 0
1, 0, 1
1, 1, 1

    I presume it can be reduced less than 16 steps as there are only 12 vertices to be drawn

    You can view a working example in three.js javascript here: http://jsfiddle.net/kmturley/5aeucehf/show/

    解决方案

    Well I encoded a small brute force solver for this

    • the best solution is with 16 vertexes
    • took about 11.6 sec to compute
    • all is in C++ (visualization by OpenGL)

    First the cube representation:

    //---------------------------------------------------------------------------
#define a 0.5
double pnt[]=
    {
    -a,-a,-a, // point 0
    -a,-a,+a,
    -a,+a,-a,
    -a,+a,+a,
    +a,-a,-a,
    +a,-a,+a,
    +a,+a,-a,
    +a,+a,+a, // point 7
    1e101,1e101,1e101, // end tag
    };
#undef a
int lin[]=
    {
    0,1,
    0,2,
    0,4,
    1,3,
    1,5,
    2,3,
    2,6,
    3,7,
    4,5,
    4,6,
    5,7,
    6,7,
    -1,-1, // end tag
    };
// int solution[]={ 0, 1, 3, 1, 5, 4, 0, 2, 3, 7, 5, 4, 6, 2, 6, 7, -1 }; // found polyline solution
    //---------------------------------------------------------------------------
void draw_lin(double *pnt,int *lin)
    {
    glBegin(GL_LINES);
    for (int i=0;lin[i]>=0;)
        {
        glVertex3dv(pnt+(lin[i]*3)); i++;
        glVertex3dv(pnt+(lin[i]*3)); i++;
        }
    glEnd();
    }
//---------------------------------------------------------------------------
void draw_pol(double *pnt,int *pol)
    {
    glBegin(GL_LINE_STRIP);
    for (int i=0;pol[i]>=0;i++) glVertex3dv(pnt+(pol[i]*3));
    glEnd();
    }
//---------------------------------------------------------------------------

    Now the solver:

    //---------------------------------------------------------------------------
struct _vtx             // vertex
    {
    List<int> i;        // connected to (vertexes...)
    _vtx(){}; _vtx(_vtx& a){ *this=a; }; ~_vtx(){}; _vtx* operator = (const _vtx *a) { *this=*a; return this; }; /*_vtx* operator = (const _vtx &a) { ...copy... return this; };*/
    };
const int _max=16; // know solution size (do not bother to find longer solutions)
int use[_max],uses=0;   // temp line usage flag
int pol[_max],pols=0;   // temp solution
int sol[_max+2],sols=0; // best found solution
List<_vtx> vtx;         // model vertexes + connection info
//---------------------------------------------------------------------------
void _solve(int a)
    {
    _vtx *v; int i,j,k,l,a0,a1,b0,b1;
    // add point to actual polyline
    pol[pols]=a; pols++; v=&vtx[a];
    // test for solution
    for (l=0,i=0;i<uses;i++) use[i]=0;
    for (a0=pol[0],a1=pol[1],i=1;i<pols;i++,a0=a1,a1=pol[i])
     for (j=0,k=0;k<uses;k++)
        {
        b0=lin[j]; j++;
        b1=lin[j]; j++;
        if (!use[k]) if (((a0==b0)&&(a1==b1))||((a0==b1)&&(a1==b0))) { use[k]=1; l++; }
        }
    if (l==uses) // better solution found
     if ((pols<sols)||(sol[0]==-1))
      for (sols=0;sols<pols;sols++) sol[sols]=pol[sols];
    // recursion only if pol not too big
    if (pols+1<sols) for (i=0;i<v->i.num;i++) _solve(v->i.dat[i]);
    // back to previous state
     pols--; pol[pols]=-1;
    }
//---------------------------------------------------------------------------
void solve(double *pnt,int *lin)
    {
    int i,j,a0,a1;
    // init sizes
    for (i=0;i<_max;i++) { use[i]=0; pol[i]=-1; sol[i]=-1; }
    for(i=0,j=0;pnt[i]<1e100;i+=3,j++); vtx.allocate(j); vtx.num=j;
    for(i=0;i<vtx.num;i++) vtx[i].i.num=0;
    // init connections
    for(uses=0,i=0;lin[i]>=0;uses++)
        {
        a0=lin[i]; i++;
        a1=lin[i]; i++;
        vtx[a0].i.add(a1);
        vtx[a1].i.add(a0);
        }
    // start actual solution (does not matter which vertex on cube is first)
    pols=0; sols=_max+1; _solve(0);
    sol[sols]=-1; if (sol[0]<0) sols=0;
    }
//---------------------------------------------------------------------------

    Usage:

    solve(pnt,lin); // call once to compute the solution

glColor3f(0.2,0.2,0.2); draw_lin(pnt,lin); // draw gray outline
glColor3f(1.0,1.0,1.0); draw_pol(pnt,sol); // overwrite by solution to visually check correctness (Z-buffer must pass also on equal values!!!)

    List

    • is just mine template for dynamic array
    • List<int> x is equivalent to int x[]
    • x.add(5) ... adds 5 to the end of list
    • x.num is the used size of list in entries
    • x.allocate(100) preallocate list size to 100 entries (to avoid relocations slowdowns)

    solve(pnt,lin) algorithm

    1. first prepare vertex data

      • each vertex vtx[i] corresponds to point i-th point in pnt table
      • i[] list contains the index of each vertex connected to this vertex

    2. start with vertex 0 (on cube is irrelevant the start point

      • otherwise there would be for loop through every vertex as start point

    3. _solve(a)

      • it adds a vertex index to actual solution pol[pols]
      • then test how many lines is present in actual solution
      • and if all lines from lin[] are drawn and solution is smaller than already found one
      • copy it as new solution
      • after test if actual solution is not too long recursively add next vertex
      • as one of the vertex that is connected to last vertex used
      • to limit the number of combinations

    4. at the end sol[sols] hold the solution vertex index list

      • sols is the number of vertexes used (lines-1)

    [Notes]

    • the code is not very clean but it works (sorry for that)
    • hope I did not forget to copy something

    这篇关于以最少的步数绘制立方体顶点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
其他开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆