단순다각형의 최단 외부가시선분을 구하는 최적 알고리즘

이승용(Seung-Yong Lee),신성용(Sung Yong Shin),좌경룡(Kyung-Yong Chwa) 한국정보과학회 1991 한국정보과학회 학술발표논문집 Vol.18 No.1

다각형 P의 내부를 지나지 않는 선분 L로 부터 P의 경계가 모두 보이면 L을 P의 외부가시선분이라 한다. Shin은 정점이 n개인 다각형 P가 주어졌을 때 P의 외부가시선분이 존재하는 가를 조사하고 존재할 경우 외부가시선분을 구하는 O(nlogn) 시간 알고리즘을 제시하였고 Bhattacharya 등은 다각형의 sector 가시성을 이용하여 같은 문제가 O(n) 시간에 해결됨을 보였다. Bhattacharya와 Toussaint은 주어진 다각형이 정점이 n개인 볼록다각형일 때 최단 외부가시선분을 구하는 O(n) 시간 알고리즘을 제시하였다. 본 논문에서는 정점이 n개인 단순다각형 P가 주어졌을 때 P의 최단 외부가시선분을 구하는 O(n) 시간 알고리즘을 제시한다.

MultiSIM을 이용한 심전도 모듈의 설계

신성용(Sung-Yong Shin),최현식(Hyun-Sik Choi) 대한전자공학회 2018 대한전자공학회 학술대회 Vol.2018 No.11

MultiSIM is a circuit design software that visualizes and analyzes electronic circuit behavior. This paper designs the ECG module using MultiSIM and we build and validate the circuit through a bread board. The designed ECG circuit consists of an instrumentation amplifier, a notch filter, a high pass filter and a low pass filter. This module used the instrumentation amplifier INA129 and the OP amplifier LM358 and operates in the band from 0.5Hz to 150 Hz.

A Time and Space Efficient Algorithm for VLSI Geometrical Rule Checking

정자춘,신성용,이현찬,이철동,유영욱,Jeong, Ja-Choon,Shin, Sung-Yong,Lee, Hyun-Chan,Lee, Chul-Dong,Yu, Young-Uk 대한전자공학회 1989 전자공학회논문지 Vol. No.

기하학적인 마스크 설계도면에서 최소폭/간격을 효과적으로 검증하기 위한 새로운 알고리듬을 제안한다. 제안된 알고리듬은 영역탐색문제를 평면소인법을 사용하여 순서적으로 해결하고 있다. 이 알고리듬은 O(n log n)의 시간복잡도를 가지는데, 모든 최소폭/간격의 위반을 보고하는 문제에 있어서 시간복잡도의 lower bound가 ${\Omega}$(n log n)이기때문에 이론적으로 최적이다. 여기서, n은 마스크 패턴에서의 edge의 총 수 이다. 그리고, O($n^{0.5}$)의 공간복잡도를 가지므로 실제적으로 매우 빠르다. 그리고 종래의 알고리듬에 비해 간단하므로 이해하기 용이하고 구현하기가 편리한 장점이 있다. 이 알고리듬은 VAX8650 컴퓨터에서 C-언어로 구현되었으며 직교영역에서 25만개의 정점 데이타에 대해서 116.7초내에 처리했다. A new algorithm is presented which efficiently reports minimum width/space violation in a geometric mask pattern. The proposed algorithm solves a sequence of range search problems by employing a plane sweep method. The algorithm runs in O(n log n) time, where n is the number of edges in a mask pattern. Since a lower bound in time conplexity for reporting all minimum width/space violations is ${\Omega}$ (n log n), this algorithm is theoretically optimal within a constant multiplicaive factor. It requires O($n^{0.5}$) space which is very efficient in practice. Moreover, this algorithm, we believe, is easy to implement and practically fast (116.7 seconds for a rectilinear region with 250000 vertices ar VAX 8650.)

단순 다각형을 경비하는 대각 경비원 배치 알고리즘

김대승(Dae-sung kim),신성용(Sung-Yong Shin),좌경룡(Kyung-Yong Chwa) 한국정보과학회 1991 한국정보과학회 학술발표논문집 Vol.18 No.1

