Splay 总结基础精华

article/2025/11/9 17:46:28

前言：


第一次学习Splay是2月份，打板子的时候是3月份，Ac是4月份，写这篇博客是6月初；原因是因为我竟然发现我忘了Splay的板子了！很慌，必须总结一下！

不敢说是最详细的，但希望对看到这篇博客的人有帮助。

（这部分需要很多很多图解！）


开始：几个数组


Splay是处理序列问题的有力工具，并且是一个树形结构的数据结构；主要运用于需要区间删除，插入，翻转，查询，以及数据结构的嵌套等题目中……


Splay是如何保存某一个序列中每一个元素的呢？

和普通的树一样，每一个节点存的是该节点的值（序列中对应元素的值），编号。那么如何将序列中的元素的值放到树里面呢？

1、可以进行整个序列的二分，二分的是序列的子区间，每次二分的时候将 mid 作为字数的根节点，这样就可以得到一个较平衡的树，每二分出一个子树的根节点U，给其标号，并赋值Val（U）；

2、需要记录每个以U为根的子树大小Siz（U）（包括自己），会有很大用处；

3、由于二分得到的树一定是二叉树，所以可以记录Ch（U，0/1），0左1右；

4、二叉树中每个节点只有一个爸爸，记录Fa（U）表示U结点的爸爸；


有了4个数组：

Ch（U，0 / 1）：U的左（0）右（1）儿子；

Siz（U）：以U为根的子树大小；

Val（U）：编号为U的结点携带的值；

Fa（U）：结点U的爸爸；

和2个函数：

update（）：用左右儿子更新其爸爸U的Siz（U）；

build（）：二分建树；


下一步：查询操作


存储好值以后，我们考虑一下如何用序列中的某一个下标位置对应的值呢？（注意，这时候序列可能已经有部分点已经被删除了）

其实很简单，因为当初建树的时候二分就决定了对于一个非叶子叶子结点X来说，X的左子树是 以X为中点的序列的X的左侧，X的右子树是 以X为中点的序列的X的左侧（X对应的值在序列中的下标我们并不知道，因为很可能序列中的下标已经改变了，即已经进行了若干次删除操作）

即：


语言不是很好说明，只有图片说明了。

所以我们只用关心下标的大小与当先结点U的左子树大小就好了！这里设下标值为Pos；


    1、如果下标值Pos大于左子树大小，那么说明一定不在左子树内；

        1.1、如果等于左子树大小+1，那么要找的值一定是结点U携带的值了！这时返回结点编号就好了，所需要寻找的值就是Val（U）；

        1.2、如果大于等于左子树+2，那么要找的值一定在右子树中，到右儿子结点之后，再次进行相同的判断，递归实现；

    2、如果下标值Pos小于等于左子树大小，那么说明所携带需要寻找的值的结点被一定在左子树内，到左儿子结点之后，再次进行相同的判断，递归实现；


最后一定会找到一个结点满足其子树大小等于左子树大小，不论是叶子还是非叶子结点！


下一步：单点删除


删除操作是Splay的一种重要的操作；

现在我们要删除序列中的一个元素（输入指定下标），并且可能原来在这个下标的元素早就已经删除了，也就是说现在查询的下标已经是另一个元素了，这如何实现呢？

我们可以再次利用上面的“寻找位置的值”的树的性质，也就是说，只要我们将需要删除元素下标的前一个所对应树上的结点，放到需要删除元素下标的后一个所对应树上的结点的上面，那么我们要删除的结点就可以很轻松地确定了！

图说：


这样只用把pos+1的左儿子设置为0就好了！

说得轻松，但是这样没有策略地删除是会破坏树的平衡的，也就是说，寻找删除的位置复杂度会很高的，那么如何建立这种策略步骤呢？

下一步：Splay操作


没错这一步就是Splay，是整个算法的核心；

通俗地讲，就是一个屌丝逆袭，成为祖宗的艰辛历程！

我们在删除操作中讲过了，如果没有策略地去删除的话，会大大提高时间复杂度（甚至会影响成为一次删除O（n））；所以我们需要建立策略：

