CONVEX HULL 알고리즘 개발

이진성(Jin Sung Lee),박정수(Jung-Soo Park),이영신(Young Shin Lee) 대한기계학회 2010 대한기계학회 춘추학술대회 Vol.2010 No.3

Smoothed Particle Hydrodynamics(입자완화 유동법)는 고속 충돌시 발생되는 대변형 문제를 효율적으로 계산하기 위하여 연구되고 있는 무요소 수치해석 방법중의 하나로서 해석의 정확성을 높이기 위해서는 주변입자(neighbour particle)의 선택이 매우 중요하다. 이에 본 연구에서는 기존에 많이 사용되었던 방법에서 발생되는 문제점을 보완할 수 있는 새로운 형태의 neighbour particle 선택방법인 convex hull 알고리즘에 대하여 연구하였다. 연구된 convex hull 알고리즘의 구성내용은 생성된 입자에 대하여 각각의 입자들에 대한 주변의 candidate neighbour particle set(이웃입자 후보군)을 지정하고 이들을 inverse mapping을 통하여 convex hull을 이루도록 새로운 공간으로 투영시킨 후 convex hull을 구성하는 최외곽점을 찾으면 이들이 가장 근접되어 있는 neighbour particle이 되며 이러한 과정들을 작성된 프로그램을 통하여 실제 문제에 적용해 보았으며 본 연구에서 개발된 convex hull 알고리즘은 앞으로 수행될 SPH 해석방법 연구에서 neighbour particle을 선택하는 방법으로 적용이 기대된다. SPH(Smoothed Particle Hydrodynamics) is a grid less Lagrangian technique that is useful as an alternative numerical analysis method used to analyze high deformation problems as well as astrophysical and cosmological problems. In SPH, All points within the support of the kernel are taken as neighbours. The accuracy of the SHP is highly influenced by the method for choosing neighbours from all particle points considered. Typically a linked-list method or tree search method has been used as an effective tool because of its conceptual simplicity, but these methods have some liability in anisotropy situations. In this study, convex hull algorithm is presented as an improved method to eliminate this artifact. A convex hull is the smallest convex set that contains a certain set of points or a polygon. The selected candidate neighbours set are mapped into the new space by an inverse square mapping, and extract a convex hull. The neighbours are selected from the shell of the convex hull. This algorithm is proved by Fortran programs. The program is expected to use as a searching algorithm in the future SPH program development.

평면 점집합에서 정렬을 고려한 개선된 컨벡스 헐 알고리즘

박병주,이재흥,Park, Byeong-Ju,Lee, Jae-Heung 한국전기전자학회 2013 전기전자학회논문지 Vol.17 No.1

본 연구에서는 임의의 정렬되지 않은 점집합에서 정렬을 고려한 개선된 Convex Hull 알고리즘을 제안한다. 이 알고리즘은 Convex Hull의 극점 특성을 이용하여 처리 데이터를 한정하기 때문에 계산복잡도가 낮다. 각 단계마다 볼록 정점을 판별하는 조건을 이용하여 한 번의 스캔으로 완전한 Convex Set을 구한다. 알고리즘 초기에 점집합의 정렬이 필요한데, 이때 걸리는 시간이 알고리즘 전체 동작시간의 대부분을 차지하기 때문에 값과 인덱스를 대치하여 빠르게 정렬하였다. 일반적인 상황을 가정하여 랜덤한 점집합으로 알고리즘의 동작시간을 측정하였으며 기존의 알고리즘에 비해 약 두 배의 속도 향상이 있음을 확인하였다. In this paper, we suggest an improved Convex Hull algorithm considering sort in plane point set. This algorithm has low computational complexity since processing data are reduced by characteristic of extreme points. Also it obtains a complete convex set with just one processing using an convex vertex discrimination criterion. Initially it requires sorting of point set. However we can't quickly sort because of its heavy operations. This problem was solved by replacing value and index. We measure the execution time of algorithms by generating a random set of points. The results of the experiment show that it is about 2 times faster than the existing algorithm.

Independence and maximal volume of d-dimensional random convex hull

Son, Won,Park, Seongoh,Lim, Johan The Korean Statistical Society 2018 Communications for statistical applications and me Vol.25 No.1

In this paper, we study the maximal property of the volume of the convex hull of d-dimensional independent random vectors. We show that the volume of the random convex hull from a multivariate location-scale family indexed by ${\Sigma}$ is stochastically maximized in simple stochastic order when ${\Sigma}$ is diagonal. The claim can be applied to a broad class of multivariate distributions that include skewed/unskewed multivariate t-distributions. We numerically investigate the proven stochastic relationship between the dependent and independent random convex hulls with the Gaussian random convex hull. The numerical results confirm our theoretical findings and the maximal property of the volume of the independent random convex hull.

