步行通道内行人流拉链现象的生成机理与仿真研究

以步行通道内的单向行人流为研究对象,分析研究行人拉链现象的生成机理,并建立基于Voronoi图的速度修正模型对其仿真研究.首先,从行人追求视野最佳和步行舒适的角度分析拉链现象的生成机理,以行人的视野关注和视野遮挡描述影响行人移动过程中产生拉链偏移的因素;以行人局部密度描述行人的步行舒适度;引入拉链敏感系数描述行人客观偏移的意愿程度;提出单个行人侧向偏移的机制,获得行人最佳的偏移位置.然后,构建基于Voronoi图的行人速度修正仿真模型,考虑行人是否有偏移倾向的主观意愿,并嵌入偏移规则,模拟再现行人的拉链现象.仿真发现:行人的拉链层数与通道宽度成正比,该模型速度密度关系图与实证数据吻合较好;与不考虑拉链效应相比,倾向主动进行侧向偏移的行人占比越大,越有助于提高通道内行人的移动速度、舒适度和空间利用率.     

基于Voronoi图盲区的无线传感器网络覆盖控制部署策略

针对无线传感器网络在二维平面应用场景中的覆盖控制问题, 提出了一种基于泰森盲区多边形形心的覆盖控制部署策略(blind-zone centroid-based scheme, BCBS). BCBS先对监测区域做Voronoi图划分以得到被每个传感器节点覆盖的泰森多边形, 而后根据泰森多边形顶点的覆盖情况分析得出泰森多边形内的盲区, 并构造与盲区形状相近的多边形, 最后以该多边形的几何中心作为传感器节点移动的候选目标位置, 从而达到提高网络覆盖率的目的. 仿真实验结果表明, BCBS在覆盖率、节点分布均匀性与节点覆盖效率等方面相比CBS有明显优势. 关键词： 无线传感器网络 节点覆盖 Voronoi图 多边形形心     

Methods for measuring pedestrian density, flow, speed and direction with minimal scatter

The progress of image processing during recent years allows the measurement of pedestrian characteristics on a “microscopic” scale with low costs. However, density and flow are concepts of fluid mechanics defined for the limit of infinitely many particles. Standard methods of measuring these quantities locally (e.g. counting heads within a rectangle) suffer from large data scatter. The remedy of averaging over large spaces or long times reduces the possible resolution and inhibits the gain obtained by the new technologies.In this contribution we introduce a concept for measuring microscopic characteristics on the basis of pedestrian trajectories. Assigning a personal space to every pedestrian via a Voronoi diagram reduces the density scatter. Similarly, calculating direction and speed from position differences between times with identical phases of movement gives low-scatter sequences for speed and direction. Finally we discuss the methods to obtain reliable values for derived quantities and new possibilities of an in-depth analysis of experiments. The resolution obtained indicates the limits of stationary state theory.     

基于质心Voronoi图重构的UDSM边折叠简化

城市数字表面模型网格(UDSM)的相邻网格常常出现曲率剧变,而这些位置是UDSM的细节部分,简化过程中应当尽量保持。针对该情况,引入了质心Voronoi图重划分网格,将曲率较小的表面的点云密度大大降低。重划分的网格表面细节与周围的平滑表面的三角网格尺寸悬殊,在该基础上使用二次误差矩阵边折叠进行LOD构建时网格发生明显变化,范围大大减少。算法在时间性能与网格误差与直接边折叠相近的前提下,更多地保存简化后的网格细节。     

Jamming II: Edwards’ statistical mechanics of random packings of hard spheres