대각 경비원은 변이나 대각선을 따라서 이동 가능한 경비원이다. O'Rourke은 [n/4] 명의 대각 경비원이 n개의 정점을 갖는 단순 다각형 P를 경비할 수 있음을 증명하였다. 본 논문은 P를 경비할 수 있는 [n/4] 이하의 대각 경비원의 위치를 찾아주는 선형 시간 알고리즘을 제시한다. 이 알고리즘의 기본 방향은 삼각 분할을 이용하여 P를 [n/4] 다각형들로 나눈 후, 각 삼각형을 경비하는 한 명의 대각 경비원의 위치를 결정하여 주는 것이다.

회전각 보간에 기반한 실시간 인체 변형

신승협(Seunghyup Shin),신성용(Sung-Yong Shin) 한국정보과학회 2000 한국정보과학회 학술발표논문집 Vol.27 No.1B

최근 실시간 가상 인물 애니메이션 시스템이 활발하게 보급되면서 피부 모양을 자연스럽게 유지하면서도 고속으로 동작할 수 있는 인체 변형 방법이 요구되고 있다. 본 논문은 가상 인물을 구성하는 메쉬의 정점들을 회전 연산만으로 이동시켜 실시간에 인체를 변형하는 모델을 제안한다. 인체 변형의 전처리 과정으로 드로니 삼각화를 이용하여 각 정점의 회전 기준이 될 관절을 찾는 방법을 제시하고, 사원수 형태로 입력된 동작을 회전축의 방향에 따라 분해한 후 각 정점에 차등적으로 적용하여 피부를 자연스럽게 변형할 수 있음을 보인다.

삼차원 제조성에 응용할 수 있는 다면체 단조성의 특성화

하종성(Jong-Sung Ha),신성용(Sung-Yong Shin) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.11

본 논문에서는 조립 계획, 계층적 제조, 몰드 설계에서 발생하는 삼차원 모델의 세 가지 제조성을 결정하는 기하적 문제를 고려한다. 제조성이 본래 기하적인 특성을 지녔으므로 다음과 같은 사실들을 이용함으로써 이 문제들을 다면체의 단조성이라는 일원화된 개념으로 형식화할 수 있다. 두 부품의 분해성 문제에서 강단조성은 분해 방향의 충분 조건이 된다. 계층적 제조에서는 약단조 방향이 모델의 셋업 방향을 위한 적합한 방향이 된다. 또한 분리단조 방향은 두 몰드 판의 분리성을 위한 필요충분 조건이 된다. 다면체의 모든 강단조 방향은 그 다면체의 볼록헐과 대응되는 디피션시 면들의 수직벡터들을 가우시안사상하여 o(nklogk+nlogn) 시간에 결정할 수 있다. 여기서 n은 k는 각각 다면체를 구성하는 면과 디피션시의 갯수이다. 단조 포켓만을 가지는 다면체의 경우 약단조와 분리단조를 위한 모든 방향도 강단조성과 유사하게 같은 시간 한계안에서 구할 수 있다. In this paper, we consider three geometric problems for determining the manufacturability of 3D models, that arise in assembly planning, layered manufacturing, and mould injection. Due to the inherent geometric nature of manufacturability, we are able to formulate those problems under the unified notion of monotonicity, by exploiting the following facts: For the disassemblability problem for a pair of parts, strong monotonicity gives a sufficient condition to disassemble; a weakly-monotone direction is a desirable direction for setting up a model in layered manufacturing; moreover, a separably-monotone direction is a sufficient and necessary condition for the separability of a pair of plates in mould injection. All strongly monotone directions of a polyhedron can be determined in o(nklogk+nlogn) time by using Gaussian map of the normal vectors of deficiency faces with respect to the convex hull of the polyhedron, where n and k are the number of all faces and that of deficiency faces, respectively. When a polyhedron has only monotone pockets, all weakly- and separably-monotone directions can similarly be obtained within the same time bound.

2019 식품소비행태조사 기초분석보고서

김상효(Kim Sang-Hyo),이계임(Lee Kyei-im),허성윤(Heo Seong-yoon),최재현(Choi Jae-Hyun),신성용(Shin Seong-Yong),박인호(Park In-ho) 한국농촌경제연구원 2019 한국농촌경제연구원 기타연구보고서 Vol.- No.-

원형 가시 영역을 구하는 알고리즘

