TY - JOUR
T1 - An improved star test for implicit polynomial objects
AU - Fang, Lincong
AU - Michelucci, Dominique
AU - Foufou, Sebti
N1 - Funding Information:
The work is supported by National Natural Science Foundation of China ( 61100084 , 61202197 , 61272300 ), Zhejiang Provincial Natural Science Foundation of China ( LQ13F020003 , LY15F020014 ), Zhejiang Province Department of Education Fund ( Y201223321 ), and China Scholarship Council .
Publisher Copyright:
© 2015 Elsevier Ltd. All rights reserved.
PY - 2016/1/1
Y1 - 2016/1/1
N2 - For a given point set, a particular point is called a star if it can see all the boundary points of the set. The star test determines whether a candidate point is a star for a given set. It is a key component of some topology computing algorithms such as Connected components via Interval Analysis (CIA), Homotopy type via Interval Analysis (HIA), etc. Those algorithms decompose the input object using axis-aligned boxes, so that each box is either not intersecting or intersecting with the object and in this later case its center is a star point of the intersection. Graphs or simplicial complexes describing the topology of the objects can be obtained by connecting these star points following different rules. The star test is performed for simple primitive geometric objects, because complex objects can be constructed using Constructive Solid Geometry (CSG), and the star property is preserved via union and intersection. In this paper, we improve the method to perform the test for implicit objects. For a primitive set defined by an implicit polynomial equation, the polynomial is made homogeneous with the introduction of an auxiliary variable, thus the degree of the star condition is reduced. A linear programming optimization is introduced to further improve the performance. Several examples are given to show the experimental results of our method.
AB - For a given point set, a particular point is called a star if it can see all the boundary points of the set. The star test determines whether a candidate point is a star for a given set. It is a key component of some topology computing algorithms such as Connected components via Interval Analysis (CIA), Homotopy type via Interval Analysis (HIA), etc. Those algorithms decompose the input object using axis-aligned boxes, so that each box is either not intersecting or intersecting with the object and in this later case its center is a star point of the intersection. Graphs or simplicial complexes describing the topology of the objects can be obtained by connecting these star points following different rules. The star test is performed for simple primitive geometric objects, because complex objects can be constructed using Constructive Solid Geometry (CSG), and the star property is preserved via union and intersection. In this paper, we improve the method to perform the test for implicit objects. For a primitive set defined by an implicit polynomial equation, the polynomial is made homogeneous with the introduction of an auxiliary variable, thus the degree of the star condition is reduced. A linear programming optimization is introduced to further improve the performance. Several examples are given to show the experimental results of our method.
KW - Geometric modeling
KW - Implicit objects
KW - Star test
KW - Star-shaped
UR - http://www.scopus.com/inward/record.url?scp=84942499740&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84942499740&partnerID=8YFLogxK
U2 - 10.1016/j.cad.2015.07.005
DO - 10.1016/j.cad.2015.07.005
M3 - Article
AN - SCOPUS:84942499740
VL - 70
SP - 161
EP - 170
JO - CAD Computer Aided Design
JF - CAD Computer Aided Design
SN - 0010-4485
ER -