보로노이 다이어그램(Voronoi Diagram)의 기하학적 형태를 응용한 패션디자인 연구 - 저지 소재를 중심으로 -

이지련,박선희 한국니트디자인학회 2013 패션과 니트 Vol.11 No.2

This study is to research the application possibility of fashion design by using Voronoi diagram with concepts of mathematics and geometrics. Geometric space constructive characteristics of Voronoi diagram was investigated to see the possibility grafting to fashion design in the research work production, and design concept which can be accord with diverse demands of modern fashion design is suggested in creating the high value fashion by developing unique and structural pattern and silhouette with combination between Voronoi diagram and computer programming. For the method and content of the study, concept and definition of Voronoi diagram was organized through advanced researches and literatures to investigate Voronoi diagram which is the theoretical background of the study and after analyzing formative characteristics, the production process of Voronoi diagram was investigated. And geometric shapes which is the characteristic of Voronoi diagram was investigated and in the research of fashion design applying geometric shapes analyzed cases applying geometric three-dimensional shapes through visual materials. For the foundation of above theoretical consideration, space characteristics of Voronoi diagram in the work production were applied at the motif design of work by using Rhino 3D program. In the study, total 4 works were produced by applying geometric shapes of Voronoi diagram. Trying new attempt in the method of fashion design field is meaningful in fashion design. With the thesis, Voronoi diagram in a method of fashion design is thought to be utilized actively as a creative, infinite instrument.

Voronoi Vertex 최적화를 이용한 경로계획 기법 연구

박상혁,홍주현,하현종,유창경,신원영 한국항공우주학회 2013 한국항공우주학회 학술발표회 논문집 Vol.2013 No.11

본 논문은 Voronoi diagram에 기반한 최적 경로계획 기법을 제안한다. Voronoi diagram은 위협의 위치와 크기가 주어져 있을 때, 위협을 최소화하는 경로를 계획하는데 많이 이용되는 기법이다. 하지만 위협이 지수함수 형태로 모델링되고 비행경로가 직선경로로 계획되어야 하는 경우 기존의 (Weighted) Voronoi diagram으로는 한계가 있다. 본 연구에서 Voronoi diagram을 통해 얻어진 초기 비행경로는 위협의 형태에 맞춰 최적화된다. 이때 각 Voronoi vertex를 인접한 vertex를 고정시킨 상태에서 모든 vertex가 수렴할 때 까지 순차적으로 최적화시키는 방법을 이용하여 연산시간을 감소시키고자 하였다. This paper proposes an optimal path planning algorithm based on Voronoi diagram. Voronoi diagram is most widely used path planning technique to avoid the threat as far as possible when the location and strength of the threat are given. But if the threat is modeled as an exponential function and the planned flight path is constrained on the straight, (Weighted) Voronoi diagram has a limitation in applications. In this study, the initial path obtained from Voronoi diagram is optimized considering the shape of threat. Here, each Voronoi vertex is sequentially optimized while adjacent vertices are fixed on the original position until converged. By doing this, the computation time for optimization is greatly reduced.

Polygon-based Vector Voronoi Diagram Implementation

조청운 (사)한국컴퓨터게임학회 2023 한국컴퓨터게임학회논문지 Vol.36 No.2

Implementing a Voronoi diagram for a set of points on a two-dimensional plane is a technique very often used for non-realistic or stylized rendering. However, looking at implementation methods of existing studies, a method of calculating Voronoi cells in a pixel-based image space is used. The implementation of the vector-based Voronoi diagram is a method that can directly express the boundary where cells meet. In the case of the pixel-based method, the boundary between Voronoi cells can be obtained through edge extraction image processing after first making it in the form of an image, and the accuracy is determined by the resolution, which is inevitably less accurate than the vector-based method. That is, the pixel-based Voronoi diagram generation method mainly calculates the Voronoi cell area and does not explicitly have data on clear boundaries. In contrast, the vector-based Voronoi diagram generation method can be said to be a highly accurate expression method because it directly includes the boundary line data of the Voronoi diagram. However, because the pixel-based implementation method is a more intuitive and easy implementation method, existing studies are using the pixel-based implementation method. In this study, we propose a method for calculating Voronoi diagrams in 3D space using polygon geometry directly at points. Both the Euclidean distance and the Manhattan distance can be used, and it is proposed to be used for the extension of the Voronoi diagram for line segments.

Voronoi diagram의 건축적 이해와 도시 주거공간 계획에 대한 적용

이상원,박수훈 대한건축학회지회연합회 2011 대한건축학회지회연합회 학술발표대회논문집 Vol.2011 No.1

