New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Point to hull distance #59
Comments
On Sun, 2021-07-11 at 17:26 +0000, RENAUD Jean-Pierre (RDI Nancy) wrote:
@cbbarber 's message was:
|
The geometry package can't do what you ask at the moment, but I am now pretty confident that I can adapt the |
Hi David,
Something to watch for with qh_findbestfacet. It performs a directed search if the point is outside of the initial facet. Otherwise, it performs an exhaustive search.
Jean-Pierre's points are known to be outside of the convex hull, so it may be worthwhile to find a facet below the point before calling qh_findbestfacet.
I'd like to find a generic solution. CGAL has methods to reduce the set of candidate facets.
…--Brad
At 09:01 AM 08/29/2021, David C Sterratt wrote:
The geometry package can't do what you ask at the moment, but I am now pretty confident that I can adapt the inhulln() function to do this fairly quickly.
You are receiving this because you were mentioned.
Reply to this email directly, <#59 (comment)>view it on GitHub, or <https://github.com/notifications/unsubscribe-auth/ADDZ7R3JXZOZEBSLFHGXQADT7IVTTANCNFSM5CYQMXLQ>unsubscribe.
Triage notifications on the go with GitHub Mobile for <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675>iOS or <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>Android.
|
Hi David,
For the facet closest to a point, you should call qh_findbestfacet with 'qh_ALL' instead of '!qh_ALL'. That explains your undesired result for 'the point (10, -1)'.
Extract from the documentation of qh_findbestfacet in poly2_r.c
if !bestoutside (!qh_ALL)
returns first facet below point
if point is inside, returns nearest, !upperdelaunay facet
returns:
distance to facet
isoutside set if outside of facet
note:
If inside, qh_findbestfacet performs an exhaustive search
If you know a facet below the point (e.g., 'facetA'), then you do not need the exhaustive search branch of qh_findbestfacet. The replacement code is the first two lines of qh_findbestfacet
bestfacet= qh_findbest(qh, point, facetA,
qh_ALL, !qh_ISnewfacets, qh_NOupper,
bestdist, isoutside, &totpart);
if (*bestdist < -qh->DISTround) {
// report an error, facetA was not below the point.
…--Brad
|
Thanks @cbbarber. However, I've run into a conceptual problem. When a point is above a facet (i.e. the perpendicular to the hyperplane of the facet passing through the point also passes through the facet, then the distance is reported correctly. But when a point is not above a facet, e.g. the point (-2, -2) in the above example, the closest point of the hull is the nearest vertex. But how do we test if a point is above a facet in order to use the distance to the nearest vertex? |
The crucial changes are in this file: 5454978#diff-18d95f23a29dae23e9245ff171c2905184d938e4f109e63072a960f8b10801e0 |
There's a slight misunderstanding. For Qhull 'above' is relative to an interior point of the convex hull. Hyperplanes are oriented so that a point is above a facet if its signed distance to the facet's hyperplane is positive.
More properly, a point is clearly above a facet if the signed distance is greater than roundoff from the facet's outerplane. The outerplane is a positive offset from the facet's hyperplane. A point is clearly outside the convex hull if it is clearly above a facets and all of its neighbors. Nearly coplanar neighbors must be likewise tested. The definition of nearly coplanar neighbor uses empirically derived constants. After multiple merges produce wide facets, this definition may be incorrect, especially near a vertex.
A point is coplanar with a facet if it is neither clearly above nor clearly below the facet. A point is clearly below a facet, if the signed distance is less the facet's innerplane (including roundoff). The innerplane is a negative offset from the facet's hyperplane. The innerplane clearly below all of a facet's vertices.
Given the closest facet for a point, the closest vertex for the point is one of the facet's vertices or one of the vertices of a neighbor that is coplanar with point. Neighbors of a coplanar neighbor likewise need to be tested.
…--Brad
At 04:34 PM 09/04/2021, you wrote:
qh_ALL in qh_findbestfacet seems to work and I've pushed my work so far containing this code.
However, I've run into a conceptual problem. When a point is above a facet (i.e. the perpendicular to the hyperplane of the facet passing through the point also passes through the facet, then the distance is reported correctly. But when a point is not above a facet, e.g. the point (-2, -2) in the above example, the closest point of the hull is the nearest vertex. But how do we test if a point is above a facet in order to use the distance to the nearest vertex?
You are receiving this because you were mentioned.
Reply to this email directly, <#59 (comment)>view it on GitHub, or <https://github.com/notifications/unsubscribe-auth/ADDZ7RY3DM33SKURP7S7LRDUAJ7E7ANCNFSM5CYQMXLQ>unsubscribe.
Triage notifications on the go with GitHub Mobile for <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675>iOS or <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>Android.
|
Would it be possible to add the point to hull distance ?
The text was updated successfully, but these errors were encountered: