Compute min/max distance between two GeometryQuery objects

[dassaf4]

This is a Civil iTwin user request for reporting min/max distance between points/linestrings/polyfaces.

See this video re: user request for max distance, as reported on Yammer: https://web.yammer.com/main/org/bentley.com/threads/eyJfdHlwZSI6IlRocmVhZCIsImlkIjoiMjM1MzY3OTA1NjI0MDY0MCJ9

Existing logic:

• Civil mesh-mesh O(n^2) close approach code (using async, Promise).
• native geomlibs:
  • pf_SearchContext.cpp DoPointPickXY for fast projection to mesh along z-vec.
  • SearchClosestApproachToLinestring (PolyfaceVisitorSearch.cpp) - does not use range speedup

[dassaf4]

Idea for initial framework: stroke both input GeometryQuery objects to LineString3d/IndexedPolyface so that the problem reduces to computing discretized min/max distance between meshes, linestrings, or one of each.

Later refinements can include exact computations to avoid stroking (where possible), and speedups to avoid the O(n^2) complexity.

Min Distance (port existing code from imodel-native): https://github.com/iTwin/itwinjs-core/pull/6181

• For mesh-mesh:
  • [x] Port PolyfaceQuery::SearchClosestApproach in PolyfaceVisitorSearch.cpp (with substantial support code in polygon3d.cpp).
• For mesh-linestring:
  • [x] Port PolyfaceQuery::SearchClosestApproachToLinestring in PolyfaceVisitorSearch.cpp.
• For linestring-linestring:
  • [x] Port PolylineOps::AddCloseApproaches in DPoint3dOpsRangeHeap.cpp
  • Note that this can be used for a new 3D close approach API for iTwin along the lines of CurveCurve::CloseApproach.

Max Distance:

• This is an ill-posed problem, but we can solve certain definitions of max distance with simplifying assumptions.
• Definitions:
  • MicroStation's Measure Distance tool with Maximum Between method computes the largest distance between any two points of the objects in 3D or in a plane. This doesn't seem useful.
  • Hausdorff distance is a mathematical measure of the max distance between objects, defined as the larger of the largest minimum distances over all points of one object to the other. This measure works even for overlapping objects, is simple (if expensive) to compute, and doesn't require additional input from the user. Doesn't seem very useful either (it is traditionally used as a measure of how far an object has been perturbed).
  • According to the video, the user seems to be requesting max distance between the nearest surfaces of two objects as seen from above. (The presumed application is estimating pedestrian flow through the corridor.) Call this modification Restricted Hausdorff distance. Specifically, it is 2D Hausdorff distance between the objects' nearest xy-silhouettes. In the following, we will use this restricted version of Hausdorff for max distance.
• A note on "nearest":
  • If the projection segment of a point of object A has an interior xy-intersection with a linestring of object A ("is obstructed"), then Restricted Hausdorff ignores that projection distance. This is because that point is not on the nearest xy-silhouette, so by definition, it doesn't contribute to the computation.
  • Thus, for a given point, only the smallest unobstructed close approach segment contributes its length to the "max of the mins" for Restricted Hausdorff. This is common for loops: the projections from points on the half of loopA further from objectB are likely to be obstructed by the nearer half of loopA.
  • But we cannot just split a silhouette loop to consider only its nearest half. For one thing, how do you define "nearer" if the objects aren't separated by a plane? In general, if we consider the totality of close approaches of point A to object B, it is possible that the smallest-length close approach (the projection) is obstructed, while the next further close approach is unobstructed, and would contribute. This has implications for how we compute point-linestring minimum distance.
  • Conclusion: if we further restrict the definition of Restricted Hausdorff to ignore the contribution of any point whose projection is obstructed, we can use an out-of-the-box point-linestring xy-closest approach method.
• Assumptions:
  • We need a Plane3d in which to measure xy-distances.
  • User to provide a view/plane, or default to top view/xy-plane.
  • Rotate the two objects into the local coordinates of this plane so we can ignore z.
• For mesh-mesh (and mesh-linestring):
  • Compute the mesh xy-silhouettes and boundary edges with PolyfaceQuery.collectSilhouetteEdges and PolyfaceQuery.collectBoundaryEdges (added in https://github.com/iTwin/itwinjs-core/pull/6168). The returned curves are chains of xy-linestrings. Reduce to one linestring by constructing the largest outer negative xy-area loop from these chains with RegionOps.constructAllXYRegionLoops. The idea is to reduce mesh cases to xy-linestring-linestring.
• For linestring-linestring:
  • For each vertexA compute the (unobstructed) closest approach to linestringB, and remember the largest distance maxA.
  • The new LineString3dRangeContext.searchForClosestPoint can return several close approaches within a given max distance. These projection segments can be examined for interior intersection with linestringA, and thrown out if so obstructed, so that vertexA contributes an unobstructed closest approach.
  • Alternatively, as a simplification, just compute the (single) closest approach of vertexA to linestringB, and skip updating maxA if the projection segment is obstructed.
  • Swap linestrings and compute maxB.
  • The Restricted Hausdorff distance between the linetrings is max(maxA, maxB).

[dassaf4]

Min distance with range tree speedup: https://github.com/iTwin/itwinjs-core/pull/6181