Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Calculating minimimum edge to edge distance between large clusters of points

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Calculating minimimum edge to edge distance between large clusters of points


Chronological Thread 
  • From: Sebastien Loriot <>
  • To:
  • Subject: Re: [cgal-discuss] Calculating minimimum edge to edge distance between large clusters of points
  • Date: Thu, 7 Jul 2022 10:07:58 +0200
  • Authentication-results: mail3-smtp-sop.national.inria.fr; spf=None ; spf=Pass ; spf=None
  • Ironport-data: A9a23:2pPhGaPAtia/dhzvrR2XkcFynXyQoLVcMsEvi/4bfWQNrUoghjUEn GdKXz+OaKuJYjf1fN0gOo+/90wG7cDUmtIySXM5pCpnJ55ogZqcVI7Bdi8cHAvLc5adFBo/h yk6QoOdRCzhZiaE/n9BCpC48T8kk/vgqoPUUIYoAAgoLeNfYHpn2EgLd9IR2NYy24DmW1zV4 LsenuWGULOb824sWo4rw/nbwP9flKyaVOQw4zTSzdgS1LPvvyF94KA3fcldHFOkKmVgJdNWc s6YpF2PEsw1yD92Yj+tuu6TnkTn2dc+NyDW4pZdc/DKbhSvOkXe345jXMfwZ3u7hB2npN9Vl tJUp6eaEwE1DKOWssMSbTdHRnQW0a1uoNcrIFC6uM2XilLcKj7in6soA0YxMokVvO1wBAmi9 9RCcGFLPk3F3bjvhu7lIgVvrpxLwM3DJ4cYoHBn0XfcCd4pRJnCR+PB4towMDIY35ARQ6aOP ZZxhTxHSEmbP0V/HlEtCKkSosuM3navfX5FpwfAzUYwyzGLkFYZPKLWGNHac9jPScROlVuDv Urd7mHhC1cbMsaewHyL6BqRavTnmCr6XMcNDuT9+KI0xlKUwWMXBVsdUl7TTeSFZlCWdelQD xIT4zgVh/I06H6lFPPaUCOWvyvR1vIDYOZ4H+o/4QCL76Pb5QeFG2QJJgKtjvR25KfaohR6h je0c8PV6S9H6+LKFCrMnluAhXbjZnhPdD5qiTosFFNdu7HeTJcPYgUjp+uP/Yawh9zxXC7qm nWE8HZ4iLIUgsoGka68+DgrYg5ARLCZHmbZBS2NBgpJCz+Vgqb7OuREDnCFtp59wH6xFAXpg ZT9s5H2ABoyJZ+MjjeRZ+4GAauk4f2IWBWF3wMwRsJ7rW79oi/7FWy13N2YDBc5WirjUW+5C HI/RSsMjHOuFCD3MvMtMtrZ5zoClPG4TYSNug/ogipmO8AtLmdrDQlhYkmf222FraTfufBXB HtvSu71VSxyIf0/klKeHr5BuZd2mH1W7T6MHfjTkkX/uZLDNSX9YepUYDOmMLplhIva+1692 4gEZ6O3J+B3CrKWjt//qt5Nczjn7BETWfjLliCgXrfceVU6QDB9UK65LHFIU9UNopm5X9zgp hmVMnK0AnKm7ZEeAQnVOH1ldp31WpNz8SAyMSA2bASn3nEiZcCk66JGL8k7erwu9epCy/9oT qldK5/QXKgXEjmXqS4AaZTdrZB5cEv5iA+LOR2jamdtcpNlQTvP5dK5LBDk8zMDD3bsuMZn+ ++g2wrXTIAtXQNnCMqKOvujw0ng73cYkeN2GUDPJ4ALKknr9YFrLQ33j+M2c5lcc0WdmmPC2 l/PUxkCpOTLr4sky/XzhPiJ/9WzDu9zPktGBG2Ev7u7MC/t+GD8k4JNVeC/ey+ECDH59aCkU uViz//mNcoBklsX4ZF3FKxmzP5n6tbi++1awwBjECmZZlinEOk7cHyP3M0KqbcUg7EF5025X UWA/tQcMrKMYZu3HFkULQsjT+KCyfBExWWIvKpteB33tH1t4b6KcUROJB3Q2iZTG714bdE+y uA7tc9KtgGy1kgwPtCdgnwG/miANCZbAaAut5VfH5WyzwR3lBdNZpvTDiKw65aKMo0ePk4vK z6SpazDm7UMmRaYIiRrTSDAjbhHmJADmBFW11tedV6HrdzI260s1xpL/DVrEwlYw32rCQ6o1 rSH6qG0GUmPw9usrM1KXmTpBBsYQRPFpAr+zFwGkGCfRE6tPoAIwKvRJs7VlH31MUoFFtSYw F1c4GngWDfuOsr220PenGZ7/uf7Q4UZGhLqwaia8gfsI3X+STXgi66qI2EPrnMLxC/3aFLv/ YFXwQq7VUE32eP8bUH250l2GIn8kCy5GVE=
  • Ironport-hdrordr: A9a23:GKnOV6MnCTthf8BcTuKjsMiBIKoaSvp037BZ7TEWdfUzSL3lqy nOpoVn6faQslwssR4b6LK90cW7MAjhHNtOkPMs1NSZLWzbUQmTXeJfBOLZqlWKexEWtNQtrZ uIG5IeNDSaNykcsS+V2njALz9t+qjizElqv4vjJrVWID2Cp5sO0+6xMGimLnE=
  • Ironport-phdr: A9a23:bCgqyhSezcPnWdwvAM2MtVNBbNpsoiaVAWYlg6HPa5pwe6iut67vI FbYra00ygOTBsOCta4P0rCG+4nbGkU4qa6bt34DdJEeHzQksu4x2zIaPcieFEfgJ+TrZSFpV O5LVVti4m3peRMNQJW2aFLduGC94iAPERvjKwV1Ov71GonPhMiryuy+4ZLebxtGiTanfL9/L Rq7oQrMusUIgoZpN7o8xAbOrnZUYepd2HlmJUiUnxby58ew+IBs/iFNsP8/9MBOTLv3cb0gQ bNXEDopPWY15Nb2tRbYVguA+mEcUmQNnRVWBQXO8Qz3UY3wsiv+sep9xTWaMMjrRr06RTiu8 6FmQwLuhSwaNTA27XvXh9RzgqxVrx2uqQFxzZDaYI+VNvVxYqzTcMgGRWdCRMtdSzBND42+Y oYJEuEPPfxYr474p1YWsBWxGxKjC/n0yj9Uh3/5w6s62PknHwHBxgwgHtUOsGjJp9jyL6cSV ee1zLPJzTXEc/NawzL96IzTfxAupPGDR7Nwcc7LxUYzEAPFi0ydpIr4NDyayuoDqXKU7/Z8V e2xkW4nrRl8rzqyy8oiiITEm4MYxkzZ+Ct3wYs4Kt61RUxmbNO6FJZduCGUOYt0T84mX2xlt yQ3xLMJtJOlYSQHxpopygPbZvGBboOG7BXjVOOLLjd5gnJoYLO/hxCo8Uih0OLwTMe00ExMo yFYkdfMrmgA2wLP5sWDUPdw/Ues1SyR2wzN9+1IO085mKvDJ5Miw7M8jJgevEXZEiPolkj6k rWaelgk9+Wn7ensf6/oqYWGN4BujwHzKqQuldK7AeQ/KgUOWnKU+eW41LH680z5WqhGguQ4k qTWsZ3WP8sbpqm+Aw9a1oYs9QyzACuh0NQdhXUHLVRFdwybj4XxJV3CPPT1Ae28jlmsijtn2 e7KMqD7DpjCL3XPiLLhcqx8605Yxgoz19df55dMB7EaJPLzXVXxtN3fDh8lKQC0xuLnBc5y1 oMbQ22PA6uZPLnOvl+P4+IjO++Ma5QNtzbnN/cl/+LujWM+mVIFYKWlxYEXZ2ygHvR6P0WZZ mLhjcsOEWgQugoyVfHliFyZUTFPenayRLk86yogCIOmCIfDXpqijKaA3Ce9BJ1WZ3pJBkqCE XfyJM25XewRYneSPtN5iW5DEqOwTpcokxCorg7zjbR9afHF/zUR8pPl2t8y7OLakVQ+9Cd/E t+GgFyLVHx+om4YW2o2wLxnuh46jUyS1LBxxf1eD91aof1TFRwrMIbViO18Bde1UQ3IepKFS U2tX869Ug02G9k+yttLb0dmEMi5lTjC2TCrCvkbje+lHpsxp5nR1XHqO8dwzT7i07MgiEVuF tBLMnengbI58gz7CIvAkkHfnKGvI/dPlBXR/XuOmDLd9HpTVxR9BP2ttRE3Y0LXqY+8/UbeV /q1DqxhNAJdyMmEI68Ma9vzjFwASu2wcM/GbTeXnGG9TQ2N2qvKdJDjLn4Z2z/cD1RClgQ78 nOPNAx4DSCk8CrFFDI7LVv0eAv39PVm7nayT0s61QaPOlZl0KC0/QJTgPi0RPYa37ZCsyAk+ H1vBFjo+dXQBpKbohZ5OqVRZdRo+FBcyWfQrBBwJLSlJqFmw0EEKkF54x2o2BJwBYFN18Mtq RvG1SJULqSVmBNEfjKchtXrP6HPb3L15FapYrLX3VfX1JCX/L0O4bI2sQerugbhDUck/3h9t rsdm3KB+pXHChYTWpPtQw428RZ9vbTTfig64cvdy3RtNaC+tjKK1cguAaMpzROpftEXN63hd ke6CMkdHcmpNKovn3CmaxsFOKZZ86t1d8Kqev2a2bK6af56lWHuhmBG7YZhl0OUonAkG6iYg tBfmajeglXUMlW0xE2suc32h41eMDQbH27kjDPhGJYUfapqO4ACFWapJcSzgNR4nZ/kHXBCp zvBTxsL3tGkfR2KYhnzxwpVgA4MpXu9mCykiTlwuz4sp6ubmifJxq6xEXhPcn4OX2RkgVr2d MKvi9cAXU+0KQ0tvBSg7Ef+gaNcoe4sSgubCVcNdC/wIWZ4V6K2vbfXeM9D5qQjtiBPWfi9a 1SXIlLkiyMTyDirX25XxTRgMiqvpo28hBtizmSUMHd0qnPdP8B23xbWotLGF7Zd2T8PRS8wj jeyZBD0JN2u59STi9HGtsixUmugUttYdiyjwY6btSS97HFnGlXlx6H1yoChS1Jjl3Oln9BxH T3FthP9fpXm28HYeap8c09kCUW9o8t2F4dik5ch0ZQZ2HwUnJKQrjIMlWb+N8ke2LqrNiJcA 25WhYSPuU65hh4GTDrB3Y/yW3SDz9E0YtC7ZjhTwSch94VRD7/S6rVYnCxzq17+rATLYPE7k C1OrJlmoHMcnewNvxIgiyuHBbVHV1JcOjbtkAjO6tSWo6BeZWLper+1nhkb/5jpHPSZrwdQV WysMIwmGjVx6dk5NVbk33j664Wic97VJ4F21FXcg1LLiO5bL4g0n/wBiH98OG7zinYizvYyk R1k2Zzp9JjCMWhm+7i1RwJJLjCgLd1G4Snj1OwN+6Tel5DqBJhqHS8HGYflXe79WixHruzpb k6PCGFu8SrdQOuHW1XDtwE+6CiTW5GzayPJeD9Dlo4kHUfFYhQY2VFxPn1yn4ZlRF70gpW5K gEhoGhWvAawqwMQmLw2cUOjAyGP/EHwLW1sAJmHcEgJtEcbuwGMYJbYtqUqT0Q6ttWgtFDfd TDdPl4VSzlPAgvdWRjiJuX8vIGQtbHHWazuaaOJO+zGqPQCBa7XntT2g9cgp3DUcZzRWxsqR /wjhhgZBSE/S5mfwm9fDXRQzn2FbtbH9k3lpGsq/obmoa6tAEW2tMOOE+cAa4wxvUrt0OHYb ajIw38oTFQQnoUFwXuCoFQG9HgVjSwmNzykELBb8DXIULqVgahPSRgSdyJ0MsJMqaM6xAhEf 8DB2Jvz0fZjg/g5Bk0gNxSpk9y1ZcEMP2C2NU/WTEeNOrOcIDTXwsbxKaqiQLxUhe9QulW+o zGeW0PkOz2CkXHuWXXNealUizqHORVFpIynWhNkCGymU8i/LxPnbpl4ijo5xbByjXTPdCYdP TV6b0JRv+iQ4Cdf0ZAdUyRK6ntoK/XBmj7MtbGJbMZL96ExW2IoybE/gjxy0bZe4SBaSeYgn SLTqoUruFS6iqyUzSIhVhNSqzFNjYbNvEN4OKyf+IMTPBSMtB8L82iUDAwH4tV/Ddi68btUz cLOk761LTNq/Nfd/M9aDM/RYpHiUjJpIV/yFTjYARFQByasLn3ajldBneu683SUqt0lsMGpl sZQDLBcU1MxG7URDUEvT7lgaN9nGzgjl7CclssB43Gz+QLQSMtttZfCTvuOAP/rJV5xYpFLY hIJxfXzKoFBb+UTPmRtb1B7mMLBHE+CBbilQwVkZw4w5VpXqT1wEjN11EXiZQegpnQUEKzs9 iM=
  • Ironport-sdr: K+GPtJ1Ucmse2xbA1qGPPlX33DyTV/LpYxGPbA62hNoXbcg+Md/TVGS7kHNbN4Vu4orOy6ljQt zBWwzktqykvSM5llq1/1IdLhaXdN71aGXdY6HDE/TZxf3yG246eOU611Zd61hh2DkGCE2AdigH /vW2jLiQLapMsj48jLxkTd6hxmil5wJSXDIIiBqIpQKVMG9Pn+Qw7q+2hENGqvuKGoc8XcX8RG o8AFO/oazKhe2/f46qaVnk18rm2Dp2FBq16RzzcIapGdfq1LNQu6f1hc/lG+sBK2Jl8utFn4+I lhHtMMuA7dE7kvGeGKAKnHWi