The problem of finding the most efficient way to pack spheres has an illustrious history, dating back to the crystalline arrays conjectured by Kepler and the random geometries explored by Bernal in the 1960s. This problem finds applications spanning from the mathematician’s pencil, the processing of granular materials, the jamming and glass transitions, all the way to fruit packing in every grocery. There are presently numerous experiments showing that the loosest way to pack spheres gives a density of ∼55% (named random loose packing, RLP) while filling all the loose voids results in a maximum density of ∼63%-64% (named random close packing, RCP). While those values seem robustly true, to this date there is no well-accepted physical explanation or theoretical prediction for them. Here we develop a common framework for understanding the random packings of monodisperse hard spheres whose limits can be interpreted as the experimentally observed RLP and RCP. The reason for these limits arises from a statistical picture of jammed states in which the RCP can be interpreted as the ground state of the ensemble of jammed matter with zero compactivity, while the RLP arises in the infinite compactivity limit. We combine an extended statistical mechanics approach ‘a la Edwards’ (where the role traditionally played by the energy and temperature in thermal systems is substituted by the volume and compactivity) with a constraint on mechanical stability imposed by the isostatic condition. We show how such approaches can bring results that can be compared to experiments and allow for an exploitation of the statistical mechanics framework. The key result is the use of a relation between the local Voronoi volumes of the constituent grains (denoted the volume function) and the number of neighbors in contact that permits us to simply combine the two approaches to develop a theory of volume fluctuations in jammed matter. Ultimately, our results lead to a phase diagram that provides a unifying view of the disordered hard sphere packing problem and further sheds light on a diverse spectrum of data, including the RLP state. Theoretical results are well reproduced by numerical simulations that confirm the essential role played by friction in determining both the RLP and RCP limits. The RLP values depend on friction, explaining why varied experimental results can be obtained.     

基于几何覆盖的导航星视场构造算法

由导航星表构造导航星匹配模式是星图匹配、识别的最关键步骤。为了从根本上能保证星图识别模式的完备性,提出了构造导航星视场的方法。从导航星表中任一颗星开始,依次找到两两角距小于FOV的星,构成1颗星、2颗星…m颗星的全部子集(子集P)。以子集P中心的视轴为基准,取两倍于视场的导航星子集Q(Q包含P)。把Q中的每一颗星投影到星敏感器像平面,形成点列子集Q。视场的构造就可以表述为平面上点集的几何覆盖问题。对每一个子集P来说,先计算其最小覆盖圆,若其半径小于视场在像平面的投影值(R),则计算点列子集Q删除P后的Voronoi图,这样就可求出包含点列子集P的最大空圆;若其半径大于R,则点列子集P为一个导航星视场。给出了由20颗导航星生成的124个视场,并与Monte Carlo 20万次随机生成的视场作了比较。结果证明了该算法是有效的、实用的。     

Cooling rate dependence and local structure in aluminum monatomic metallic glass

Abstract

The local atomic structure in aluminium monatomic metallic glass is studied using molecular dynamics simulations combined with the embedded atom method (EAM). We have used a variety of analytical methods to characterise the atomic configurations of our system: the Pair Distribution Function (PDF), the Common Neighbour Analysis (CNA) and the Voronoi Tessellation Analysis. CNA was used to investigate the order change from liquid to amorphous phases, recognising that the amount of icosahedral clusters increases with the decrease of temperature. The Voronoi analysis revealed that the icosahedral-like polyhedral are the predominant ones. It has been observed that the PDF function shows a splitting in the second peak, which cannot be attributed to the only ideal icosahedral polyhedron 〈0, 0, 12, 0〉, but also to the formation of other Voronoi polyhedra 〈0, 1, 10, 2〉 . Further, the PDFs were then integrated giving the cumulative coordination number in order to compute the fractal dimension (d_f).     

基于BP神经网络的小样本星图识别方法

为解决星敏感器的星图识别算法高实时性和鲁棒性,采用了BP神经网络;根据飞行轨迹精简了导航星及对应的模式,即一个视场中的一幅星图对应一个惟一的导航模式。采用二维Voronoi图计算向平面上最大空圆,构造了完备的圆视场集合;经过反复比较,选择以恒星为顶点能构造包含视场中所有星的凸多边形的导航模式,以其角距和顶角作为识别向量,具有平移和旋转不变性,并以该模式为BP神经网络的训练样本。仿真试验表明：该方法的识别成功率达100%,识别时间小于20ms。     

Simulation and Statistical Analysis of Random Packings of Ellipsoids