김대승(Dae-Sung Kim),신성용(Sung-Yong Shin),좌경룡(Kyung-Yong Chwa) 한국정보과학회 1991 한국정보과학회 학술발표논문집 Vol.18 No.2

다각형 P 내부의 두 점을 연결하는 원호가 P에 포함되는 것이 존재하면 그 두 점이 서로 원형 가시가능하다고 한다. 본 논문에서는 원형 가시성의 기본적인 문제로써 n개의 정점으로 이루어진 단순 다각형 P와 그 내부의 한 점 u가 주어져 있을 때, u로 부터 원형 가시가능한 영역을 구하는 선형 시간 알고리즘을 제시한다.

삼차원 부품 분해성과 기계가공성에서 최적 방향을 결정하는 선형시간 알고리즘

하종성(Jong-Sung Ha),최승학(Seung-Hak Choi),좌경룡(Kyung-Yong Chwa),신성용(Sung-Yong Shin) 한국정보과학회 1996 정보과학회논문지 : 시스템 및 이론 Vol.23 No.10

본 논문에서는 제조와 관련된 두 문제로서 3차원 부품의 분해성과 표면의 (기계)가공성을 고려 한다. 전자는 주어진 3차원 조립체에서 한 부품을 분리할 수 있는 방향을 찾는 것이고, 후자는 NC 기계도구로 주어진 표면을 접근할 수 있는 방향을 찾는 것이다. 이 문제들은 선형부동식 시스템을 사용하여 일원화된 형식으로 표현된다. 이 형식화를 2차원 선형분리성 문제로 변환하여 가능한 방향을 O(n) 시간에 찾을 수 있음을 보인다. 여기에서 n은 면의 갯수이다. 또한 최소포함구 문제로 변환하여 3차원 표면의 수직벡터 와의 최대각을 최소화하는 최적방향을 O(n) 시간에 찾는 알고리즘을 제시한다. In this paper, we consider two manufacturing-related problems 3D part disassemblability and surface machinability. The former is to find a feasible direction along which a part can be separated from a given 3D assembly, and the latter is to find a feasible direction in which an NC machining tool can approach a given surface. These problems are described as a unified formulation using a system of linear inequalities. We also show that a feasible direction can be found in O(n) time by transforming the formulation into the 2D linear separability problem, where n is the number of faces. Furthermore, by transforming the formulation into the smallest enclosing sphere problem, an O(n) time algorithm is proposed to find the optimal direction, i.e., the direction minimizing the maximum angle to the normal vectors of 3D surfaces.

4축 및 5축 기계가공성에서 구상의 밴드를 이용한 최적 방향의 결정

하종성(Jong-Sung Ha),신성용(Sung-Yong Shin) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.12

설계된 삼차원 표면을 수치제어(NC) 기계로 가공하려면 공구가 그 표면에 접근할 수 있는 방향을 결정해야 한다. 이러한 것을 기계가공성 문제라 한다. 본 논문에서는 여러 기계가공성 문제를 원으로 경계지워진 구상의 영역인 도메인이 주어진 점의 집합을 포함하는지 결정하는 구상의 기하적인 문제로 형식화한다. 도메인은 기계가공 환경으로부터 사상되는 반면에 점의 집합은 표면의 수직벡터들로부터 사상 된다. 본 논문에서는 특히 4축 및 5축의 기계가공성 문제를 밴드 도메인의 포함 문제로 형식화하여 해결한다. o(n) 시간에 그 가능성을 점검하는 방법이 제시된다. 찾아진 방향은 가공후 남는 cusp의 높이를 고려할 때 최적의 방향임을 증명한다. In order to manufacture a designed 3D surface with an NC machine, we should determine a feasible direction along which the machining tool can approach the surface. This is called the machinability problem We formulate various machinability problems into geometric problems on the sphere; determine whether a domain, which is a spherical region bounded by circles, can contain a given set of points on the sphere. Domains are mapped from machining environments, while the set of points are mapped from the surface normals. Especially in this paper, we solve 4- and 5-axis machinability problems, which are commonly formulated as the containment problem of a band domain. A method is presented for checking the feasibility in o(n) time, where n is the number of points on the sphere. The found direction is proved to be optimal for minimizing the cusp height resulting from machining.