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
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:
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
|
show 1 more comment
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:
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
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
|
show 1 more comment
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:
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
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:
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
algorithm shapes data-fitting
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
|
show 1 more comment
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
|
show 1 more comment
1 Answer
1
active
oldest
votes
well so you will have to handle meshes with volume then. That changes things a lot ...
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
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 centerscompute 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 ...
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...
add a comment |
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
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
well so you will have to handle meshes with volume then. That changes things a lot ...
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
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 centerscompute 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 ...
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...
add a comment |
well so you will have to handle meshes with volume then. That changes things a lot ...
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
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 centerscompute 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 ...
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...
add a comment |
well so you will have to handle meshes with volume then. That changes things a lot ...
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
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 centerscompute 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 ...
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...
well so you will have to handle meshes with volume then. That changes things a lot ...
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
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 centerscompute 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 ...
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...
edited 13 hours ago
answered 14 hours ago
SpektreSpektre
30.1k649219
30.1k649219
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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