The paper describes an algorithm for the generation of random packings of ellipsoids of revolution, which is a natural generalization of an older algorithm for the case of spherical particles and belongs to the class of collective rearrangement algorithms. It yields packings with a broad spectrum of densities and geometrical properties, aspect ratio which depend on and the various parameters controlling the motions of ellipsoids during the simulation. The ellipsoid systems obtained are characterized by second‐order characteristics, namely pair correlation and orientation correlation functions. Furthermore, the constructed packings are described in a phase diagram taken from statistical physics.     

Dense Packing on Uniform Lattices

We study the Hard Core Model on the graphs G obtained from Archimedean tilings i.e. configurations in {0,1} ^G with the nearest neighbor 1’s forbidden. Our particular aim in choosing these graphs is to obtain insight to the geometry of the densest packings in a uniform discrete set-up. We establish density bounds, optimal configurations reaching them in all cases, and introduce a probabilistic cellular automaton that generates the legal configurations. Its rule involves a parameter which can be naturally characterized as packing pressure. It can have a critical value but from packing point of view just as interesting are the noncritical cases. These phenomena are related to the exponential size of the set of densest packings and more specifically whether these packings are maximally symmetric, simple laminated or essentially random packings. Research partially supported by The Finnish Academy of Science and Letters.     

Hot ice computer

We experimentally demonstrate that supersaturated solution of sodium acetate, commonly called ‘hot ice’, is a massively-parallel unconventional computer. In the hot ice computer data are represented by a spatial configuration of crystallization induction sites and physical obstacles immersed in the experimental container. Computation is implemented by propagation and interaction of growing crystals initiated at the data-sites. We discuss experimental prototypes of hot ice processors which compute planar Voronoi diagram, shortest collision-free paths and implement and and or logical gates.     

A three-dimensional electrostatic particle-in-cell methodology on unstructured Delaunay–Voronoi grids

The mathematical formulation and computational implementation of a three-dimensional particle-in-cell methodology on unstructured Delaunay–Voronoi tetrahedral grids is presented. The method allows simulation of plasmas in complex domains and incorporates the duality of the Delaunay–Voronoi in all aspects of the particle-in-cell cycle. Charge assignment and field interpolation weighting schemes of zero- and first-order are formulated based on the theory of long-range constraints. Electric potential and fields are derived from a finite-volume formulation of Gauss’ law using the Voronoi–Delaunay dual. Boundary conditions and the algorithms for injection, particle loading, particle motion, and particle tracking are implemented for unstructured Delaunay grids. Error and sensitivity analysis examines the effects of particles/cell, grid scaling, and timestep on the numerical heating, the slowing-down time, and the deflection times. The problem of current collection by cylindrical Langmuir probes in collisionless plasmas is used for validation. Numerical results compare favorably with previous numerical and analytical solutions for a wide range of probe radius to Debye length ratios, probe potentials, and electron to ion temperature ratios. The versatility of the methodology is demonstrated with the simulation of a complex plasma microsensor, a directional micro-retarding potential analyzer that includes a low transparency micro-grid.     

Comparison between smoothed dissipative particle dynamics and Voronoi fluid particle model in a shear stationary flow

We present a numerical comparison between two Lagrangian techniques for the simulation of fluids, smoothed dissipative particle dynamics (SDPD) and Voronoi fluid particle model. These methods reproduce the movement of the fluid with extensive particles. The main differences between these techniques are the volume definition and the implementation of the second derivatives. The Voronoi model is computationally more efficient than SDPD. For quasi-regular meshes, the Voronoi method is more accurate than SDPD but for arbitrary configurations its precision degrades. This means that the SDPD discrete versions of the second derivative operators are better than the ones used in the Voronoi method.     

A Lagrangian fractional step method for the incompressible navier-stokes equations on a periodic domain

In the Lagrangian fractional step method introduced in this paper, the fluid velocity and pressure are defined on a collection of N fluid markers. At each time step, these markers are used to generate a Voronoi diagram, and this diagram is used to construct finite-difference operators corresponding to the divergence, gradient, and Laplacian. The splitting of the Navier-Stokes equations leads to discrete Helmholtz and Poisson problems, which we solve using a two-grid method. The nonlinear convection terms are modeled simply by the displacement of the fluid markers. We have implemented this method on a periodic domain in the planee. We describe an efficient algorithm for the numerical construction of periodic Voronoi diagrams, and we report on numerical results which indicate that the fractional step method is convergent of first order. The overall work per time step is proportional to N log N.     

用于光子相关光谱颗粒粒度测量的实数编码混合遗传算法

提出一种自动缩小反演范围的实数编码混合遗传算法,并用于光子相关光谱颗粒粒度测量中.该算法利用混沌遍历性质,融入模拟退火算法,具有较强的局部搜索能力.通过数值模拟,讨论在无噪声和多种噪声水平影响下单分散颗粒系的反演结果;分析90 nm聚苯乙烯标准颗粒样品的实验测量数据.结果表明,反演的粒径分布在峰值位置、峰宽度、峰对称性等方面很接近颗粒的真实分布,具有较强的抗噪声干扰能力.     

一种复杂多边形最大内圆的快速查找算法

任意多边形的最大内圆的快速查找在多个领域有着重要的应用。首先给出了任意多边形的Voronoi图的生成方法,以及基于Voronoi图实现该多边形的最大内圆的寻找算法,在此基础上分别采用中线简化及并行化处理对算法进行了效率方面的改进,并重点研究了矢量数据并行化过程中的数据分配策略,给出了其最优数据划分策略——算法复杂度均衡法。最后对北美阿拉斯加地区的多个湖泊进行了最大内圆的查找实验,相应的实验结果表明,改进的方法能够很大程度地提高最大内圆的查找效率。     

Lateral diffusion and percolation in membranes

An algorithm based on Voronoi tessellation and percolation theory is presented to study the diffusion of model membrane components (solutes) in the plasma membrane. The membrane is modeled as a two-dimensional space with integral membrane proteins as static obstacles. The Voronoi diagram consists of vertices, which are equidistant from three matrix obstacles, joined by edges. An edge between two vertices is said to be connected if solute particles can pass directly between the two regions. The percolation threshold, pc, determined using this passage criterion is pc approximately equal to 0.53. This is smaller than if the connectivity of edges were assigned randomly, in which case the percolation threshold pr=2/3, where p is the fraction of connected edges. Molecular dynamics simulations show that diffusion is determined by percolation of clusters of edges.     

Topological and statistical properties of a constrained Voronoi tessellation

Voronoi tessellation has been used widely to approximate and model various cellular structures and stochastic patterns appearing in nature. In this work, we present an extended version of the Voronoi tessellation method that partitions the space with certain constraints commonly encountered in either experimental measurements or theoretical models, such as cell volume or size distribution. The new Voronoi method is implemented using an inverse Monte Carlo method. We calculate the topological and statistical properties of tessellated Voronoi cells in several model systems with cell volumes obeying lognormal and bimodal distributions. We also compare the results with those obtained using the conventional Poisson–Voronoi method. We observed systematic changes in the topological properties as well as deviations from some established topological relations as the parameters in the constraint were varied. The application of this constrained Voronoi method in microstructure modelling and characterization in poly- and nano-crystalline materials is briefly discussed.     

Disks vs. spheres: Contrasting properties of random packings

Collections of random packings of rigid disks and spheres have been generated by computer using a previously described concurrent algorithm. Particles begin as infinitesimal moving points, grow in size at a uniform rate, undergo energy-onconserving collisions, and eventually jam up. Periodic boundary conditions apply, and various numbers of particles have been considered (N2000 for disks,N8000 for spheres). The irregular disk packings thus formed are clearly polycrystalline with mean grain size dependent upon particle growth rate. By contrast, the sphere packings show a homogeneously amorphous texture substantially devoid of crystalline grains. This distinction strongly influences the respective results for packing pair correlation functions and for the distributions of particles by contact number. Rapidly grown disk packings display occasional vacancies within the crystalline grains; no comparable voids of such distinctive size have been found in the random sphere packings. Rattler particles free to move locally but imprisoned by jammed neighbors occur in both the disk and sphere packings.This paper is dedicated to Jerry Percus on the occasion of his 65th birthday.