A NOTE ON PRECONVEXITY SPACES

Min, Won-Keun The Honam Mathematical Society 2007 호남수학학술지 Vol.29 No.4

In this paper, we introduce the concepts of the convexity hull and co-convex sets on preconvexity spaces. We study some properties for the co-convexity hull and characterize c-convex functions and c-concave functions by using the co-convexity hull and the convexity hull.

Fuzzy Color Classifier 와 Convex-hull을 사용한 얼굴 검출

박민식,박창우,김원하,박민용,Park, Min-Sik,Park, Chang-U,Kim, Won-Ha,Park, Min-Yong 대한전자공학회 2002 電子工學會論文誌-SP (Signal processing) Vol.39 No.2

본 논문에서는 복잡한 배경에서의 얼굴 추출 방법을 제안한다. 제안된 알고리즘은 적응 퍼지 색 분할기법을 사용하여 얼굴색과 머리색을 분할시킨다. 얼굴색 분포는 Y,Cb,Cr 색 공간내에서 유도되어지고, 조명값에 적응적인 퍼지 시스템을 사용하여 얼굴색을 구분해낸다. 머리색은 RGB 색 공간내에서 구분되어진다. 전처리 과정을 거쳐 추출되어진 얼굴색과 머리색 영역에 컨벡스 헐을 적용하여 그들의 관계를 통해 최종적인 얼굴 영역이 추출되어진다. 제안된 방법은 기존의 패턴 매칭 방법에 비해 효율적인 성능을 나타낸다. 제안된 알고리즘의 유효성을 실험을 통해 증명하며, 색 영역에서의 제한 조건 없이 성공적으로 얼굴 영역을 추출해 냄을 알 수 있다. This paper addresses a method to automatically detect out a person's face from a given image that consists of a hair and face view of the person and a complex background scene. Out method involves an effective detection algorithm that exploits the spatial distribution characteristics of human skin color via an adaptive fuzzy color classifier (AFCC), The universal skin-color map is derived on the chrominance component of human skin color in Cb, Cr and their corresponding luminance. The desired fuzzy system is applied to decide the skin color regions and those that are not. We use RGB model for extracting the hair color regions because the hair regions often show low brightness and chromaticity estimation of low brightness color is not stable. After some preprocessing, we apply convex-hull to each region. Consequent face detection is made from the relationship between a face's convex-hull and a head's convex-hull. The algorithm using the convex-hull shows better performance than the algorithm using pattern method. The performance of the proposed algorithm is shown by experiment. Experimental results show that the proposed algorithm successfully and efficiently detects the faces without constrained input conditions in color images.

다방향 선형 스캐닝과 컨벡스 헐을 이용한 아무르불가사리의 특징 추출

신현덕(Hyun-Deok Shin),전영철(Young-Cheol Jeon) 한국컴퓨터정보학회 2011 韓國컴퓨터情報學會論文誌 Vol.16 No.3

패턴을 이용한 불가사리 특징 검출은 불가사리의 오목 특징과 볼록 특징을 모두 검출하기 어려우며 또한, 오목과 볼록을 구분 할 수도 없다. 오목과 볼록은 아무르불가사리의 중요한 구조적 특징으로서 반드시 찾아야 할 특징이며 오목과 볼록을 분류함으로서 차후 불가사리 인식에서도 필요하다. 따라서 본 논문에서는 아무르불가사리의 주요 특징인 오목과 볼록 특징을 추출하는 기법을 제안한다. 이 기법은 다방향 선형 스캐닝을 이용하여 오목과 볼록의 특징점 후보군을 형성하고 이 후보군에서 특징점을 결정한 후 추출된 특징점에 컨벡스 헐 알고리즘을 적용하여 오목 특징과 볼록 특징을 구분한다. 제안한 기법은 불가사리의 주요 특징인 오목 특징과 볼록 특징을 구분하여 효과적으로 추출한다. 따라서 향후 불가사리 인식을 위한 연구에 기여할 것으로 기대한다. The feature extraction of asterias amurensis by using patterns is difficult to extract all the concave and convex features of asterias amurensis nor classify concave and convex. Concave and convex as important structural features of asterias amurensis are the features which should be found and the classification of concave and convex is also necessary for the recognition of asterias amurensis later. Accordingly, this study suggests the technique to extract the features of concave and convex, the main features of asterias amurensis. This technique classifies the concave and convex features by using the multi-directional linear scanning and form the candidate groups of the concave and convex feature points and decide the feature points of the candidate groups and apply convex hull algorithm to the extracted feature points. The suggested technique efficiently extracts the concave and convex features, the main features of asterias amurensis by dividing them. Accordingly, it is expected to contribute to the studies on the recognition of asterias amurensis in the future.