这个策略就是Splay；Splay操作的目的是将某个树上的节点旋转到根，对于单点删除的操作，先将Pos-1“拿”到根节点，然后将Pos+1结点“拿”到根节点的下方（即pos-1的下方），这样就可以按照把pos+1的左儿子设置为0就好了！


下一步：旋转操作

 

这个更加重要，是既保证整个树平衡，又能让儿子变成祖宗的操作！

为什么要这样做呢？我怎么知道，Tarjan大佬想出来的，实在是太强了！

所以直接上干货了：

左旋：

情况1：



左旋还有一种情况，右旋可以自己画一下。

 

设Nd为当前节点，它的爸爸是P，它爸爸的爸爸是PP；

 

Zig-Zig：

儿子和孙子再在同一侧：“左左”或者“右右”

如图


另一种就不言而喻啦，就是将上面的图反过来。

 

Zig-Zag：

儿子和孙子不在同一侧：“左右”或者“右左”

如图



相信聪明的读者已经发现了:

对于Zigzig来说，如果Nd想当祖宗，那么先让Nd的爸爸将Nd的爷爷搞下台，再Nd自己将爸爸搞下去，毕竟，两个长辈还是不好一个人对付的。

而对Zigzag来说，如果Nd想当祖宗，那么只有先让Nd将自己的爸爸搞下台，再搞自己的爷爷，毕竟，爷爷管不了Nd，这种情况Nd自己一个人就可以搞定了。

一共有4种情况；

 

其实还有两种，如果Nd的爸爸已经是我的目标了，那么旋转奋斗两次是没有必要甚至是错误的，所以，这种情况只用旋转一次，把爸爸搞下台就好了。

 

这只是旋转的几种情况，究竟如何实现旋转呢？

我们经过画图发现，其实Zigzig和Zigzag都是由X左旋和X右旋组成的，所以我们只用针对某一个单次旋转进行操作：

1、左儿子右旋，右儿子左旋；

2、如果右旋的左儿子有右子树，那么被它搞下去的那个爸爸的右子树就是左儿子的右子树；同理，如果左旋的右儿子有左子树，那么被它搞下去的那个爸爸的左子树就是右儿子的左子树。



这个操作很自然，像提塑料袋一样。

我们只需要更改每个受旋转影响的节点的父子信息就好了啊。

 

下一步：插入操作

插入和删除一样哒，不过只是删和插本质不同而已：

受到删除的启发，可以将插入的 pos 结点旋转到根，将其后继的 pos+1 结点旋转到 pos 的右儿子，这样我们只需要将我们需要插入的序列建成一个子树之后，和 pos+1 接起来就好啦！接哪里呢？根据 Splay “键建树”的性质，当然是接在 pos+1 的左儿子啦！


下一步：区间删除


这和单点删除是一样哒，只是旋转的额结点不同：我们需要旋转的是，对于即将被删除的区间 [ L，R ] 来说，将 了 L-1 旋转到根，R+1 旋转到 L-1 的右儿子，这样 R+1 的左儿子是什么呢？是不是刚刚好是一个整的序列 [ L，R ]？这样就和单点删除没有区别啦！

注意更新的顺序，先更新 R+1，再 L-1；


下一步：区间翻转


这个怎么办呢？别忘了每个子树的根的意义：其与其子树所代表的序列位于中央的元素，就是子树的根，那么每个序列的中央翻转了之后是不会对它的位置产生影响的（不论在mid或是mid-1），需要翻转的总是左右子树；所以，受到线段树的启发，我们可以对每一个非叶子子树根节点进行标记下放：

1、如果一个非叶子子树根带有下放标记，那么交换左右子树，这样做的意义是左右的序列对于整个子树序列已经换位了，而左右子树所代表的序列内部自动会根据其根的下放而决定翻转或者不翻转。

2、下放标记：如果 非叶子子树根 的 子树的根 已经有了翻转标记，那么就意味着我不需要再进行翻转了啊，因为翻转偶数次还是原来的序列，而这个可以用抑或“^1”实现；下放标记过程在查询一个结点之前，至于 非叶子子树根 的 子树的根 的子树 内的结点下不下放，是以后的事了；总之如果一个结点需要被查询的话，它一定会被下放，其子树也会被交换的，正确；反之如果完全不会查询到它，说明它就是一个没用的垃圾，不会影响答案，还是正确。这就是懒标记的妙处啊！

