Fit a shape to pointsFinding holes in 2d point sets?Approximating data with a multi segment cubic bezier curve and a distance as well as a curvature contraintGiven n points on a 2D plane, find the maximum number of points that lie on the same straight lineAlgorithms: Ellipse matchingDetect if geolocation is in complex polygon or notUnordered cloud point of polygon contour to polygonHow to Compute OBB of Multiple Curves?fitting a L shape (corner) to points to remove outliersCalculate distance between two latitude-longitude points? (Haversine formula)What algorithms compute directions from point A to point B on a map?How to define a circle shape in an Android xml drawable file?Fill 2D shape with rectanglesRobust polygon normal calculationFitting data with integral functionActive Shape Models: matching model points to target pointsIs there an algorithm to derive the vertices of a polygon if you have all of the points within?Efficient algorithm to create polygons from a 2D mesh? (vertices+edges)Find outlier after data fit in R

How to explain what's wrong with this application of the chain rule?

How can ping know if my host is down

How does electrical safety system work on ISS?

Why do Radio Buttons not fill the entire outer circle?

Has the laser at Magurele, Romania reached a tenth of the Sun's power?

What is the difference between lands and mana?

Microchip documentation does not label CAN buss pins on micro controller pinout diagram

Has any country ever had 2 former presidents in jail simultaneously?

How can I write humor as character trait?

PTIJ: Why is Haman obsessed with Bose?

"It doesn't matter" or "it won't matter"?

How could a planet have erratic days?

What to do when eye contact makes your coworker uncomfortable?

15% tax on $7.5k earnings. Is that right?

Circuit Analysis: Obtaining Close Loop OP - AMP Transfer function

Stack Interview Code methods made from class Node and Smart Pointers

What is going on with gets(stdin) on the site coderbyte?

What is the English pronunciation of "pain au chocolat"?

Permission on Database

Change the color of a single dot in `ddot` symbol

Why does Carol not get rid of the Kree symbol on her suit when she changes its colours?

Is there any evidence that Cleopatra and Caesarion considered fleeing to India to escape the Romans?

Is there a RAID 0 Equivalent for RAM?

C++ check if statement can be evaluated constexpr



Fit a shape to points


Finding holes in 2d point sets?Approximating data with a multi segment cubic bezier curve and a distance as well as a curvature contraintGiven n points on a 2D plane, find the maximum number of points that lie on the same straight lineAlgorithms: Ellipse matchingDetect if geolocation is in complex polygon or notUnordered cloud point of polygon contour to polygonHow to Compute OBB of Multiple Curves?fitting a L shape (corner) to points to remove outliersCalculate distance between two latitude-longitude points? (Haversine formula)What algorithms compute directions from point A to point B on a map?How to define a circle shape in an Android xml drawable file?Fill 2D shape with rectanglesRobust polygon normal calculationFitting data with integral functionActive Shape Models: matching model points to target pointsIs there an algorithm to derive the vertices of a polygon if you have all of the points within?Efficient algorithm to create polygons from a 2D mesh? (vertices+edges)Find outlier after data fit in R













4















I am trying to fit known well-defined shapes (eg rectangles and circles, with variable positions, rotations and dimensions) to a set of points with normals generated from sampling a polygon. My current method is to define a custom fit function for each shape and pass it to a third-party optimisation function:



fitness = get_fitness(shape_parameters, points)
best_parameters = external.optimise(get_fitness, initial_parameters, points)