how is it different to the other problem you posted and for which I
gave you an answer?

Best,

Sebastien.

On 7/7/22 03:03, "Scriven, David" ( via cgal-discuss Mailing List) wrote:
I have a problem in which there are 2D planes on which there are thousands of clusters of points (x,y coordinates) - the size of the clusters varies from many tens to many thousands of points and the shapes are variable. For every cluster I have to find the nearest neighbour edge-to-edge distance. My solution so far has been to identify the nearby clusters through their centroids and then do a nearest neighbour search between the  cluster of interest and each cluster that was  identified as nearby. I have to  be able to identify the nearest cluster so I can examine at its properties, so I cannot pool the data.


I can see many ways that this approach could fail - if one doesn't search far enough or if the centroids are very far from the edge of the cluster (imagine two very elongated clusters, one above the other  that have their tips very close but their centroids very far apart).  This sort of scenario becomes more likely when studying the relationship between multi-clusters (clusters of clusters, where the formation is defined by some parameter).


Can someone suggest a rapid, robust and reliable method that could solve this problem?


I was wondering if there was a way to use a Delaunay triangulation on all the points and then, in some way, pick out individual clusters and look at the connections from the edge of that cluster, but it's not obvious to me how to make this work.


David


David Scriven, Ph.D. e-mail : <>Dept Cellular & Physiological Sci. ph: 604-822-7812 <tel:604-822-7812> 2350 Health Sciences Mall, fax: 604-822-2316 <tel:604-822-2316> University of British Columbia, Vancouver, BC. V6T 1Z3, Canada


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss




Archive powered by MHonArc 2.6.19+.

Top of Page