懒标记的思想还可以用于 Splay 的区间求和+修改，思想大相径庭。


最后一步：注意几点


1、一开始建立 Splay 的时候一定要在序列首位建立“虚拟结点”，并将其值赋为 Inf，因为这个点是不存在的。然而它是至关重要的！因为如果需要删除区间 [ 1，x ] 或者 [ y，n ] 的序列，你会发现根本没有 1-1 这个点或者 n+1 这个点，而建立“虚拟节点”就是解决方案。

2、Splay 的运用很广，其实质是平衡树，也可以化身为 Link Cut Tree 动态树的辅助树。

3、Splay的区间操作没有完全结束，例如求和、乘积、修改都没有写，只写了翻转。


后记：


1、写到手软啊，到 2018.6.30 的凌晨终于写完了啊，累死啦，不过还是很开心的啊！

2、希望各位大佬提建议，欢迎各位萌新来围观学习！

3、画图还是真的不是很好画，画风在中间变了；因为东北联训没有时间写博客了，回到成都需要肝文化课，所以就过了20多天没动，Splay操作后面的是一气呵成的，真的累啊，但完工还是很开心哒！


差点忘了代码：

数组版本：

#include<bits/stdc++.h>const int N=100000+5;using namespace std;int ch[N][3],siz[N],rev[N],val[N],fa[N],a[N];
int root,tail,n,m,x,y;struct SPLAY{void update(int pos){siz[pos]=siz[ch[pos][0]]+siz[ch[pos][1]]+1;}void init(){siz[0]=0;root=build(0,a,1,n+2);}void pushdown(int nd){if(rev[nd]){//翻转标记 ch[nd][0]^=ch[nd][1]^=ch[nd][0]^=ch[nd][1];if(ch[nd][0]) rev[ch[nd][0]]^=1;if(ch[nd][1]) rev[ch[nd][1]]^=1;rev[nd]=0;}}int build(int p,int *a,int l,int r){if(l>r) return 0;int mid=(l+r)>>1;fa[mid]=p;ch[mid][0]=build(mid,a,l,mid-1);ch[mid][1]=build(mid,a,mid+1,r);val[mid]=a[mid];update(mid);return mid;}void rotate(int nd,int pd){int s=ch[nd][!pd];int ss=ch[s][pd];int p=fa[nd];fa[nd]=s;if(p) ch[p][nd==ch[p][1]]=s;else root=s;ch[s][pd]=nd;ch[nd][!pd]=ss;if(ss) fa[ss]=nd;fa[s]=p;update(nd);update(s);}void splay(int nd,int top=0){while(fa[nd]!=top){int p=fa[nd];int pp=fa[p];int nl=nd==ch[p][0];if(pp==top)rotate(p,nl);else{int pl=p==ch[pp][0];if(pl==nl){rotate(pp,pl);rotate(p,nl);}else{rotate(p,nl);rotate(pp,pl);}}}}int find(int pos){int nd=root;while(1){pushdown(nd);if(pos<=siz[ch[nd][0]])nd=ch[nd][0];else if(pos>=siz[ch[nd][0]]+2){pos-=siz[ch[nd][0]]+1;nd=ch[nd][1];}else{splay(nd);return nd;}}}void erase(int pos){int lnd=find(pos-1),rnd=find(pos+1);splay(lnd);splay(rnd,lnd);ch[rnd][0]=0;update(rnd);update(lnd);}void reverse(int l,int r){int lnd=find(l-1);int rnd=find(r+1);splay(lnd);splay(rnd,lnd);rev[ch[rnd][0]]^=1;//打上翻转标记，并且" ^ "保证了原本需要翻转的点现在不需要翻转了 pushdown(ch[rnd][0]);splay(ch[rnd][0]);} 
}
worker;int main(){scanf("%d%d",&n,&m);for(int i=2;i<=n+1;i++)a[i]=i-1;a[1]=0x7fffffff;a[n+2]=0x7fffffff;worker.init();for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);worker.reverse(x+1,y+1);}for(int i=2;i<=n+1;i++)printf("%d ",worker.find(i)-1);return 0;
}