(for reference, I'm currently using Python 3 and scipy.optimize.minimize with bounds, but language is irrelevant).



This fitness function for a rectangle would look something like



def get_fitness(parameters, points):
side_fitnesses = []
for side in [top, right, bottom, left]:
dists = get_side_distances(parameters, points, side)
ndevs = get_side_normal_deviations(parameters, points, side)
side_fitnesses.append(combine_dists_and_ndevs(dists, ndevs))
fitnesses = choose_best_side_for_each_point(side_fitnesses)
return mean(fitnesses)


However this means I have to determine outliers (with/without caching), and I can only fit one shape at a time.



For example, for these points (with normals), I'd like the following result:



boxes fitted to points with normals



Notice that there are multiple shapes returned, and outliers are ignored. In general, there can be many, one or zero shapes in the input data. Post-processing can remove invalid (eg too small) results.



Note: This questions deals with hypotheticals in 2D, but my real problem is in 3D. I have segments of a 3D mesh representation of real-world objects, which means I have more information than just points/normals (such as face areas and connectivity) which are in the example above.



Further reading:



  • Not well-defined shape-fitting

  • Highly technical n-dimensional fitting

  • Primitive shape-fitting thesis

  • Unanswered SO question on something similar

PS: I'm not sure if StackOverflow is the best StackExchange site for this question










share|improve this question



















  • 1





    Hi, can you clarify a bit more, e.g. for the example you present: Is the number of shapes fixed? Is the relative position of the two fixed? Is it size, orientation or both that you want to optimize? In the given example a third rectangle in the lower right would make the 'outliers' perfectly valid.

    – mikuszefski
    yesterday






  • 1





    I would go with different approach ... first identify contours so create a polylines going through all of your points in other words reorder/group your points first. then find edge and cross/joint points on the polylines , which will divide your set to groups after that just decide if a group is line or curve ... fit it and at last detect your shapes on the fitted lines and curves ... as you can see this sort of things might be too much for single SO answer ...

    – Spektre
    yesterday












  • after that determining simple shapes is easy (and even faster) for example rectangle is set of 4 connected lines with 90 degrees angle where the two pairs of line are the same length... so you can match that +/- some margin error ... see Unordered cloud point of polygon contour to polygon and Given n points on a 2D plane, find the maximum number of points that lie on the same straight line and Approximating data with a multi segment cubic bezier curve

    – Spektre
    yesterday











  • As you mentioned you aim for 3D but what shapes planar or with volume like spheres, boxes, etc ... ? Also where does your dataset come from ... if already processed its possible that in raw data is still some information that can ease up your task

    – Spektre
    yesterday












  • Thank you @Spektre, I've updated the question with more information. Do you think I should edit the question to remove all 2D? It may make the problem much more difficult to process

    – Epic Wink
    15 hours ago















4















I am trying to fit known well-defined shapes (eg rectangles and circles, with variable positions, rotations and dimensions) to a set of points with normals generated from sampling a polygon. My current method is to define a custom fit function for each shape and pass it to a third-party optimisation function:



fitness = get_fitness(shape_parameters, points)
best_parameters = external.optimise(get_fitness, initial_parameters, points)


(for reference, I'm currently using Python 3 and scipy.optimize.minimize with bounds, but language is irrelevant).



This fitness function for a rectangle would look something like



def get_fitness(parameters, points):
side_fitnesses = []
for side in [top, right, bottom, left]:
dists = get_side_distances(parameters, points, side)
ndevs = get_side_normal_deviations(parameters, points, side)
side_fitnesses.append(combine_dists_and_ndevs(dists, ndevs))
fitnesses = choose_best_side_for_each_point(side_fitnesses)
return mean(fitnesses)


However this means I have to determine outliers (with/without caching), and I can only fit one shape at a time.



For example, for these points (with normals), I'd like the following result:



boxes fitted to points with normals



Notice that there are multiple shapes returned, and outliers are ignored. In general, there can be many, one or zero shapes in the input data. Post-processing can remove invalid (eg too small) results.



Note: This questions deals with hypotheticals in 2D, but my real problem is in 3D. I have segments of a 3D mesh representation of real-world objects, which means I have more information than just points/normals (such as face areas and connectivity) which are in the example above.



Further reading:



  • Not well-defined shape-fitting

  • Highly technical n-dimensional fitting

  • Primitive shape-fitting thesis

  • Unanswered SO question on something similar

PS: I'm not sure if StackOverflow is the best StackExchange site for this question










share|improve this question



















  • 1





    Hi, can you clarify a bit more, e.g. for the example you present: Is the number of shapes fixed? Is the relative position of the two fixed? Is it size, orientation or both that you want to optimize? In the given example a third rectangle in the lower right would make the 'outliers' perfectly valid.

    – mikuszefski
    yesterday






  • 1





    I would go with different approach ... first identify contours so create a polylines going through all of your points in other words reorder/group your points first. then find edge and cross/joint points on the polylines , which will divide your set to groups after that just decide if a group is line or curve ... fit it and at last detect your shapes on the fitted lines and curves ... as you can see this sort of things might be too much for single SO answer ...

    – Spektre
    yesterday












  • after that determining simple shapes is easy (and even faster) for example rectangle is set of 4 connected lines with 90 degrees angle where the two pairs of line are the same length... so you can match that +/- some margin error ... see Unordered cloud point of polygon contour to polygon and Given n points on a 2D plane, find the maximum number of points that lie on the same straight line and Approximating data with a multi segment cubic bezier curve

    – Spektre
    yesterday











  • As you mentioned you aim for 3D but what shapes planar or with volume like spheres, boxes, etc ... ? Also where does your dataset come from ... if already processed its possible that in raw data is still some information that can ease up your task

    – Spektre
    yesterday












  • Thank you @Spektre, I've updated the question with more information. Do you think I should edit the question to remove all 2D? It may make the problem much more difficult to process

    – Epic Wink
    15 hours ago













4












4








4








I am trying to fit known well-defined shapes (eg rectangles and circles, with variable positions, rotations and dimensions) to a set of points with normals generated from sampling a polygon. My current method is to define a custom fit function for each shape and pass it to a third-party optimisation function:



fitness = get_fitness(shape_parameters, points)
best_parameters = external.optimise(get_fitness, initial_parameters, points)


(for reference, I'm currently using Python 3 and scipy.optimize.minimize with bounds, but language is irrelevant).



This fitness function for a rectangle would look something like



def get_fitness(parameters, points):
side_fitnesses = []
for side in [top, right, bottom, left]:
dists = get_side_distances(parameters, points, side)
ndevs = get_side_normal_deviations(parameters, points, side)
side_fitnesses.append(combine_dists_and_ndevs(dists, ndevs))
fitnesses = choose_best_side_for_each_point(side_fitnesses)
return mean(fitnesses)


However this means I have to determine outliers (with/without caching), and I can only fit one shape at a time.



For example, for these points (with normals), I'd like the following result:



boxes fitted to points with normals



Notice that there are multiple shapes returned, and outliers are ignored. In general, there can be many, one or zero shapes in the input data. Post-processing can remove invalid (eg too small) results.



Note: This questions deals with hypotheticals in 2D, but my real problem is in 3D. I have segments of a 3D mesh representation of real-world objects, which means I have more information than just points/normals (such as face areas and connectivity) which are in the example above.



Further reading:



  • Not well-defined shape-fitting

  • Highly technical n-dimensional fitting

  • Primitive shape-fitting thesis

  • Unanswered SO question on something similar

PS: I'm not sure if StackOverflow is the best StackExchange site for this question










share|improve this question
















I am trying to fit known well-defined shapes (eg rectangles and circles, with variable positions, rotations and dimensions) to a set of points with normals generated from sampling a polygon. My current method is to define a custom fit function for each shape and pass it to a third-party optimisation function:



fitness = get_fitness(shape_parameters, points)
best_parameters = external.optimise(get_fitness, initial_parameters, points)


(for reference, I'm currently using Python 3 and scipy.optimize.minimize with bounds, but language is irrelevant).



This fitness function for a rectangle would look something like



def get_fitness(parameters, points):
side_fitnesses = []
for side in [top, right, bottom, left]:
dists = get_side_distances(parameters, points, side)
ndevs = get_side_normal_deviations(parameters, points, side)
side_fitnesses.append(combine_dists_and_ndevs(dists, ndevs))
fitnesses = choose_best_side_for_each_point(side_fitnesses)
return mean(fitnesses)


However this means I have to determine outliers (with/without caching), and I can only fit one shape at a time.



For example, for these points (with normals), I'd like the following result:



boxes fitted to points with normals



Notice that there are multiple shapes returned, and outliers are ignored. In general, there can be many, one or zero shapes in the input data. Post-processing can remove invalid (eg too small) results.



Note: This questions deals with hypotheticals in 2D, but my real problem is in 3D. I have segments of a 3D mesh representation of real-world objects, which means I have more information than just points/normals (such as face areas and connectivity) which are in the example above.



Further reading:



  • Not well-defined shape-fitting

  • Highly technical n-dimensional fitting

  • Primitive shape-fitting thesis

  • Unanswered SO question on something similar

PS: I'm not sure if StackOverflow is the best StackExchange site for this question







algorithm shapes data-fitting






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited 15 hours ago







Epic Wink

















asked 2 days ago









Epic WinkEpic Wink

13618




13618







  • 1





    Hi, can you clarify a bit more, e.g. for the example you present: Is the number of shapes fixed? Is the relative position of the two fixed? Is it size, orientation or both that you want to optimize? In the given example a third rectangle in the lower right would make the 'outliers' perfectly valid.

    – mikuszefski
    yesterday






  • 1





    I would go with different approach ... first identify contours so create a polylines going through all of your points in other words reorder/group your points first. then find edge and cross/joint points on the polylines , which will divide your set to groups after that just decide if a group is line or curve ... fit it and at last detect your shapes on the fitted lines and curves ... as you can see this sort of things might be too much for single SO answer ...

    – Spektre
    yesterday












  • after that determining simple shapes is easy (and even faster) for example rectangle is set of 4 connected lines with 90 degrees angle where the two pairs of line are the same length... so you can match that +/- some margin error ... see Unordered cloud point of polygon contour to polygon and Given n points on a 2D plane, find the maximum number of points that lie on the same straight line and Approximating data with a multi segment cubic bezier curve

    – Spektre
    yesterday











  • As you mentioned you aim for 3D but what shapes planar or with volume like spheres, boxes, etc ... ? Also where does your dataset come from ... if already processed its possible that in raw data is still some information that can ease up your task

    – Spektre
    yesterday












  • Thank you @Spektre, I've updated the question with more information. Do you think I should edit the question to remove all 2D? It may make the problem much more difficult to process

    – Epic Wink
    15 hours ago












  • 1





    Hi, can you clarify a bit more, e.g. for the example you present: Is the number of shapes fixed? Is the relative position of the two fixed? Is it size, orientation or both that you want to optimize? In the given example a third rectangle in the lower right would make the 'outliers' perfectly valid.

    – mikuszefski
    yesterday






  • 1





    I would go with different approach ... first identify contours so create a polylines going through all of your points in other words reorder/group your points first. then find edge and cross/joint points on the polylines , which will divide your set to groups after that just decide if a group is line or curve ... fit it and at last detect your shapes on the fitted lines and curves ... as you can see this sort of things might be too much for single SO answer ...

    – Spektre
    yesterday












  • after that determining simple shapes is easy (and even faster) for example rectangle is set of 4 connected lines with 90 degrees angle where the two pairs of line are the same length... so you can match that +/- some margin error ... see Unordered cloud point of polygon contour to polygon and Given n points on a 2D plane, find the maximum number of points that lie on the same straight line and Approximating data with a multi segment cubic bezier curve

    – Spektre
    yesterday











  • As you mentioned you aim for 3D but what shapes planar or with volume like spheres, boxes, etc ... ? Also where does your dataset come from ... if already processed its possible that in raw data is still some information that can ease up your task

    – Spektre
    yesterday












  • Thank you @Spektre, I've updated the question with more information. Do you think I should edit the question to remove all 2D? It may make the problem much more difficult to process

    – Epic Wink
    15 hours ago







1




1





Hi, can you clarify a bit more, e.g. for the example you present: Is the number of shapes fixed? Is the relative position of the two fixed? Is it size, orientation or both that you want to optimize? In the given example a third rectangle in the lower right would make the 'outliers' perfectly valid.

– mikuszefski
yesterday





Hi, can you clarify a bit more, e.g. for the example you present: Is the number of shapes fixed? Is the relative position of the two fixed? Is it size, orientation or both that you want to optimize? In the given example a third rectangle in the lower right would make the 'outliers' perfectly valid.

– mikuszefski
yesterday




1




1





I would go with different approach ... first identify contours so create a polylines going through all of your points in other words reorder/group your points first. then find edge and cross/joint points on the polylines , which will divide your set to groups after that just decide if a group is line or curve ... fit it and at last detect your shapes on the fitted lines and curves ... as you can see this sort of things might be too much for single SO answer ...

– Spektre
yesterday






I would go with different approach ... first identify contours so create a polylines going through all of your points in other words reorder/group your points first. then find edge and cross/joint points on the polylines , which will divide your set to groups after that just decide if a group is line or curve ... fit it and at last detect your shapes on the fitted lines and curves ... as you can see this sort of things might be too much for single SO answer ...

– Spektre
yesterday














after that determining simple shapes is easy (and even faster) for example rectangle is set of 4 connected lines with 90 degrees angle where the two pairs of line are the same length... so you can match that +/- some margin error ... see Unordered cloud point of polygon contour to polygon and Given n points on a 2D plane, find the maximum number of points that lie on the same straight line and Approximating data with a multi segment cubic bezier curve

– Spektre
yesterday





after that determining simple shapes is easy (and even faster) for example rectangle is set of 4 connected lines with 90 degrees angle where the two pairs of line are the same length... so you can match that +/- some margin error ... see Unordered cloud point of polygon contour to polygon and Given n points on a 2D plane, find the maximum number of points that lie on the same straight line and Approximating data with a multi segment cubic bezier curve

– Spektre
yesterday













As you mentioned you aim for 3D but what shapes planar or with volume like spheres, boxes, etc ... ? Also where does your dataset come from ... if already processed its possible that in raw data is still some information that can ease up your task

– Spektre
yesterday






As you mentioned you aim for 3D but what shapes planar or with volume like spheres, boxes, etc ... ? Also where does your dataset come from ... if already processed its possible that in raw data is still some information that can ease up your task

– Spektre
yesterday














Thank you @Spektre, I've updated the question with more information. Do you think I should edit the question to remove all 2D? It may make the problem much more difficult to process

– Epic Wink
15 hours ago





Thank you @Spektre, I've updated the question with more information. Do you think I should edit the question to remove all 2D? It may make the problem much more difficult to process

– Epic Wink
15 hours ago












1 Answer
1






active

oldest

votes


















0














well so you will have to handle meshes with volume then. That changes things a lot ...




  1. segmentate objects



    be selecting all faces enclosing its inside ... So its similar to this:



    • Finding holes in 2d point sets?

    so simply find a point inside yet unused mesh ... and "fill" the volume until you hit all the faces it is composed of. Select those faces as belonging to new object. and set them as used... beware touching objects may lead to usage of faces twice or more ...



    You can do this also on vector math/space so just test if line from some inside point to a face is hitting any other face ... if no you found your surface face ... similar to Hit test




  2. process object (optional)



    you can further segmentate the object mesh into "planar" objects that it is composed of by grouping faces belonging to the same plane ... or inside enclosing edge/contour ... then detect what they are



    • triangle

    • rectangle

    • polygon

    • disc

    from count and type of faces you can detect basic objects like:



    cone = 1 disc + 1 curved surface with singular edge point parallel to disc center
    box/cube = 6 rectangles/squares
    cylinder = 2 discs + 1 curved surface with center axis going through discs centers



  3. compute basic geometric properties of individual objects (optional)



    like BBOX or OBB, surface, volume, geom. center, mass center, ...



    Now just decide what type of object it is. For example ratio between surface area and volume can hint sphere or ellipsoid, if OBB matches sides it hints box, if geom and mass centers are the same it hints symmetrical object ...




  4. pass the mesh to possible object type fitting function



    so based on bullets #2,#3 you have an idea which object could be which shapes so just confirm it with your fitting function ...



    to ease up this process you can use properties from #3 for example of this see similar:



    • ellipse matching

    so you can come up with similar techniques for basic 3D shapes...







share|improve this answer
























    Your Answer






    StackExchange.ifUsing("editor", function ()
    StackExchange.using("externalEditor", function ()
    StackExchange.using("snippets", function ()
    StackExchange.snippets.init();
    );
    );
    , "code-snippets");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "1"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader:
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    ,
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );













    draft saved

    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55236481%2ffit-a-shape-to-points%23new-answer', 'question_page');

    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    0














    well so you will have to handle meshes with volume then. That changes things a lot ...




    1. segmentate objects



      be selecting all faces enclosing its inside ... So its similar to this:



      • Finding holes in 2d point sets?

      so simply find a point inside yet unused mesh ... and "fill" the volume until you hit all the faces it is composed of. Select those faces as belonging to new object. and set them as used... beware touching objects may lead to usage of faces twice or more ...



      You can do this also on vector math/space so just test if line from some inside point to a face is hitting any other face ... if no you found your surface face ... similar to Hit test




    2. process object (optional)



      you can further segmentate the object mesh into "planar" objects that it is composed of by grouping faces belonging to the same plane ... or inside enclosing edge/contour ... then detect what they are



      • triangle

      • rectangle

      • polygon

      • disc

      from count and type of faces you can detect basic objects like:



      cone = 1 disc + 1 curved surface with singular edge point parallel to disc center
      box/cube = 6 rectangles/squares
      cylinder = 2 discs + 1 curved surface with center axis going through discs centers



    3. compute basic geometric properties of individual objects (optional)



      like BBOX or OBB, surface, volume, geom. center, mass center, ...



      Now just decide what type of object it is. For example ratio between surface area and volume can hint sphere or ellipsoid, if OBB matches sides it hints box, if geom and mass centers are the same it hints symmetrical object ...




    4. pass the mesh to possible object type fitting function



      so based on bullets #2,#3 you have an idea which object could be which shapes so just confirm it with your fitting function ...



      to ease up this process you can use properties from #3 for example of this see similar:



      • ellipse matching

      so you can come up with similar techniques for basic 3D shapes...







    share|improve this answer





























      0














      well so you will have to handle meshes with volume then. That changes things a lot ...




      1. segmentate objects



        be selecting all faces enclosing its inside ... So its similar to this:



        • Finding holes in 2d point sets?

        so simply find a point inside yet unused mesh ... and "fill" the volume until you hit all the faces it is composed of. Select those faces as belonging to new object. and set them as used... beware touching objects may lead to usage of faces twice or more ...



        You can do this also on vector math/space so just test if line from some inside point to a face is hitting any other face ... if no you found your surface face ... similar to Hit test




      2. process object (optional)



        you can further segmentate the object mesh into "planar" objects that it is composed of by grouping faces belonging to the same plane ... or inside enclosing edge/contour ... then detect what they are



        • triangle

        • rectangle

        • polygon

        • disc

        from count and type of faces you can detect basic objects like:



        cone = 1 disc + 1 curved surface with singular edge point parallel to disc center
        box/cube = 6 rectangles/squares
        cylinder = 2 discs + 1 curved surface with center axis going through discs centers



      3. compute basic geometric properties of individual objects (optional)



        like BBOX or OBB, surface, volume, geom. center, mass center, ...



        Now just decide what type of object it is. For example ratio between surface area and volume can hint sphere or ellipsoid, if OBB matches sides it hints box, if geom and mass centers are the same it hints symmetrical object ...




      4. pass the mesh to possible object type fitting function



        so based on bullets #2,#3 you have an idea which object could be which shapes so just confirm it with your fitting function ...



        to ease up this process you can use properties from #3 for example of this see similar:



        • ellipse matching

        so you can come up with similar techniques for basic 3D shapes...







      share|improve this answer



























        0












        0








        0







        well so you will have to handle meshes with volume then. That changes things a lot ...




        1. segmentate objects



          be selecting all faces enclosing its inside ... So its similar to this:



          • Finding holes in 2d point sets?

          so simply find a point inside yet unused mesh ... and "fill" the volume until you hit all the faces it is composed of. Select those faces as belonging to new object. and set them as used... beware touching objects may lead to usage of faces twice or more ...



          You can do this also on vector math/space so just test if line from some inside point to a face is hitting any other face ... if no you found your surface face ... similar to Hit test




        2. process object (optional)



          you can further segmentate the object mesh into "planar" objects that it is composed of by grouping faces belonging to the same plane ... or inside enclosing edge/contour ... then detect what they are



          • triangle

          • rectangle

          • polygon

          • disc

          from count and type of faces you can detect basic objects like:



          cone = 1 disc + 1 curved surface with singular edge point parallel to disc center
          box/cube = 6 rectangles/squares
          cylinder = 2 discs + 1 curved surface with center axis going through discs centers



        3. compute basic geometric properties of individual objects (optional)



          like BBOX or OBB, surface, volume, geom. center, mass center, ...



          Now just decide what type of object it is. For example ratio between surface area and volume can hint sphere or ellipsoid, if OBB matches sides it hints box, if geom and mass centers are the same it hints symmetrical object ...




        4. pass the mesh to possible object type fitting function



          so based on bullets #2,#3 you have an idea which object could be which shapes so just confirm it with your fitting function ...



          to ease up this process you can use properties from #3 for example of this see similar:



          • ellipse matching

          so you can come up with similar techniques for basic 3D shapes...







        share|improve this answer















        well so you will have to handle meshes with volume then. That changes things a lot ...




        1. segmentate objects



          be selecting all faces enclosing its inside ... So its similar to this:



          • Finding holes in 2d point sets?

          so simply find a point inside yet unused mesh ... and "fill" the volume until you hit all the faces it is composed of. Select those faces as belonging to new object. and set them as used... beware touching objects may lead to usage of faces twice or more ...



          You can do this also on vector math/space so just test if line from some inside point to a face is hitting any other face ... if no you found your surface face ... similar to Hit test




        2. process object (optional)



          you can further segmentate the object mesh into "planar" objects that it is composed of by grouping faces belonging to the same plane ... or inside enclosing edge/contour ... then detect what they are



          • triangle

          • rectangle

          • polygon

          • disc

          from count and type of faces you can detect basic objects like:



          cone = 1 disc + 1 curved surface with singular edge point parallel to disc center
          box/cube = 6 rectangles/squares
          cylinder = 2 discs + 1 curved surface with center axis going through discs centers



        3. compute basic geometric properties of individual objects (optional)



          like BBOX or OBB, surface, volume, geom. center, mass center, ...



          Now just decide what type of object it is. For example ratio between surface area and volume can hint sphere or ellipsoid, if OBB matches sides it hints box, if geom and mass centers are the same it hints symmetrical object ...




        4. pass the mesh to possible object type fitting function



          so based on bullets #2,#3 you have an idea which object could be which shapes so just confirm it with your fitting function ...



          to ease up this process you can use properties from #3 for example of this see similar:



          • ellipse matching

          so you can come up with similar techniques for basic 3D shapes...








        share|improve this answer














        share|improve this answer



        share|improve this answer








        edited 13 hours ago

























        answered 14 hours ago









        SpektreSpektre

        30.1k649219




        30.1k649219





























            draft saved

            draft discarded
















































            Thanks for contributing an answer to Stack Overflow!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid


            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.

            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55236481%2ffit-a-shape-to-points%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Kamusi Yaliyomo Aina za kamusi | Muundo wa kamusi | Faida za kamusi | Dhima ya picha katika kamusi | Marejeo | Tazama pia | Viungo vya nje | UrambazajiKuhusu kamusiGo-SwahiliWiki-KamusiKamusi ya Kiswahili na Kiingerezakuihariri na kuongeza habari

            SQL error code 1064 with creating Laravel foreign keysForeign key constraints: When to use ON UPDATE and ON DELETEDropping column with foreign key Laravel error: General error: 1025 Error on renameLaravel SQL Can't create tableLaravel Migration foreign key errorLaravel php artisan migrate:refresh giving a syntax errorSQLSTATE[42S01]: Base table or view already exists or Base table or view already exists: 1050 Tableerror in migrating laravel file to xampp serverSyntax error or access violation: 1064:syntax to use near 'unsigned not null, modelName varchar(191) not null, title varchar(191) not nLaravel cannot create new table field in mysqlLaravel 5.7:Last migration creates table but is not registered in the migration table

            은진 송씨 목차 역사 본관 분파 인물 조선 왕실과의 인척 관계 집성촌 항렬자 인구 같이 보기 각주 둘러보기 메뉴은진 송씨세종실록 149권, 지리지 충청도 공주목 은진현