在我们内部开发使用的一个工具中,我们需要几乎从 0 开始实现一个高效的二维图像渲染引擎.比较幸运的是,我们只需要画直线.圆以及矩形,其中比较复杂的是画直线和圆.画直线和圆已经有非常多的成熟的算法了,我们用的是Bresenham的算法. 计算机是如何画直线的?简单来说,如下图所示,真实的直线是连续的,但我们的计算机显示的精度有限,不可能真正显示连续的直线,于是我们用一系列离散化后的点(像素)来近似表现这条直线. (上图来自于互联网络,<计算机图形学的概念与方法>柳朝阳,郑州大学数学系) 接下来的

这里不仔细讲原理,只是把我写的算法发出来,跟大家分享下,如果有错误的话,还请大家告诉我,如果写的不好,也请指出来,一起讨论进步. 算法步骤: (1) 输入圆的半径R. (2) 计算初始值d = 1 - R, x  = 0; y = R. (3) 绘制点(x, y), 及其在八分圆中的另外7个对称点. (4) 判断d的符号,若d < 0, 则先将d更新为d+2*x+3,再将(x,y)更新为(x+1, y),否则将d更新为d+2*(x - y) + 5,再将(x, y)更新为(x+1, y-1).

[Bresenham画线算法] Bresenham是一种光栅化算法.不仅可以用于画线,也可以用用画圆及其它曲线. 通过lower与upper的差,可以知道哪一个点更接近线段: 参考:<计算机图形学>3.5.3 Bresenham画线算法

这里不仔细讲原理,只是把我写的算法发出来,跟大家分享下,如果有错误的话,还请大家告诉我,如果写的不好,也请指出来,一起讨论进步. 算法步骤: (1) 输入椭圆的长半轴a和短半轴b. (2) 计算初始值d = b*b + a * a * (-b + 0.25),  x = 0, y = b. (3) 绘制点 (x, y)及其在四分象限上的另外3个对称点. (4) 判断d的符号.若d <= 0,则先将d更新为d + b * b * (2 * x + 3),再将 (x, y)更新为(x+1, y):否

#include<stdio.h> #include<stdlib.h> #include<graphics.h> #include<math.h> void MidBrehansemCircle(int x, int y, int radius); int main() { int gdriver = DETECT, gmove; int x, y, radius; printf("Please input circle corner:\n&qu

开发环境: VC++6.0,OpenGL 实验内容: 使用中点Bresenham算法画圆. 实验结果: 代码: #include <gl/glut.h> #define WIDTH 500 #define HEIGHT 500 #define OFFSET 15 #define R 8 void Init() //其它初始化 { glClearColor(1.0f,1.0f,1.0f,1.0f); //设置背景颜色,完全不透明 glColor3f(1.0f,0.0f,0.0f); //设置画笔

bresenham算法画圆思想与上篇 bresenham算法画线段 思想是一致的 画圆x^2+y^2=R^2 将他分为8个部分,如上图 1. 只要画出1中1/8圆的圆周,剩下的就可以通过对称关系画出这个圆 X变化从0->R 那为什么不采用从-R->R呢, Y=+-sqrt(R^2-x^2); dy/dx=-x/(sqrt(R^2-x^2)) =-x/y 所以采用从-R到R,每次横坐标增1,计算量大,而且在(x=+-R,y=0)处,x的很小变化就引起了y的很大变化. 所以不是采用x从-R---&

中点画圆算法        如同光栅画线算法,我们在每一个步中以单位间隔取样并确定离指定圆近期的像素位置.对于给定半径r和屏幕中心(xc,yc),能够先使用算法计算圆心在坐标原点(0, 0)的圆的像素位置,然后通过将xc加到x且yc加到y.从而把计算出的每一个位置(x,y)移动到其适当的屏幕位置.在第一象限中,圆弧段从x = 0到x = y,曲线的斜率从0变化到-1.0. 因此,能够在该八分圆上的正x方向取单位步长.并使用决策參数来确定每一步两个可能的y位置中,哪一个更接近于圆的位置.然后,其它

function DrawLineBresenham(x1,y1,x2,y2) %sort by x,sure x1<x2. if x1>x2 tmp=x1; x1=x2; x2=tmp; tmp=y1; y1=y2; y2=tmp; end dx=x2-x1; dy=y2-y1; twoDy=2*dy; twoDy_Dx=2*(dy-dx); twoDx=2*dx; twoDx_Dy=2*(dx-dy); twoDxPlusDy=2*(dx+dy); %branch 1: k>0 ?

DDA(digital differential analyzer) 由直线的斜截式方程引入 对于正斜率的线段,如果斜率<=1,则以单位x间隔(δx=1)取样,并逐个计算每一个y值 Yk+1 = Yk + m   (m为由初始点确定的斜率) 对于斜率>1的线段 Xk+1 = Xk + 1/m   (m为由初始点确定的斜率) 起始端点在于右侧时 "+" -> "-" #include "stdlib.h" #include &qu

#include <cstdio> #include <cstring> #include <conio.h> #include <graphics.h> void line1(){ line(100, 100, 200, 400); line(100, 400, 200, 100); line(0, 200, 300, 300); line(0, 300, 300, 200); } void lineDDA(int x0, int y0, int x1,

