1
$\begingroup$

I have a 3D surface, defined as collection of points in a 3D evenly spaced mesh. I have a rectangle of fixed size (height x width), and I need to find a collection of rectangles positions in the 3D space (i.e. I also need the tilt angles of the rectangle, or the vector normal to the rectangle) which will cover all the points. The different rectangle positions can overlap. There is a tolerance in the distance of the points from the rectangle surface, to still consider the point "covered by the rectangle".

To give a physical intuition of the problem, the rectangle can be thought as the "field of view" of a camera, and I need to find the set of camera positions to "image" all the parts of the 3D surface (e.g. the external surface of an object), taking into account the depth-of-field of the camera (distance tolerance).

Here is a sketch (sorry for my poor drawing abilities!):

sketch

Improve this question
$\endgroup$
9
  • $\begingroup$ I don't understand the question. Are you asking whether the projection of the rectangle onto the surface covers these points? $\endgroup$
    – Wolfgang Bangerth
    Commented Dec 29, 2023 at 3:06
  • $\begingroup$ Thank you for the question, Wolfgang! No, I am asking for an algorithm to generate a set of positions that catch all the points (all the parts) of the surface. $\endgroup$
    – Fabio
    Commented Dec 29, 2023 at 9:42
  • 1
    $\begingroup$ Well, then I don't understand the question. How can a rectangle (a 2d structure) cover points in 3d? In general, none of the points will be enclosed in the rectangle's area (because it has zero 3d volume). $\endgroup$
    – Wolfgang Bangerth
    Commented Dec 29, 2023 at 22:04
  • 1
    $\begingroup$ @WolfgangBangerth I think Fabio is asking for a disco-ball approximation to the sphere. But maybe in a way that rectangles are allowed to overlap. Maybe a generalization/specialization of Voronoi algorithm for this case? $\endgroup$
    – Abdullah Ali Sivas
    Commented Dec 31, 2023 at 21:41
  • $\begingroup$ @WolfgangBangerth sorry for my imprecise description: there is a "tollerance" in the third dimension of the rectangle. If you want, the rectangle is not 2D, but it is rather a rectangle parallelepiped. $\endgroup$
    – Fabio
    Commented Jan 2 at 7:50

2 Answers 2

Reset to default
2
$\begingroup$

Welcome to Scicomp! Cover your surface with points of roughly equal spacing. Then iterate over these points and grow a cube around them. You could use the minimal distance of points in your point cloud as stepsize. If any of the cube surfaces touches the neighbouring cubes, stop iterations for this cube (for now). continue growing along those axes which still have no neighbouring counterpart (loosing cubic shape to a parallel-epiped). If the cells each have found their neighbours you enter the second phase.

Iterate over all your points in your pointcloud und check if they are contained in any of the cells of step one. if not, grow only the adjacent cells a bit more.

You may add postprocessing phases to shrink your cells in z-direction, or do the iteration separately for each dimension.

Improve this answer
$\endgroup$
4
  • $\begingroup$ your idea is good, but unfortunately one of my constrains id that the size of the 'cell' is fixed... $\endgroup$
    – Fabio
    Commented Jan 5 at 10:42
  • 1
    $\begingroup$ Ah! Then you could globally find the smallest bounding box of your point cloud and fill that global bounding box up with the cells with size of your choosing. Then iterate through that box of boxes and delete all boxes not containing points. That will leave you with a set of boxes which all have the same orientation. That might not be optimal, but a good start. Your 'camera' will move more efficiently if the target squares are lined up anyway. $\endgroup$
    – MPIchael
    Commented Jan 5 at 10:45
  • 1
    $\begingroup$ Is this some satelite LIDAR application or are we talking car parts? $\endgroup$
    – MPIchael
    Commented Jan 5 at 10:55
  • $\begingroup$ Good idea, this "divide and conquer" of yours... No, no satellite, it is more like an industrial application. $\endgroup$
    – Fabio
    Commented Jan 5 at 10:56
2
$\begingroup$

Your problem is related to the Geometric Set Cover problem in that you could reduce a variant of the 2d axis-aligned rectangle cover problem to your problem. This implies your problem is NP-Hard and getting a perfect result efficiently will not happen. Fortunately, there are a lot of interesting approximation techniques for such problems that you might be able to use to give you ideas about how to solve your problem.

Something you could consider is take your surface and break it into contiguous subsurfaces that are approximately (to within your tolerance, say) planar and then reduce the problem on each subsurface to solving the 2d axis-aligned rectangle cover problem. Then you can either find an existing implementation for the axis-aligned rectangle cover problem you can reduce to or implement that yourself based on a literature review, which should be a bit easier.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.