Division d'un nuage de points 3D en zones de délimitation orientées plus petites

Question

Je travaille avec C# WPF.

Je cherche un algorithme pour résoudre mon problème. Probablement ce n'est pas si trivial et va dans les graphiques 3D.

J'ai une surface 2D dans un espace 3D (peut également être représenté par un nuage de points).

J'ai besoin de diviser cette surface en plus petits morceaux, qui devraient tenir dans une boîte spécifique (par exemple 300 x 300 x 15). Je recherche un algorithme qui fonctionne en 3D et qui n'est pas aligné sur l'axe, quelque chose comme un cadre de volume minimal mais qui divise le volume en plus petites boîtes si la boîte est plus grande que le volume spécifique.

Je suspecte un problème d'optimisation d'OBB et beaucoup d'itérations, mais je n'ai aucune idée de la façon d'y remédier.

L'image illustre un peu le problème. Les cases rouge et noire ne sont pas obligées d'être alignées sur l'axe et elles doivent être < ou = à la taille maximale de la boîte (taille et non volume!).

Merci à tous pour votre soutien!

Answer 1

Votre problème est connu pour être NP-difficile dans le cas de couvrir une forme avec des disques: voir f.e. https://en.wikipedia.org/wiki/Geometric_set_cover_problem. Je soupçonne fortement que votre cas de problème de couverture n'est rien de mieux. Il faut donc recourir à des algorithmes à peu près exacts pour faire le travail en temps linéaire ou polynomial. En fonction des conditions que vous pouvez sacrifier dans votre solution, vous pouvez arriver à une tâche complètement différente avec une solution connue. Donc, si vous expliquez comment vous êtes arrivé à cette tâche et quelle était la véritable tâche que vous vouliez résoudre, alors nous pourrions discuter de la solution approximative qui pourrait être suffisante pour votre cas. Par exemple, si vous êtes bon avec un recouvrement suboptimal (mais suffisant) de votre ensemble de points avec des boîtes orientées de taille et d'orientation sub-optimales (mais assez bon), vous pouvez utiliser un algorithme rapide impliquant la génération epsilon-nets (voir fe https://en.wikipedia.org/wiki/%CE%95-net_(computational_geometry) et https://en.wikipedia.org/wiki/Delone_set) et/ou glouton subdivisant l'ensemble de points en sous-ensembles avec une certaine approximation gloutonne d'une boîte de délimitation orientée suffisamment bonne pour chaque sous-ensemble.

Aussi, je ne l'ai pas encore utilisé moi-même en pratique mais si je devais penser à une solution approximative de votre tâche en connaissant vos contraintes sur la solution, je penserais avec https://arxiv.org/abs/1409.7425 qui est censé servir de cadre pour générer des solutions approximatives d'une famille de tâches similaires aux vôtres. Jetez un coup d'oeil, peut-être vous voyez quelque chose explicitement utile pour vous ou peut-être vous voyez là des mots utiles à google prêt à utiliser des solutions.