四月份代码风格，难受……


下面是指针版本：

#include <bits/stdc++.h>const  int  N = 100000 + 5 ;int  a [ N ] ;
int  n , m , x , y , ok , inf = 1e9 + 7 ;struct  Node  {Node  * son [ 2 ] ;Node  * fa ; int  val ;int  siz ;int  tag ;void  update ( ) ;void  push_down ( ) ;
}
pool [ N * 32 ] , * tail = pool , * root , * zero = ++ tail ;void  Node :: update ( ) {siz = 1 ;if ( son [ 0 ] != zero )  siz += son [ 0 ] -> siz ;if ( son [ 1 ] != zero )  siz += son [ 1 ] -> siz ;
}
void  Node :: push_down ( ) {if ( tag ) {std :: swap ( son [ 0 ] , son [ 1 ] ) ;if ( son [ 0 ] != zero )  son [ 0 ] -> tag ^= 1 ;if ( son [ 1 ] != zero )  son [ 1 ] -> tag ^= 1 ;tag = 0 ;}
}struct  Splay {void  init ( ) {root = build ( zero , 1 , n + 2 , a ) ;}Node  * build ( Node  * p , int  l , int  r , int  * a ) {if ( l > r )  return  zero ;Node  * nd = ++ tail ;int  mid = l + r >> 1 ;nd -> fa = p ;nd -> val = a [ mid ] ;nd -> son [ 0 ] = build ( nd , l , mid - 1 , a ) ;nd -> son [ 1 ] = build ( nd , mid + 1 , r , a ) ;nd -> update ( ) ;return  nd ;}void  rotate ( Node  * nd , int  pd ) {int  tmp = 1413213 ;Node  * p = nd -> fa ; tmp = p -> siz ;Node  * s = nd -> son [ ! pd ] ; tmp = s -> siz ;Node  * ss = s -> son [ pd ] ; tmp = ss -> siz ;if ( p != zero )  p -> son [ nd == p -> son [ 1 ] ] = s ;else  root = s ;s -> son [ pd ] = nd ;nd -> son [ ! pd ] = ss ;s -> fa = p ;nd -> fa = s ;if ( ss != zero )  ss -> fa = nd ;nd -> update ( ) ;s -> update ( ) ;}void  splay ( Node  * nd , Node  * top = zero ) {while ( nd -> fa != top ) {Node  * p = nd -> fa ;Node  * pp = p -> fa ;int  nl = nd == p -> son [ 0 ] ;int  pl = p == pp -> son [ 0 ] ;if ( pp == top )rotate ( p , nl ) ;else {if ( pl == nl ) {rotate ( pp , pl ) ;rotate ( p , nl ) ;}else {rotate ( p , nl ) ;rotate ( pp , pl ) ;}}}}Node  * find ( int  pos ) {Node  * nd = root ;while ( 1 ) {nd -> push_down ( ) ;if ( pos <= nd -> son [ 0 ] -> siz )nd = nd -> son [ 0 ] ;else  if ( pos >= nd -> son [ 0 ] -> siz + 2 )pos -= nd -> son [ 0 ] -> siz + 1 , nd = nd -> son [ 1 ] ;else {splay ( nd ) ;return  nd ;}}}void  erase ( int  pos ) {Node  * lnd = find ( pos - 1 ) ;Node  * rnd = find ( pos + 1 ) ;splay ( lnd ) ;splay ( rnd , lnd ) ;rnd -> son [ 0 ] -> fa = zero ;rnd -> son [ 0 ] = zero ;rnd -> update ( ) ;lnd -> update ( ) ;}void  erase ( int  l , int  r ) {Node  * lnd = find ( l - 1 ) ;Node  * rnd = find ( r + 1 ) ;splay ( lnd ) ;splay ( rnd , lnd ) ;rnd -> son [ 0 ] -> fa = zero ;rnd -> son [ 0 ] = zero ;rnd -> update ( ) ;lnd -> update ( ) ;}void  reverse ( int  l , int  r ) {Node  * lnd = find ( l - 1 ) ;Node  * rnd = find ( r + 1 ) ;splay ( lnd ) ;splay ( rnd , lnd ) ;Node  * ls = rnd -> son [ 0 ] ;ls -> tag ^= 1 ;ls -> push_down ( ) ;splay ( ls ) ;}
}
work ;int  main ( ) {scanf ( "%d%d" , & n , & m ) ;for ( int  i = 2 ; i <= n + 1 ; i ++ )a [ i ] = i - 1 ;a [ 1 ] = a [ n + 2 ] = inf ;work . init ( ) ;for ( int  i = 1 ; i <= m ; i ++ ) {scanf ( "%d%d" , & x , & y ) ;work . reverse ( x + 1 , y + 1 ) ;}for ( int  i = 1 ; i <= n ; i ++ ) printf ( "%d " , work . find ( i + 1 ) -> val ) ;return  0 ;
}