Clearance-Based Performance-Efficient Path Planning Using Generalized Voronoi Diagram

JunTak Lee,Tae-Won Kang,Yong-Sik Choi,Jin-Woo Jung 한국지능시스템학회 2023 INTERNATIONAL JOURNAL of FUZZY LOGIC and INTELLIGE Vol.23 No.3

The Voronoi diagram is one of the most well-known methods in clearance-based pathfinding. The generalized Voronoi diagram, which is derived from the Voronoi diagram, accepts a polygon as input. This study proposes a method for generating and simplifying a generalized Voronoi diagram. A generalized Voronoi diagram is generated by creating a Voronoi diagram with points representing polygons. The Douglas-Peucker line simplification algorithm is used to simplify the diagram, and the A-star algorithm is used to determine the optimal path. By comparing the simplified and non-simplified versions, we determine that the simplifying process decreases the run time while preserving most of the clearance; however, the distance inefficiency of the Voronoi diagram is not overcome. Additional research is required to determine a more distance-efficient path.

보로노이 다이어그램의 공간구축 가능성에 관한 연구-디지털 패브리케이션의 폴딩 기법을 중심으로-

임우창 ( Lim Woochang ),이재규 ( Lee Jaekyu ) 한국공간디자인학회 2021 한국공간디자인학회논문집 Vol.16 No.1

(Background and Purpose) In recent arts and design fields including architecture, the convergence with theories, technologies, etc. of other fields has broken bounds, and various attempts are being made. In the architectural area, studies and cases of parametric design applied with the generative theory of nature have emerged, creating a new paradigm. Among them, The Voronoi diagram is a theory allowing effective compositions of space and realization of stable structure and formative aesthetics based on a geometric constitution. However, it fails to go beyond the decorative role applied with patterns in the current state, and cases and studies on building spaces are lacking. Thus, this study aims to verify the possibilities of building the Voronoi diagram applied with the folding technique of digital fabrication. To this end, the process of digital fabrication is applied to complete a pavilion prototype. (Method) The Voronoi diagram is defined based on literature, and Grasshopper, a visual programming language method enabling effective modeling for this, is examined. Second, folding is proposed as the technique to build the Voronoi diagram, and this is examined. Third, a pavilion reflecting features of the Voronoi diagram is modeled according to the process of digital fabrication. Next, a flat paper is processed with CNC lasers and produced into a unit with the folding technique, and then, the pavilion prototype is embodied. (Results) The Voronoi diagram showed expressive features of repetitive self-replication, self-organization, and algorithmic evolution, and continuity, organicness, and flexibility were respectively displayed in the process. As a result of writing an algorithm reflecting these features. Folding can be classified into creasing, folding, crumpling, and bending based on preceding research, and commonly exhibited. Moreover, folding allows effective utilization of material in digital fabrication and has the features of lightweighting spaces. Applying folding to the process of digital fabrication based on this organically linked pavilion units and effectively divided designated spaces, and polygonal units could be dimensionalized by processing a flat paper exquisitely and using the folding technique. (Conclusions) This study suggested the folding technique as a way to dimensionalize the Voronoi diagram, and furthermore, experimented with a series of processes of creating a pavilion prototype through digital fabrication. Units produced with the folding technique were connected organically and heightened structural solidity, and the possibility of lightweighting could also be confirmed. This experiment has significance in examining whether it is feasible to build a generative theory of nature by applying the folding technique and is expected to serve as a material in seeking utilization methods of digital fabrication folding techniques in the future.

Support-free hollowing for 3D printing via Voronoi diagram of ellipses

Lee, Mokwon,Fang, Qing,Cho, Youngsong,Ryu, Joonghyun,Liu, Ligang,Kim, Deok-Soo Elsevier 2018 Computer aided design Vol.101 No.-

<P><B>Abstract</B></P> <P>3D printing, also called additive manufacturing, has been increasingly popular and printing efficiency has become more critical. To print artifacts faster with less material, thus leading to lighter and cheaper printed products, various types of void structureshave been designed and engineered inside of shape models. In this paper, we present a novel method for generating support-free elliptic hollowing for 3D shapes which can entirely avoid additional supporting structures. To achieve this, we perform the ellipse hollowing in one of the cross sectional polygons and then extrude the hollowed ellipses to the other parallel cross sections. To efficiently pack the ellipses in the polygon, we construct the Voronoi diagram of ellipses to reason the free-space around the ellipses and other geometric features by taking advantage of the available algorithm for the efficient and robust construction of the Voronoi diagram of circles. We demonstrate the effectiveness and feasibility of our proposed method by designing and printing support-free hollow for various 3D shapes using Poretron, the program which computes the hollow by embedding appropriate APIs of the Voronoi Diagram Machine library that is freely available from Voronoi Diagram Research Center. It takes a 3D mesh model and produces an STL file which can be either fed into a 3D printer or postprocessed.</P> <P><B>Highlights</B></P> <P> <UL> <LI> Support-free elliptic hollowing for 3D shapes via ellipse packing. </LI> <LI> Derivation of a class of support-free ellipses. </LI> <LI> Packing the support-free ellipses within a polygon (a cross-section of a 3D shape). </LI> <LI> Packing the ellipses within a polygon is solved very efficiently and precisely via Voronoi diagram. </LI> </UL> </P> <P><B>Graphical abstract</B></P> <P>[DISPLAY OMISSION]</P>

