{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T12:53:13Z","timestamp":1753879993978,"version":"3.41.2"},"reference-count":26,"publisher":"ASME International","issue":"1","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["51605290"],"award-info":[{"award-number":["51605290"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003399","name":"Science and Technology Commission of Shanghai Municipality","doi-asserted-by":"publisher","award":["16YF1405500"],"award-info":[{"award-number":["16YF1405500"]}],"id":[{"id":"10.13039\/501100003399","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,3,1]]},"abstract":"<jats:p>Shape matching using their critical feature points is useful in mechanical processes such as precision measure of manufactured parts and automatic assembly of parts. In this paper, we present a practical algorithm for measuring the similarity of two point sets A and B: Given an allowable tolerance \u03b5, our target is to determine the feasibility of placing A with respect to B such that the maximum of the minimum distance from each point of A to its corresponding matched point in B is no larger than \u03b5. For sparse and small point sets, an improved algorithm is achieved based on a sparse grid, which is used as an auxiliary structure for building the correspondence relationship between A and B. For large point sets, allowing a trade-off between efficiency and accuracy, we approximate the problem as computing the directed Hausdorff distance from A to B, and provide a two-phase nested Monte Carlo method for solving the problem. Experimental results are presented to validate the proposed algorithms.<\/jats:p>","DOI":"10.1115\/1.4038968","type":"journal-article","created":{"date-parts":[[2018,1,12]],"date-time":"2018-01-12T20:21:32Z","timestamp":1515788492000},"update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":1,"title":["Circle-Point Containment, Monte Carlo Method for Shape Matching Based on Feature Points Using the Technique of Sparse Uniform Grids"],"prefix":"10.1115","volume":"18","author":[{"given":"Xiangzhi","family":"Wei","sequence":"first","affiliation":[{"name":"Institute of Intelligent Manufacturing and Information Engineering, School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China e-mail:"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Zhao","sequence":"additional","affiliation":[{"name":"Department of Physics and Astronomy, Shanghai Jiao Tong University, Shanghai 200240, China e-mail:"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siqi","family":"Qiu","sequence":"additional","affiliation":[{"name":"Institute of Intelligent Manufacturing and Information Engineering, School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China e-mail:"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"33","published-online":{"date-parts":[[2018,1,31]]},"reference":[{"issue":"5","key":"2019100603422845900_bib1","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1109\/TPAMI.2007.70812","article-title":"Approximate Matching of Digital Point Sets Using a Novel Angular Tree","volume":"31","year":"2009","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"6","key":"2019100603422845900_bib2","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1109\/TPAMI.2010.169","article-title":"Approximately Global Optimization for Robust Alignment of Generalized Shapes","volume":"33","year":"2011","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"3","key":"2019100603422845900_bib3","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0925-7721(94)90004-3","article-title":"Approximate Decision Algorithms for Point Set Congruence","volume":"4","year":"1994","journal-title":"Comp. Geom. Theor. Appl."},{"key":"2019100603422845900_bib4","doi-asserted-by":"crossref","unstructured":"Goodrich, M. T., Mitchell, J. S. B., and Orletsky, M. W., 1994, \u201cPractical Methods for Approximate Geometric Pattern Matching Under Rigid Motion,\u201d Tenth Annual ACM Symposium on Computational Geometry (SCG), Stony Brook, NY, June 6\u20138, pp. 103\u2013112.https:\/\/dl.acm.org\/citation.cfm?id=177424.177572","DOI":"10.1145\/177424.177572"},{"issue":"1","key":"2019100603422845900_bib5","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00453-003-1043-4","article-title":"Combinatorial and Experimental Methods for Approximate Point Pattern Matching","volume":"38","year":"2004","journal-title":"Algorithmica"},{"issue":"2","key":"2019100603422845900_bib6","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0925-7721(02)00095-0","article-title":"Approximate Congruence in Nearly Linear Time","volume":"24","year":"2003","journal-title":"Comp. Geom."},{"issue":"4","key":"2019100603422845900_bib7","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1287\/ijoc.4.4.375","article-title":"Matching Points Into Pairwise-Disjoint Noise Regions: Combinatorial Bounds and Algorithms","volume":"4","year":"1992","journal-title":"ORSA J. Comput."},{"issue":"1","key":"2019100603422845900_bib8","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/BF02187910","article-title":"Congruence, Similarity, and Symmetries of Geometric Objects","volume":"3","year":"1988","journal-title":"Discrete. Comput. Geom."},{"issue":"1","key":"2019100603422845900_bib9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-001-0016-8","article-title":"Geometry Helps in Bottleneck Matching and Related Problems","volume":"31","year":"2001","journal-title":"Algorithmica"},{"key":"2019100603422845900_bib10","doi-asserted-by":"publisher","first-page":"139014","DOI":"10.1155\/2012\/139014","article-title":"Point Pattern Matching Algorithm for Planar Point Sets Under Euclidean Transform","volume":"2012","year":"2012","journal-title":"J. Appl. Math."},{"issue":"16","key":"2019100603422845900_bib11","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1016\/j.ipl.2009.04.021","article-title":"Geometric Pattern Matching for Point Sets in the Plane Under Similarity Transformations","volume":"109","year":"2009","journal-title":"Inf. Process. Lett."},{"issue":"9","key":"2019100603422845900_bib12","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1109\/34.232073","article-title":"Comparing Images Using the Hausdorff Distance","volume":"15","year":"1993","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"12","key":"2019100603422845900_bib13","doi-asserted-by":"publisher","first-page":"1873","DOI":"10.1016\/S0031-3203(98)00076-4","article-title":"Comparing Face Images Using the Modified Hausdorff Distance","volume":"31","year":"1998","journal-title":"Pattern Recognit."},{"key":"2019100603422845900_bib14","doi-asserted-by":"crossref","unstructured":"Jesorsky, O., Kirchberg, K., and Frischholz, R., 2001, \u201cRobust Face Detection Using the Hausdorff Distance,\u201d Third International Conference on Audio- and Video-Based Biometric Person Authentication (AVBPA), Halmstad, Sweden, June 6\u20138, pp. 90\u201395.","DOI":"10.1007\/3-540-45344-X_14"},{"key":"2019100603422845900_bib15","doi-asserted-by":"crossref","unstructured":"Srisuk, S., and Kurutach, W., 2001, \u201cNew Robust Hausdorff Distance-Based Face Detection,\u201d International Conference on Image Processing (ICIP), Thessaloniki, Greece, Oct. 7\u201310, pp. 1022\u20131025.10.1109\/ICIP.2001.959222","DOI":"10.1109\/ICIP.2001.959222"},{"key":"2019100603422845900_bib16","unstructured":"Lu, Y., Tan, C. L., Huang, W., and Fan, L., 2001, \u201cAn Approach to Word Image Matching Based on Weighted Hausdorff Distance,\u201d Sixth International Conference on Document Analysis and Recognition (ICDAR), Seattle, WA, Sept. 10\u201313, pp. 10\u201313.10.1109\/ICDAR.2001.953920"},{"key":"2019100603422845900_bib17","doi-asserted-by":"crossref","unstructured":"Dubuisson, M. P., and Jain, A. K., 1994, \u201cA Modified Hausdorff Distance for Object Matching,\u201d 12th International Conference on Pattern Recognition (ICPR), Jerusalem, Israel, Oct. 9\u201313, pp. 566\u2013568.10.1109\/ICPR.1994.576361","DOI":"10.1109\/ICPR.1994.576361"},{"issue":"3","key":"2019100603422845900_bib18","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BF02189323","article-title":"The Upper Envelope of Voronoi Surfaces and Its Applications","volume":"9","year":"1993","journal-title":"Discrete Comput. Geom."},{"key":"2019100603422845900_bib19","doi-asserted-by":"crossref","unstructured":"Huttenlocher, D. P., Kedem, K., and Kleinberg, J. M., 1992, \u201cOn Dynamic Voronoi Diagrams and the Minimum Hausdorff Distance for Point Sets Under Euclidean Motion in the Plane,\u201d Eighth Annual ACM Symposium on Computational Geometry (SCG), Berlin, June 10\u201312, pp. 110\u2013119.https:\/\/dl.acm.org\/citation.cfm?id=142700","DOI":"10.1145\/142675.142700"},{"issue":"1\u20132","key":"2019100603422845900_bib20","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0925-7721(95)00047-X","article-title":"Geometric Pattern Matching Under Euclidean Motion","volume":"7","year":"1997","journal-title":"Comp. Geom. Theory. Appl."},{"issue":"1","key":"2019100603422845900_bib21","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0031-3203(98)00086-7","article-title":"Efficient Algorithms for Robust Feature Matching","volume":"32","year":"1999","journal-title":"Pattern Recognit."},{"issue":"2","key":"2019100603422845900_bib22","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s00453-007-9059-9","article-title":"Improved Approximation Bounds for Planar Point Pattern Matching","volume":"50","year":"2008","journal-title":"Algorithmica"},{"key":"2019100603422845900_bib23","doi-asserted-by":"crossref","unstructured":"Alt, H., Aichholzer, O., and Rote, G., 1994, \u201cMatching Shapes With a Reference Point,\u201d Tenth Annual ACM Symposium on Computational Geometry (SCG), Stony Brook, NY, June 6\u20138, pp. 85\u201391.https:\/\/dl.acm.org\/citation.cfm?id=177555","DOI":"10.1145\/177424.177555"},{"key":"2019100603422845900_bib24","first-page":"1","article-title":"The Polygon Placement Problem","volume":"1","year":"1983","journal-title":"Adv. Comput. Res."},{"issue":"1","key":"2019100603422845900_bib25","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","article-title":"Optimal Search in Planar Subdivisions","volume":"12","year":"1983","journal-title":"SIAM J. Comput."},{"issue":"74","key":"2019100603422845900_bib26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1531326.1531380","article-title":"Interactive Hausdorff Distance Computation for General Polygonal Models","volume":"28","year":"2009","journal-title":"ACM Trans. Graph."}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4038968\/6101711\/jcise_018_01_011008.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4038968\/6101711\/jcise_018_01_011008.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,29]],"date-time":"2025-06-29T20:42:46Z","timestamp":1751229766000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/doi\/10.1115\/1.4038968\/366483\/CirclePoint-Containment-Monte-Carlo-Method-for"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,31]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.4038968","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"type":"print","value":"1530-9827"},{"type":"electronic","value":"1944-7078"}],"subject":[],"published":{"date-parts":[[2018,1,31]]},"article-number":"011008"}}