| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 342 人关注过本帖
标题:请教前辈一个关于算法的问题、。。!
只看楼主 加入收藏
yaosi
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2011-5-4
结帖率:0
收藏
 问题点数:0 回复次数:3 
请教前辈一个关于算法的问题、。。!
int rowNumber = 10, colNumber = 10;
  int[,]a=new int [rowNumber,colNumber];
  double cellsize=1;
  int lineID = 1,col,j,row;
  double x1 = 1, y1 = 2;
  double x2 = 8, y2 = 6;
  double k = (y2-y1)/(x2-x1),b = y1-x1*k;  
  int col1=(int)(x1/cellsize),col2=(int)(x2/cellsize);
  int row1=(int)(y1/cellsize),row2=(int)(y2/cellsize);
  if (k > 1 || k < -1)
  {  
  for (col= col1; col < col2;col++ )
  {
  double y0 =col*k+b;
   
  double x = col+1;
  double y = x*k+b;
  double p = Math.Ceiling(y-y0);
  for(j=0;j<p;j++)
  {
  int yz = (int)(y0);
  a[yz, col] = lineID;
  Console.WriteLine("a[{0},{1}]={2}", yz,col, a[yz, col]);

  y0++;
  }
   
   
  }
   
  }
  else
  {
  for (row = row1; row < row2;row++ )
  {
  double x0 =(row-b)/k;
   
  double y = row+1;
  double x = (y-b)/k;
  double p = Math.Ceiling(x - x0);
   
  for(j=0;j<p;j++)
  {
  int xz = (int)(x0);
  a[row, xz] = lineID;
  Console.WriteLine("a[{0},{1}]={2}", row,xz, a[row,xz]);
 ;
  x0++;
   
   
  }
   
   
  }
   
  }



程序定义了一个10乘10的数组。。想要看看从点(1,2)到点(8,6)形成的线段穿过了哪些“格子”。。然后给穿过的这些格子赋值lineID。。。。每次运行出来结果都不对。好像差了几个格子。请各位前辈指教一下。。。很着急很着急!!!非常感谢!!!
搜索更多相关主题的帖子: double 
2011-05-05 19:39
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:0 
程序代码:
/*

 *说明方格的构造顶点坐标(x, y) 宽度(width) 高度(height)

 *程序中顶点坐标是使用一个间接的方式得出 即利用map当中的

 *二位数组的下标分别计算 因为10*10个方格的形状相同.

 */
#include <stdio.h>
#include <math.h>

#define WIDTH    1//宽度
#define HEIGHT    1//高度
#define DIM        10

double p1_x, p1_y, p2_x, p2_y;//两点的坐标
/*线性方程中的参数*/
double k;//斜率
double b;//常量

int map[DIM][DIM];//虚拟位置

/*

 *从终端输入两个点 得出一条直线

 *形如y = k*x + b;

 *1)若返回为1 则表示斜率存在

 *2)若返回为0 则表示斜率不存在

 */
int cacu_k_and_b()
{
    printf("输入第一个点的横纵坐标(例如: x, y): ");
    scanf("%lf, %lf", &p1_x, &p1_y);
    printf("输入第二个点的横纵坐标(例如: x, y): ");
    scanf("%lf, %lf", &p2_x, &p2_y);

    printf("输入的两个点分别为(%.3f, %.3f) 和 (%.3f, %.3f)\n",
        p1_x, p1_y, p2_x, p2_y );

    //斜率
    if (fabs(p1_x - p2_x) < 0.0001)
    {//表示斜率不存在 x = b;
        return 0;
    }
    else
    {
        k = (p1_y-p2_y)/(p1_x-p2_x);
        b = p1_y - k*p1_x;
        //printf("y = %.3fx + %.3f\n", k, b);
        return 1;
    }
}