以上两种版本，没有插入操作，练习插入操作可以做一下 NOI 2003 的文本编辑器（传送门）；


NOI 2003 文本编辑器 的代码：


#include <bits/stdc++.h>const  int  N = 1000000 + 5 ;int  sum , cnt , zc ;
int  n , m , x , y , ok , inf = 1e9 + 7 , plc , sss ;
char s [ 203 ] , sx [ 2 * N ] ;struct  Node  {Node  * son [ 2 ] ;Node  * fa ;char ch ;int  siz ;void  update ( ) ;void  push_down ( ) ;
}
pool [ N * 5 ] , * tail = pool , * root , * zero = ++ tail ;void  Node :: update ( ) {siz = 1 ;if ( son [ 0 ] != zero )  siz += son [ 0 ] -> siz ;if ( son [ 1 ] != zero )  siz += son [ 1 ] -> siz ;
}struct  Splay {Node  * build ( Node  * p , int  l , int  r , char  * a ) {if ( l > r )  return  zero ;Node  * nd = ++ tail ;int  mid = l + r >> 1 ;nd -> fa = p ;nd -> ch = a [ mid ] ;nd -> son [ 0 ] = build ( nd , l , mid - 1 , a ) ;nd -> son [ 1 ] = build ( nd , mid + 1 , r , a ) ;nd -> update ( ) ;return  nd ;}void  rotate ( Node  * nd , int  pd ) {int  tmp = 1413213 ;Node  * p = nd -> fa ; tmp = p -> siz ;Node  * s = nd -> son [ ! pd ] ; tmp = s -> siz ;Node  * ss = s -> son [ pd ] ; tmp = ss -> siz ;if ( p != zero )  p -> son [ nd == p -> son [ 1 ] ] = s ;else  root = s ;s -> son [ pd ] = nd ;nd -> son [ ! pd ] = ss ;s -> fa = p ;nd -> fa = s ;if ( ss != zero )  ss -> fa = nd ;nd -> update ( ) ;s -> update ( ) ;}void  splay ( Node  * nd , Node  * top = zero ) {while ( nd -> fa != top ) {Node  * p = nd -> fa ;Node  * pp = p -> fa ;int  nl = nd == p -> son [ 0 ] ;int  pl = p == pp -> son [ 0 ] ;if ( pp == top )rotate ( p , nl ) ;else {if ( pl == nl ) {rotate ( pp , pl ) ;rotate ( p , nl ) ;}else {rotate ( p , nl ) ;rotate ( pp , pl ) ;}}}}Node  * find ( int  pos ) {Node  * nd = root ;while ( 1 ) {if ( pos <= nd -> son [ 0 ] -> siz )nd = nd -> son [ 0 ] ;else  if ( pos >= nd -> son [ 0 ] -> siz + 2 )pos -= nd -> son [ 0 ] -> siz + 1 , nd = nd -> son [ 1 ] ;else {return  nd ;}}}void  erase ( int  l , int  r ) {Node  * lnd = find ( l - 1 ) ;Node  * rnd = find ( r + 1 ) ;splay ( lnd ) ;splay ( rnd , lnd ) ;rnd -> son [ 0 ] -> fa = zero ;rnd -> son [ 0 ] = zero ;rnd -> update ( ) ;lnd -> update ( ) ;}void  insert ( int  pos , int  num ) {Node  * lnd = find ( pos ) ;Node  * rnd = find ( pos + 1 ) ;splay ( lnd ) ;splay ( rnd , lnd ) ;rnd -> son [ 0 ] = build ( rnd , 1 , num , sx ) ;rnd -> update ( ) ;lnd -> update ( ) ;}
}
work ;void  print ( Node  * nd , int  num ) {if ( nd -> son [ 0 ] != zero )  print ( nd -> son [ 0 ] , num ) ;printf ( "%c" , nd -> ch ) ;if ( nd -> son [ 1 ] != zero )  print ( nd -> son [ 1 ] , num ) ;
}int  main ( ) {//freopen ( "shit.in" , "r" , stdin ) ;scanf ( "%d" , & n ) ;sx [ 1 ] = sx [ 2 ] = '#' ;root = work . build ( zero , 1 , 2 , sx ) ;for ( int  q = 1 ; q <= n ; q ++ ) {scanf ( "%s" , s ) ;if ( s [ 0 ] == 'I' ) {cnt = 0 ;scanf ( "%d" , & zc ) ;getchar ( ) ;for ( int  i = 1 ; i <= zc ; i ++ ) {sx [ i ] = getchar ( ) ;if ( sx [ i ] == '\n'  ||  sx [ i ] == '\r' )i -- ;}//printf ( "%d\n" , cnt ) ;work . insert ( plc + 1 , zc ) ;}if ( s [ 0 ] == 'D' ) {scanf ( "%d" , & zc ) ;sum -= zc ;work . erase ( plc + 2 , plc + zc + 1 ) ;}if ( s [ 0 ] == 'M' ) {scanf ( "%d" , & zc ) ;plc = zc ;}if ( s [ 0 ] == 'P' )plc -- ;if ( s [ 0 ] == 'G' ) {scanf ( "%d" , & zc ) ;Node  * tmp1 = work . find ( plc + 1 ) ;Node  * tmp2 = work . find ( plc + zc + 2 ) ;work . splay ( tmp1 ) ;work . splay ( tmp2 , tmp1 ) ;Node  * lnd = tmp2 -> son [ 0 ] ;sss = 0 ;print ( lnd , zc ) ;printf ( "\n" ) ;}if ( s [ 0 ] == 'N' )plc ++ ;}return  0 ;
}