유전자 알고리즘 교차연산자에 convex hull적용

홍의선,박유석,김병재 明知大學校 産業技術硏究所 2002 産業技術硏究所論文集 Vol.21 No.-

The Traveling Salesman Problem, a kind of sequencing problem, finds the shortest cost and fastest tour of visiting every given city exactly once and returning the starling point. Recently, to improve Genetic Algorithm which is one of methods to solve TSP and to efficiently searching space use convex hull during generating initial tour. In this paper, we adopt convex hullo to generate initial tour and crossover process. The result shows the using convex hull at the GA presents better solutions during same generation and repetition.

A PARALLEL ALGORITHM FOR CONSTRUCTING THE CONVEX-HULL OF A SIMPLE POLYGON

Min, Young-Sik,Lee, Kyeong-Sin 한국전산응용수학회 1999 Journal of applied mathematics & informatics Vol.6 No.1

Given n points in the plane the planar convex hull prob-lem in that of finding which of these points belong to the perimeter of the smallest convex region (a polygon) containing all n points. Here we suggest two kinds of methods. First we present a new sequential method for constructing the pla-nar convex hull O(1.5n) time in the quadratic decision tree model. Second using the sequential method we suggest a new parallel algo-rithm which solve the planar convex hull O(1.5n/p) time on a maspar Machine (CREW-PRAM) with O(n) processors. Also when we run on a maspar Machine we achieved a 37. 156-fold speedup with 64 pro-cessor.

컨벡스 헐을 이용한 개선된 구 좌표계 기반 렌더링 방법

김남중(Kim, Nam-Jung),홍현기(Hong, Hyun-Ki) 한국게임학회 2010 한국게임학회 논문지 Vol.10 No.1

본 논문에서는 컨벡스 헐을 이용한 구 좌표계 기반 실시간 렌더링 알고리즘이 제안되었다. OpenGL 렌더링 파이프라인은 물체의 모든 정점들을 고려하지만, 제안된 방법은 물체의 가시 삼각형들을 검사하여 보이는 정점들만을 고려한다. 본 논문에서는 구좌표계 표현에서의 물체의 가시 영역을 결정하기 위하여, 카메라 절두체를 이루는 6개의 평면 방정식과 물체의 경계구와의 기하 관계를 이용한다. 또한 대상 물체의 컨벡스 헐(convex hull)의 최대 측면 성분(maximum side factor)을 고려하여 은면(hidden surface)을 제거하는 효과적인 방법이 구현되었다. 실험결과로부터 결과 영상이 원본 영상과 거의 같고, 렌더링 성능이 크게 개선됐음을 확인하였다. This paper presents a novel real-time rendering algorithm based on spherical coordinate system of the object using convex hull. While OpenGL rendering pipeline touches all vertices of an object, the proposed method takes account the only visible vertices by examining the visible triangles of the object. In order to determine the visible areas of the object in its spherical coordinate representation, the proposed method uses 3D geometric relation of 6 plane equations of the camera frustum and the bounding sphere of the object. In addition, we compute the convex hull of the object and its maximum side factors for hidden surface removal. Simulation results showed that the quality of result image is almost same compared to original image and rendering performance is greatly improved.

Computing minimum-area rectilinear convex hull and L-shape

Bae, S.W.,Lee, C.,Ahn, H.K.,Choi, S.,Chwa, K.Y. Elsevier 2009 Computational Geometry Vol.42 No.9

We study the problems of computing two non-convex enclosing shapes with the minimum area; the L-shape and the rectilinear convex hull. Given a set of n points in the plane, we find an L-shape enclosing the points or a rectilinear convex hull of the point set with minimum area over all orientations. We show that the minimum enclosing shapes for fixed orientations change combinatorially at most O(n) times while rotating the coordinate system. Based on this, we propose efficient algorithms that compute both shapes with the minimum area over all orientations. The algorithms provide an efficient way of maintaining the set of extremal points, or the staircase, while rotating the coordinate system, and compute both minimum enclosing shapes in O(n<SUP>2</SUP>) time and O(n) space. We also show that the time complexity of maintaining the staircase can be improved if we use more space.