为了能以任意点为圆心画圆,我们可以把圆心先设为视点(相当于于将其平移到坐标原点),然后通过中点法扫描转换后,再恢复原来的视点(相当于将圆心平移回原来的位置). 圆心位于原点的圆有四条对称轴x=0,y=0,x=y和x=-y,从而圆上一点(x,y),可得到其关于四条对称轴的七个对称点,这称为八对称性,下面的函数就用来显示(x,y)及其七个对称点. void CirclePoints(int x,int y,long color,CDC *pDC) { //第1象限 pDC->SetPixel(x,y

现在的计算机的图像的都是用像素表示的,无论是点.直线.圆或其他图形最终都会以点的形式显示.人们看到屏幕的直线只不过是模拟出来的,人眼不能分辨出来而已.那么计算机是如何画直线的呢,其实有比较多的算法,这里讲的是Bresenham的算法,是光栅化的画直线算法.直线光栅化是指用像素点来模拟直线,比如下图用蓝色的像素点来模拟红色的直线. 给定两个点起点P1(x1, y1), P2(x2, y2),如何画它们直连的直线呢,即是如何得到上图所示的蓝色的点.假设直线的斜率0<k>0,直线在第一象限,Bres

文章版权由作者李晓晖和博客园共有,若转载请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/. 1.背景 某个项目需求中需要在前端进行画圆查询,将圆范围上的多边形要素在前端进行展示.因为此项目的环境是AGS环境,考虑使用AGS的I查询来完成. 2.I查询的相关参数介绍 I查询中主要涉及到如下几个参数:geometry.geometryType.layerDefs.layers.tolerance.mapExtent.imageDisplay等. 2.1理解相对简

一.             算法原理简介: 算法原理的详细描述及部分实现可参考: http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html Fig.1 假设以(x, y)为绘制起点,一般情况下的直观想法是先求m = dy /dx(即x每增加1, y的增量),然后逐步递增x, 设新的点为x1 = x + j, 则y1 = round(y + j * m).可以看到,这个过程涉及大量的浮点运算,效率上是比较低的(特别是在嵌入式

    本节介绍OpenGL中绘制直线.圆.椭圆,多边形的算法原理.     (1)绘制任意方向(任意斜率)的直线: 1)中点画线法: 中点画线法的算法原理不做介绍,但这里用到最基本的画0<=k<=1的中点画线法实现任意斜率k直线的绘制. )当A点x坐标值大于B点坐标值时,即A点在B点的右侧时,交换A.B点的坐标.保证A点在B的左侧. )考虑特殊情况,当直线AB的斜率不存在时,做近似处理,设置斜率为-(y0-y1)*,即近似无穷大. )当斜率m满足0<=m<=1时,按书本上的中点画

Bresenham画线算图形学中最基础的知识了,可惜我并没有选修过图形学,所有还是有必要熟悉一下. 上一篇用到的画线函数应该算是数值微分法,也是我最常用的一种方法,不过这种方法似乎并不是很好. 这里的画线方法比上一种方法好. 算法原理如下: 过各行各列象素中心构造一组虚拟网格线.按直线从起点到终点的顺序计算直线与各垂直网格线的交点,然后确定该列象素中与此交点最近的象素. 该算法的巧妙之处在于采用增量计算,使得对于每一列,只要检查一个误差项的符号,就可以确定该列的所求象素. 更细节的原理参考这里.

博客转载自:https://leileiluoluo.com/posts/kdtree-algorithm-and-implementation.html k-d tree即k-dimensional tree,常用来作空间划分及近邻搜索,是二叉空间划分树的一个特例.通常,对于维度为k,数据点数为N的数据集,k-d tree适用于N≫2k的情形. 1)k-d tree算法原理k-d tree是每个节点均为k维数值点的二叉树,其上的每个节点代表一个超平面,该超平面垂直于当前划分维度的坐标轴,并在该

在集成学习原理小结中,我们讲到了集成学习有两个流派,一个是boosting派系,它的特点是各个弱学习器之间有依赖关系.另一种是bagging流派,它的特点是各个弱学习器之间没有依赖关系,可以并行拟合.本文就对集成学习中Bagging与随机森林算法做一个总结. 随机森林是集成学习中可以和梯度提升树GBDT分庭抗礼的算法,尤其是它可以很方便的并行训练,在如今大数据大样本的的时代很有诱惑力. 1.  bagging的原理 在集成学习原理小结中,我们给Bagging画了下面一张原理图. 从上图可以看出,

前言 本文将介绍机器学习分类算法中的Logistic回归分类算法并给出伪代码,Python代码实现. (说明:从本文开始,将接触到最优化算法相关的学习.旨在将这些最优化的算法用于训练出一个非线性的函数,以用于分类.) 算法原理 首先要提到的概念是回归. 对于回归这个概念,在以后的文章会有系统而深入的学习.简单的说,回归就是用一条线对N多数据点进行一个拟合,这个拟合的过程就叫做回归. Logistic回归分类算法就是对数据集建立回归公式,以此进行分类. 而至于如何寻找最佳回归系数,或者说是分类器的