디지털 환경의 생성적 디자인 특성에 관한 연구 - 행위자 기반모형을 적용한 보로노이 다이어그램(Voronoi Diagram)을 중심으로

구본미 한국기초조형학회 2009 기초조형학연구 Vol.10 No.5

As of the digital feasibility, computer digital technology has surpassed analog’s limitations of expression, area, activity, and has established a basis for actualizing reality through virtual space. As digital technology has become a medium of its own spanning the design process represented by the connection of concept-realization-construction. It ceased to be simple instrumental and is now self-expanding. In the digital-environment-based space design field which deals with a large amount of information, the core of the problem lies in how to apply parameters to the diagram as constituents. At that point, The Voronoi Diagram, possesses the characteristics of a productive design which is based on parameters, was considered. This diagram can be defined as a medium that incorporates as much real information as possible and converts it to reality. The interaction of parameters that influence form generation and space creation exhibits the emergent characteristic that forms the appropriate form of a complex collection. The Voronoi Diagram, however, is still in need of further research on logical methodology as to how to determine the initial reference point. Therefore, an Agent-based System which can simulate Complex Adaptive System for determining the initial reference point was considered. The Agent-based System was reinterpreted to be applied to productive design, and the correlation with the Voronoi Diagram was examined through case studies. The purpose of this research is to examine if the application of an Agent-based System as a parameter to the productive design method. By using Voronoi Diagram is feasible as a logical methodology for determining the initial reference point for Voronoi Diagram. 디지털시대에 접어들면서 디지털 기술은 도구적 역할을 넘어 스스로 형태를 발생시키는 역할을 하고 있다. 생성적 디자인은 공간이 가지는 물리적 고정성의 한계를 극복하고 수많은 정보를 수용하기 위한 시도 중의 하나이다. 본 연구는 생성적 디자인의 도구적 역할을 하는 보로노이 다이어그램을 통한 공간 디자인 프로세스에 주목하였다. 또한 생성적 디자인 수법의 매개변수로 행위자 기반 모형 연구를 적용하여 추후 보로노이 다이어그램의 초기 기준점 선정에 논리적 방법론으로의 가능성을 살펴보았다. 다이어그램은 재현적 역할에서 생성적, 구축적역할로 확장되었다. 이러한 다이어그램의 성격과 보로노이 다이어그램은 증식적 매체로서 연관성을 갖는다. 셀ㆍ버텍스ㆍ스페이스ㆍ폼으로 구성되는 보로노이 다이어그램은 초기 변수 값을 매개로한 수학적 원리를 바탕으로 공간을 만들어낸다. 알고리듬에 의해 만들어진 공간은 자기조직화, 반복적 증식, 진화 공간, 개체간의 상호작용, 심미성, 구조의 안정성, 상향식(Bottom-up)디자인 프로세스의 특징을 갖는다. 행위자 기반 모형은 복잡적응계 연구의 주요한 방법론으로 행위자ㆍ 행위자와 환경 사이 상호작용, 개인주의적 관점, 시뮬레이션에 의한 분석, 창발적 성격, 미시세계와 거시세계를 잇는 교량의 역할을 갖는 특성이 있다. 보로노이 다이어그램을 통한 공간의 특성과 행위자 기반 모형은 상호작용, 상향식 디자인 프로세스 지향, 창발적 성격을 갖는 공통점이 있다. 현재 보로노이 다이어그램을 이용한 공간은 패턴을 외형적 요소로 이용하는 경우가 대부분이다. 앞으로 보로노이 다이어그램의 초기 기준점 선정에 행위자 기반 모형이 적용된다면, 시스템으로서의 공간ㆍ열린 공간으로 다양한 공간 디자인분야에 영향을 줄 수 있을 것이라 기대한다.

보로노이 다이어그램의 경계지점 최소거리 행렬 기반 k-최근접점 탐색 알고리즘