http://chatgpt.dhexx.cn/article/R69Y2Ztw.shtml

相关文章

关系型数据库与非关系型数据库详解

关系型数据库与非关系型数据库详解

关系数据库与非关系型数据库 一、数据库概述1、关系型数据库2、非关系型数据库 二、数据库区别1、数据存储方式不同2、扩展方式不同3、对事务性的支持不同 三、非关系型数据库产生背景四、Redis简介1、Redis 优点 五、Redis 安装部署六、Redis 命令工具&#xff08;1&#xff0…
阅读更多...
关系型数据库RDS基本简介

关系型数据库RDS基本简介

OSS存放非结构化的数据&#xff0c;如&#xff1a;音频、视频、图片 rds存放结构化的数据&#xff0c;如&#xff1a;一张表&#xff0c; RDS产品概要 可以根据业务的需求进行弹性伸缩。 采用主从备份架构&#xff0c;三节点数据存储&#xff0c;具备高可用性和数据可靠性 …
阅读更多...
2 关系型数据库是什么？

2 关系型数据库是什么？

目录结构 关系型数据库基本概念结构化查询语言数据定义语言&#xff08;DDL&#xff09;数据查询语言&#xff08;Data Query Language, DQL&#xff09;数据操纵语言&#xff08;Data Manipulation Language, DML&#xff09;数据控制语言&#xff08;Data Control Language, …
阅读更多...
常见的关系型数据库有哪些

常见的关系型数据库有哪些

