search

LLNL / axom

CS infrastructure components for HPC applications
BSD 3-Clause "New" or "Revised" License
152 stars 27 forks source link

Fast closest_point operator for Quadrilateral and/or Polygon #1342

Open adayton1 opened 4 months ago

adayton1 commented 4 months ago

Does anyone know of a fast algorithm for computing the closest point to a (possibly non-planar and possibly concave) quadrilateral or polygon? I have an application that currently computes the algebraic center of a quadrilateral and then uses that to divide the quadrilateral into 4 triangles. The closest point is then computed for each triangle and we take the one with the minimum squared distance. But this algorithm is expensive (currently accounts for about 15% of the run time).

kennyweiss commented 4 months ago

Based on an offline discussion w/ @adayton1, the quads/polygons are embedded in 3D and the query points are also 3D.