엄정호,장재우 한국공간정보시스템학회 2009 한국공간정보시스템학회 논문지 Vol.11 No.1

Recently, location-based services which provides k nearest POIs, e.g., gas stations, restaurants and banks, are essential such applications as telematics, ITS(Intelligent Transport Systems) and kiosk. For this, the Voronoi Diagram k-NN(Nearest Neighbor) search algorithm has been proposed. It retrieves k-NNs by using a file storing pre-computed network distances of POIs in Voronoi diagram. However, this algorithm causes the cost problem when expanding a Voronoi diagram. Therefore, in this paper, we propose an algorithm which generates a matrix of the shortest distance between border points of a Voronoi diagram. The shortest distance is measured each border point to all of the rest border points of a Voronoi Diagram. To retrieve desired k nearest POIs, we also propose a k-NN search algorithm using the matrix of the shortest distance. The proposed algorithms can minimize the cost of expanding the Voronoi diagram by accessing the pre-computed matrix of the shortest distances between border points. In addition, we show that the proposed algorithm has better performance in terms of retrieval time, compared with existing works. 최근 사용자에게 자신과 가장 가까운 k 개의 주유소, 레스토랑, 은행 등의 POI(Point Of Interest) 정보를 추천해주는 위치 기반 서비스가 텔레매틱스, ITS(Intelligent Transport Systems), 키오스크(kiosk)등의 어플리케이션에서 필요로 하고 있다. 이를 위해, 보로노이 다이어그램 k-최근접점 탐색 알고리즘이 제안되었다. 이는 보로노이 다이어그램에서 각 POI의 네트워크의 거리를 미리 계산한 파일을 이용하여 k-최근접점 탐색을 수행한다. 그러나 이 알고리즘은 보로노이 다이어그램 확장에 따른 비용 문제를 야기한다. 따라서 본 논문에서는 보로노이 다이어그램의 경계지점마다 각각에 대하여 최소거리 행렬을 생성하는 알고리즘을 제안한다. 또한 k 개의 POI를 탐색하기 위해, 최소거리 행렬을 이용한 k-최근접점 탐색 알고리즘을 제안한다. 제안하는 알고리즘은 미리 계산된 경계 지점 간 최소거리 행렬을 통해 탐색하므로, k-최근접점 탐색 시 보로노이 다이어그램의 확장비용을 최소화한다. 아울러 기존 연구와의 성능비교를 통해 제안하는 알고리즘이 기존 알고리즘에 비해 검색시간 측면에서 성능이 우수함을 보인다.

대공위협에 대한 무인기 생존성 최대화 경로점 결정기법

박상혁(Sanghyuk Park),홍주현(Ju-Hyeon Hong),하현종(Hyun-Jong Ha),유창경(Chang-Kyung Ryoo),신원영(Wonyoung Shin) 한국항공우주학회 2014 韓國航空宇宙學會誌 Vol.42 No.2

본 논문은 무인기의 생존성을 최대화하기 위한 경로점을 결정하는 기법을 제안한다. 본 논문에서 초기 경로점을 선정하기 위해 사용된 Voronoi diagram은 위협의 위치와 크기가 주어져 있을 때, 위협으로부터 최대한 멀리 피해서 가는 경로를 계획하는데 많이 이용되고 있는 기법이다. 하지만 위협의 크기가 서로 다르고, 비행경로가 직선경로로 계획되어야 한다면 실제 경로 계획 시 Voronoi diagram으로는 한계가 있다. 본 논문에서는 Voronoi diagram을 통해 선정한 초기 경로점을 위협의 형태에 맞춰 최적화를 수행하는 방식을 적용하였다. 각 경로점의 인접한 경로점들을 고정시킨 상태에서 경로점을 하나씩 최적화를 수행하는 방식으로 최적화를 수행하였다. 이 방식은 전체 경로점들이 수렴할 때 까지 국소최적화를 반복함으로써, 최적의 경로점을 찾기 위해 소요되는 연산시간을 크게 감소시켰다. This paper proposes a determination method of waypoints to maximize the survivability of a UAV. Voronoi diagram which is used for the initial selection of waypoint candidates is the most widely used path planning technique to avoid the threat as far as possible when the location and strength of the threat are given. But if threat strength is different each other and flight path is constrained along with straight lines, Voronoi diagram has limitations in real applications. In this study, the initial waypoints obtained from Voronoi diagram are optimized considering the shape of each threat. Here, a waypoint is optimized while adjacent waypoints are fixed. By repeating this localized optimization until whole waypoints are converged, computation time for finding the best waypoints is greatly reduced.