Oracle Database&#xff1a;由Oracle公司开发和维护的商业关系型数据库&#xff0c;具有广泛的应用场景和功能。 MySQL&#xff1a;开源关系型数据库&#xff0c;常用于Web应用程序和小型企业应用。 Microsoft SQL Server&#xff1a;由Microsoft公司开发和维护的商业关系型…
阅读更多...
Bezier曲线快速相交计算(含代码)

Bezier曲线快速相交计算(含代码)

Bezier曲线快速相交计算 背景介绍算法思路解释和分析示例参考资料 背景介绍 很多时候&#xff0c;需要计算曲线段与曲线段是否有交点。常规的思路是直接联立方程求解。不过&#xff0c;直接求方程的解这种思路通常在计算上开销较大。 针对任意曲线&#xff0c;曲线的方程阶次…
阅读更多...
js绘制贝塞尔曲线（Bézier-Curve）

js绘制贝塞尔曲线（Bézier-Curve）

贝塞尔曲线(Bzier curve)&#xff0c;又称贝兹曲线或贝济埃曲线&#xff0c;是应用于二维图形应用程序的数学曲线。一般的矢量图形软件通过它来精确画出曲线&#xff0c;贝兹曲线由线段与节点组成&#xff0c;节点是可拖动的支点&#xff0c;线段像可伸缩的皮筋&#xff0c;我们…
阅读更多...
Bezier曲线与B-Spline曲线

Bezier曲线与B-Spline曲线

微分几何基础 微分集合是用微分的方法来研究曲线的局部性质&#xff0c;如曲线的弯曲程度等。 一条可以用参数表示的三维曲线是一个有界点集&#xff0c;可以写成一个带参数的、连续的、单值的数学函数&#xff1a; { x x ( t ) y y ( t ) z z ( t ) 0 ⩽ t ⩽ 1 p p ( t…
阅读更多...
初识贝塞尔（bezier）曲线

初识贝塞尔（bezier）曲线

文章目录 资料援引贝塞尔曲线的用途一阶贝塞尔&#xff08;bezier&#xff09;曲线二阶贝塞尔&#xff08;bezier&#xff09;曲线三阶贝塞尔&#xff08;bezier&#xff09;曲线高阶贝塞尔&#xff08;bezier&#xff09;曲线三阶贝塞尔曲线求插值&#xff08;Slerp&#xff0…
阅读更多...
贝塞尔曲线（Bezier Curve）原理、公式推导及matlab代码实现

贝塞尔曲线（Bezier Curve）原理、公式推导及matlab代码实现

1. 定义 贝塞尔曲线(Bezier curve)&#xff0c;又称贝兹曲线或贝济埃曲线&#xff0c;是应用于二维图形应用程序的数学曲线。一般的矢量图形软件通过它来精确画出曲线&#xff0c;贝兹曲线由线段与节点组成&#xff0c;节点是可拖动的支点&#xff0c;线段像可伸缩的皮筋&#…
阅读更多...
Bezier（贝塞尔曲线通用规律算法-DEMO）

Bezier（贝塞尔曲线通用规律算法-DEMO）

之前也看过一些相关贝塞尔曲线的知识&#xff0c;但就是一直没有实践应用&#xff1b; 今天&#xff0c;听到有同事&#xff1a;程序、美术&#xff0c;在讨论相关的&#xff0c;人物的曲线路径行走的问题&#xff1b; 一些数学比较牛X的&#xff0c;说了用2阶&#xff0c;或…
阅读更多...
bezier曲线原理(简单阐述)

bezier曲线原理(简单阐述)

原理和简单推导&#xff08;以三阶为例&#xff09;&#xff1a; 设P0、P02、P2是一条抛物线上顺序三个不同的点。过P0和P2点的两切线交于P1点&#xff0c;在P02点的切线交P0P1和P2P1于P01和P11&#xff0c;则如下比例成立&#xff1a; 这是所谓抛物线的三切线定理。 当P0&…
阅读更多...
Bezier贝塞尔曲线

Bezier贝塞尔曲线

1.简介 Bezier曲线在图形学和游戏中经常使用&#xff0c;一般用的比较多的是4个控制点的贝塞尔曲线&#xff0c;这里手写了一个仅供参考&#xff08;注&#xff1a;理论上也可以写任意多个点&#xff08;3个及以上&#xff09;的贝塞尔&#xff0c;就是一个递归的过程&#xff…
阅读更多...
java 贝塞尔曲线_在Java中绘制贝塞尔曲线

java 贝塞尔曲线_在Java中绘制贝塞尔曲线

我需要创建一个简单的Java程序,通过任意数量的点逐个像素地绘制贝塞尔曲线.此刻,一切似乎都没问题,只是曲线总是在x 0 y 0坐标处结束. 截图1 截图2 我需要它在最后一点结束.我的大脑今天工作不太好,所以我正在寻求帮助. 这是我有的&#xff1a; private void drawScene(){ pr…
阅读更多...
贝塞尔曲线（Bezier Curve）原理及公式推导

贝塞尔曲线（Bezier Curve）原理及公式推导

1. 定义 贝塞尔曲线(Bezier curve)&#xff0c;又称贝兹曲线或贝济埃曲线&#xff0c;是应用于二维图形应用程序的数学曲线。一般的矢量图形软件通过它来精确画出曲线&#xff0c;贝兹曲线由线段与节点组成&#xff0c;节点是可拖动的支点&#xff0c;线段像可伸缩的皮筋&#…
阅读更多...
Bezier（贝塞尔）曲线小总结

Bezier（贝塞尔）曲线小总结

在初学时&#xff0c;我发现Bezier曲线&#xff08;中文名贝塞尔曲线&#xff0c;想要了解历史发展等的可以看此百度百科&#xff1a;贝塞尔曲线_百度百科&#xff09;很难理解&#xff0c;故在此写了一篇自己的心得感悟。要理解它最重要的是理解Bernstein基函数。首先&#xf…
阅读更多...
Bezier曲线原理—动态解释

Bezier曲线原理—动态解释

Bezier曲线原理 贝塞尔曲线(Bzier curve)&#xff0c;又称贝兹曲线或贝济埃曲线&#xff0c;是应用于二维图形应用程序的数学曲线。一般的矢量图形软件通过它来精确画出曲线&#xff0c;贝兹曲线由线段与节点组成&#xff0c;节点是可拖动的支点&#xff0c;线段像可伸缩的皮…
阅读更多...
正确的Bezier曲线的绘制

正确的Bezier曲线的绘制

原文地址:http://blog.csdn.net/mylovestart/article/details/8434310 Bezier曲线是参数多项式曲线,它由一组控制多边形折线(控制多边形)的顶点唯一定义,在控制多边形的各顶点中,只有第一个和最后一个顶点在曲线上,其他的顶点则用以定义曲线的导数,阶次和形状 Bezier曲线的数…
阅读更多...
根据Bezier曲线的定义公式实现Bezier曲线的绘制

根据Bezier曲线的定义公式实现Bezier曲线的绘制

Bezier曲线的定义公式 Pi是曲线上点的坐标&#xff08;x,y,(z0)&#xff09;&#xff0c; Bi,n(t)伯恩斯坦公式&#xff0c;绘制Bezier曲线的第一种方法是根据这个公式来绘制。首先看看绘制的效果&#xff1a; &#xff08;1&#xff09;计算定义中多项式的值 首先要求伯恩斯…
阅读更多...
Bezier曲线描述

Bezier曲线描述

Bezier曲线 1.Bezier曲线的定义 当用曲线段拟合曲线f(x)时&#xff0c;可以把曲线表示为许多小线段φi(x)之和&#xff0c;其中φi(x)称为基&#xff08;混合&#xff09;函数。 这些基&#xff08;混合&#xff09;函数是要用于计算和显示的。因此&#xff0c;经常选择多项式…
阅读更多...
Bezier曲线的绘制

Bezier曲线的绘制

Bezier曲线是参数多项式曲线,它由一组控制多边形折线(控制多边形)的顶点唯一定义,在控制多边形的各顶点中,只有第一个和最后一个顶点在曲线上,其他的顶点则用以定义曲线的导数,阶次和形状 Bezier曲线的数学基础是能够在第一个和最后一个顶点之间进行插值的一个多项式混合函数,…
阅读更多...
推荐文章

Copyright @ 2022~2023