int isx_in_scope(int x)
{
    if ( p1_x > p2_x )
    {
        if ( p1_x > x*WIDTH && p2_x < (1+x)*WIDTH )
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    else
    {
        if ( p1_x < (x+1)*WIDTH && p2_x > x*WIDTH )
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
}
int isy_in_scope(int y)
{
    if ( p1_y > p2_y )
    {
        if ( p1_y > y*HEIGHT && p2_y < (1+y)*HEIGHT )
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    else
    {
        if ( p1_y < (1+y)*HEIGHT && p2_y > y*HEIGHT )
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
}
/*

 *判断map[y][x]所标记的方框 是否在线段的影响范围内

 *1) 若在则返回 1

 *2) 若不在则返回 0

 */
int is_in_scope(int y, int x)
{
    return isx_in_scope(x) && isy_in_scope(y);
}
/*

 *判断直线与map[y][x]是否存在交点

 *1)若存在 返回1

 *2)若不存在 返回0

 */
int has_common_point( int y, int x)
{
    double p_x, p_y;

    //代入横坐标 x*WIDTH
    //1
    p_y = k * x * WIDTH + b;
    if ( p_y > y*HEIGHT && p_y < (y+1)*HEIGHT )
    {
        return 1;
    }
    //2
    p_y = k * (x+1) * WIDTH + b;
    if ( p_y > y*HEIGHT && p_y < (y+1)*HEIGHT )
    {
        return 1;
    }

    //代入纵坐标 y*WIDHT
    //1
    p_x = (y*HEIGHT-b)/k;
    if ( p_x > x*WIDTH && p_x < (x+1)*WIDTH )
    {
        return 1;
    }
    //2
    p_x = ((y+1)*HEIGHT-b)/k;
    if ( p_x > x*WIDTH && p_x < (x+1)*WIDTH )
    {
        return 1;
    }

    return 0;
}
/*

 *判断直线y = k*x + b 是否经过 虚拟点map[y][x]标记的实际方块

 *1)若是进过 则返回1

 *2)若是不经过 则返回0

 */
int is_cross_block(int y, int x, int flag)
{
    //1.贯穿整个方框则和边界(不同的边)有两个交点

    //2.一个点为线段的终点或者起点 驻留在方块里面 则两端和方块只有一个
    // 交点

    //3. 若斜率为 0  或者不存在的时候 存在这样的情况 直线落在边上
    if (flag)
    {
        if (0 != k)
        {
            if ( !is_in_scope(y, x) )
            {
                return 0;
            }

            if ( has_common_point(y, x) )
            {//如果有公共点则返回1
                return 1;
            }
        }
        else
        {
            if ( !isx_in_scope(x) )
            {
                return 0;
            }

            if ( (b-y*HEIGHT) > (10e-6) &&
                (((y+1)*HEIGHT)-b) > (10e-6) )
            {
                return 1;
            }       
        }
    }
    else
    {//斜率不存在
        if ( !isy_in_scope(y) )
        {
            return 0;
        }

        if ( (b-x*WIDTH) > (10e-6) &&
            (((x+1)*WIDTH)-b) > (10e-6) )
        {
            return 1;
        }
    }

    return 0;
}

void deal()
{
    int flag;//标记斜率是否存在标志
    int i, j;

    flag = cacu_k_and_b();

    for (i=0; i<DIM; ++i)
    {
        for (j=0; j<DIM; ++j)
        {
            if ( is_cross_block(i, j, flag) )
            {//若果经过则把值置为1
                map[i][j] = 1;
            }
        }
    }

    for (i=0; i<DIM; ++i)
    {
        for (j=0; j<DIM; ++j)
        {
            printf("%d ", map[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

int main(void)
{
    deal();

    return 0;
}
2011-05-07 15:49
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:0 
图片附件: 游客没有浏览图片的权限,请 登录注册
2011-05-07 15:50
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等 级:贵宾
威 望:66
帖 子:1710
专家分:8645
注 册:2009-9-15
收藏
得分:0 
注意调整 方块的高和宽   不同的形状 所画出来的效果是不同的
#define WIDTH    1//宽度
#define HEIGHT    1//高度

c#写的不多  


2011-05-07 15:52
快速回复:请教前辈一个关于算法的问题、。。!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020339 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved