{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:33:43Z","timestamp":1760240023689,"version":"build-2065373602"},"reference-count":30,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2019,2,18]],"date-time":"2019-02-18T00:00:00Z","timestamp":1550448000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Project of National Key R&amp;D Program of China","award":["2017YFC0504404"],"award-info":[{"award-number":["2017YFC0504404"]}]},{"name":"the Fundamental Research Funds for the Central Universities","award":["2015ZCQ-XX"],"award-info":[{"award-number":["2015ZCQ-XX"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In our daily lives, many plane patterns can actually be regarded as a compact distribution of a number of elements with certain shapes, like the classic pattern mosaic. In order to synthesize this kind of pattern, the basic problem is, with given graphics elements with certain shapes, to distribute a large number of these elements within a plane region in a possibly random and compact way. It is not easy to achieve this because it not only involves complicated adjacency calculations, but also is closely related to the shape of the elements. This paper attempts to propose an approach that can effectively and quickly synthesize compact distributions of elements of a variety of shapes. The primary idea is that with the seed points and distribution region given as premise, the generation of the Centroidal Voronoi Tesselation (CVT) of this region by iterative relaxation and the CVT will partition the distribution area into small regions of Voronoi, with each region representing the space of an element, to achieve a compact distribution of all the elements. In the generation process of Voronoi diagram, we adopt various distance metrics to control the shape of the generated Voronoi regions, and finally achieve the compact element distributions of different shapes. Additionally, approaches are introduced to control the sizes and directions of the Voronoi regions to generate element distributions with size and direction variations during the Voronoi diagram generation process to enrich the effect of compact element distributions. Moreover, to increase the synthesis efficiency, the time-consuming Voronoi diagram generation process was converted into a graphical rendering process, thus increasing the speed of the synthesis process. This paper is an exploration of elements compact distribution and also carries application value in the fields like mosaic pattern synthesis.<\/jats:p>","DOI":"10.3390\/a12020041","type":"journal-article","created":{"date-parts":[[2019,2,19]],"date-time":"2019-02-19T04:08:20Z","timestamp":1550549300000},"page":"41","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Computation of Compact Distributions of Discrete Elements"],"prefix":"10.3390","volume":"12","author":[{"given":"Jie","family":"Chen","sequence":"first","affiliation":[{"name":"School of Information Science &amp; Technology, Beijing Forestry University, Beijing 100083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gang","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Information Science &amp; Technology, Beijing Forestry University, Beijing 100083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meng","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Information Science &amp; Technology, Beijing Forestry University, Beijing 100083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,2,18]]},"reference":[{"key":"ref_1","unstructured":"Cho, J.H., Xenakis, A., and Gronsky, S. (2007, January 5\u20139). Course 6: Anyone can cook: inside Ratatouille\u2019s kitchen. Proceedings of the SIGGRAPH \u201807 ACM SIGGRAPH 2007 courses, San Diego, CA, USA. Available online: https:\/\/www.xuebuyuan.com\/zh-hant\/121918.html."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1145\/882262.882358","article-title":"Nonconvex rigid bodies with stacking","volume":"22","author":"Guendelman","year":"2003","journal-title":"ACM Trans. Graphics"},{"key":"ref_3","unstructured":"Barla, P., Breslav, S., Markosian, L., and Thollot, J. (2019, February 14). Interactive Hatching and Stippling by Example. Available online: https:\/\/arxiv.org\/abs\/cs\/0607050."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","article-title":"Least squares quantization in PCM","volume":"28","author":"Lloyd","year":"1982","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1145\/7529.8927","article-title":"Stochastic sampling in computer graphics","volume":"5","author":"Cook","year":"1986","journal-title":"ACM Trans. Graphics"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Hoff, K., Keyser, J., Lin, M., Manocha, D., and Culver, T. (1999, January 8\u201313). Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware. Proceedings of the 26th annual conference on Computer graphics and interactive techniques, Los Angeles, CA, USA.","DOI":"10.1145\/311535.311567"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Smith, K., Liu, Y., and Klein, A.W. (2005, January 29\u201331). Animosaics. Proceedings of the 2005 ACM SIGGRAPH\/Eurographics Symposium on Computer Animation, Los Angeles, CA, USA.","DOI":"10.1145\/1073368.1073397"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Efros, A.A., and Leung, T.K. (1999, January 20\u201325). Texture synthesis by non-parametric sampling. Proceedings of the International Conference on Computer Vision 1999, Kerkyra, Corfu, Greece.","DOI":"10.1109\/ICCV.1999.790383"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Wei, L., and Levoy, M. (2000, January 23\u201328). Fast texture synthesis using tree-structured vector quantization. Proceedings of the 27th annual conference on Computer graphics and interactive techniques, New Orleans, LA, USA.","DOI":"10.1145\/344779.345009"},{"key":"ref_10","unstructured":"Fritzsche, L.P., Hellwig, H., Hiller, S., and Deussen, O. (2005, January 10\u201313). Interactive design of authentic looking mosaics using Voronoi structures. Proceedings of the 2nd international symposium on Voronoi diagrams in science and engineering VD 2005 conference, Seoul, Korea."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1111\/j.1467-8659.2008.01140.x","article-title":"An example-based procedural system for element arrangement","volume":"27","author":"Ijiri","year":"2008","journal-title":"Comput. Graphics Forum"},{"key":"ref_12","unstructured":"Passos, V.A., Waltery, M., and Sousa, M.C. (2010, January 25\u201327). Sample-Based Synthesis of Illustrative Patterns. Proceedings of the Pacific Conference on Computer Graphics and Applications, Hangzhou, China."},{"key":"ref_13","first-page":"1703","article-title":"Vector texture pattern synthesis based on neighborhood histogram matching","volume":"18","author":"Xu","year":"2013","journal-title":"J. Image Graphics"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Hausner, A. (2001, January 12\u201317). Simulating decorative mosaics. Proceedings of the 28th annual conference on Computer graphics and interactive techniques, Los Angeles, CA, USA.","DOI":"10.1145\/383259.383327"},{"key":"ref_15","first-page":"663","article-title":"Stroke pattern analysis and synthesis","volume":"25","author":"Barla","year":"2006","journal-title":"Comput. Graphics"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Hurtut, T., Landes, P.E., Thollot, J., Gousseau, Y., Drouillhet, R., and Coeurjolly, J.F. (2009, January 1\u20132). Appearance-guided synthesis of element arrangements by example. Proceedings of the 7th International Symposium on Non-Photorealistic Animation and Rendering, New Orleans, LA, USA.","DOI":"10.1145\/1572614.1572623"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Efros, A.A., and Freeman, W.T. (2001, January 12\u201317). Image quilting for texture synthesis and transfer. Proceedings of the 28th annual conference on Computer graphics and interactive techniques, Los Angeles, CA, USA.","DOI":"10.1145\/383259.383296"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1145\/501786.501787","article-title":"Real-time texture synthesis by patch-based sampling","volume":"20","author":"Liang","year":"2001","journal-title":"ACM Trans. Graphics"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Hertzmann, A., Jacobs, C.E., Oliver, N., Curless, B., and Salesin, D.H. (2001, January 12\u201317). Image Analogies. Proceedings of the 28th annual conference on Computer graphics and interactive techniques, Los Angeles, CA, USA.","DOI":"10.1145\/383259.383295"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1145\/1015706.1015731","article-title":"Near-regular texture analysis and manipulation","volume":"23","author":"Liu","year":"2004","journal-title":"ACM Trans. Graphics"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1302","DOI":"10.1109\/TVCG.2015.2498620","article-title":"Surface Mosaic Synthesis with Irregular Tiles","volume":"22","author":"Hu","year":"2016","journal-title":"IEEE Trans. Visual. Comput. Graphics"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/116873.116880","article-title":"Voronoi diagrams\u2014A survey of a fundamental data structure","volume":"23","author":"Aurenhammer","year":"1991","journal-title":"ACM Comput. Surv."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1145\/322217.322219","article-title":"Two-dimensional Voronoi diagrams in the L_p-metric","volume":"27","author":"Lee","year":"1980","journal-title":"J. ACM"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/s004540010081","article-title":"Voronoi diagrams for convex polygon-offset distance functions","volume":"25","author":"Barequet","year":"2001","journal-title":"Discrete Comput. Geom."},{"key":"ref_25","unstructured":"Klein, R. (2005). Voronoi Diagrams in the Moscow Metric, Springer."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Labelle, F., and Shewchuk, J.R. (2003, January 8\u201310). Anisotropic voronoi diagrams and guaranteed-quality anisotropic mesh generation. Proceedings of the nineteenth annual symposium on Computational geometry, San Diego, CA, USA.","DOI":"10.1145\/777792.777822"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0021-9991(85)90140-8","article-title":"On the construction of the Voronoi mesh on a sphere","volume":"59","author":"Augenbaum","year":"1985","journal-title":"J. Comput. Phys."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1142\/S0218195999000169","article-title":"Skew Voronoi diagrams","volume":"9","author":"Aichholzer","year":"1999","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Leibon, G., and Letscher, D. (2000, January 12\u201314). Delaunay triangulations and Voronoi diagrams for Riemannian manifolds. Proceedings of the Sixteenth Annual Symposium on Computational Geometry, Kowloon, Hong Kong, China.","DOI":"10.1145\/336154.336221"},{"key":"ref_30","unstructured":"Boissonnat, J.D., Rouxel-Labb\u00e9, M., and Wintraecken, M. (2019, February 14). Anisotropic Triangulations Via Discrete Riemannian Voronoi Diagrams. Available online: https:\/\/arxiv.org\/abs\/1703.06487."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/2\/41\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:33:03Z","timestamp":1760185983000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/2\/41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,18]]},"references-count":30,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2019,2]]}},"alternative-id":["a12020041"],"URL":"https:\/\/doi.org\/10.3390\/a12020041","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,2,18]]}}}