Why does scipy.spatial.Voronoi() output zero regions even if there are no duplicate input points?

Multi tool use
Why are some Voronoi regions empty?
I have a point cloud of the surface of a human that I'm trying to find the Voronoi diagram of. So I found scipy.spatial.Voronoi()
, including some pretty good documentation. But sometimes vor.regions
includes empty regions, and the documentation doesn't quite explain why they're there. At best it explains the relation to its Delaunay calculation "Note here that due to similar numerical precision issues as in Delaunay triangulation above, there may be fewer Voronoi regions than input points." But if so, it's only because qhull calculates Voronoi using a similar (or the exact same) algorithm as it uses for Delaunay Triangulation that this happens. Mathematically, the only reason a Voronoi region should be empty is if its points are duplicated
Specific goals:
I'm looking to replicate the results from this paper that use the Voronoi diagrams to calculate normal vectors at each input point. So I could do a workaround where I use a similar normal to a nearby point's properly calculated normal, or I could ignore any point that gives a zero Voronoi region. But I'd really like to know how to solve these empty regions so I can use as much of the input data as possible.
Background and other research
This answer suggests Voronoi(points, qhull_options='Qbb Qc Qx')
and in the docs scipy suggests qhull_options="QJ Pp"
input data: http://columbia.edu/~nxb2101/minimal_stickfig_.npy
Code:
import numpy as np; np.set_err(all='raise')
import scipy.spatial
pt_cloud=np.load('minimal_stickfig_.npy')
vor=scipy.spatial.Voronoi(pt_cloud)
for idx in range(len(vor.regions)):
region=vor.regions[idx]
vertices = vor.vertices[region]
hull=scipy.spatial.ConvexHull(vertices)
volume=hull.volume
triangle_mesh_hull=vertices[hull.simplices] # (n,3,3)
# triang mesh calculation taken from
# https://stackoverflow.com/questions/26434726/return-surface-triangle-of-3d-scipy-spatial-delaunay/26516915
inner_pt = np.mean(vertices[:2],axis=0).reshape((1,3))
CoM=np.zeros((3,))
pif("inner_pt is {0}".format(inner_pt))
for triangle in triangle_mesh_hull:
pif("triangle is: n{0}".format(triangle))
tetra=np.concatenate((inner_pt,triangle),axis=0)
CoM_tetra=np.mean(tetra,axis=0)
vol_tetra=volume_tetra(tetra)
CoM+=(CoM_tetra*vol_tetra)
CoM /= volume
# do more with CoM, and volume
Any kind of help is appreciated; if you're not sure why qhull does this or how to get around it, please let me know what you did to make a high-quality mesh from a point cloud
python scipy voronoi qhull scipy-spatial
add a comment |
Why are some Voronoi regions empty?
I have a point cloud of the surface of a human that I'm trying to find the Voronoi diagram of. So I found scipy.spatial.Voronoi()
, including some pretty good documentation. But sometimes vor.regions
includes empty regions, and the documentation doesn't quite explain why they're there. At best it explains the relation to its Delaunay calculation "Note here that due to similar numerical precision issues as in Delaunay triangulation above, there may be fewer Voronoi regions than input points." But if so, it's only because qhull calculates Voronoi using a similar (or the exact same) algorithm as it uses for Delaunay Triangulation that this happens. Mathematically, the only reason a Voronoi region should be empty is if its points are duplicated
Specific goals:
I'm looking to replicate the results from this paper that use the Voronoi diagrams to calculate normal vectors at each input point. So I could do a workaround where I use a similar normal to a nearby point's properly calculated normal, or I could ignore any point that gives a zero Voronoi region. But I'd really like to know how to solve these empty regions so I can use as much of the input data as possible.
Background and other research
This answer suggests Voronoi(points, qhull_options='Qbb Qc Qx')
and in the docs scipy suggests qhull_options="QJ Pp"
input data: http://columbia.edu/~nxb2101/minimal_stickfig_.npy
Code:
import numpy as np; np.set_err(all='raise')
import scipy.spatial
pt_cloud=np.load('minimal_stickfig_.npy')
vor=scipy.spatial.Voronoi(pt_cloud)
for idx in range(len(vor.regions)):
region=vor.regions[idx]
vertices = vor.vertices[region]
hull=scipy.spatial.ConvexHull(vertices)
volume=hull.volume
triangle_mesh_hull=vertices[hull.simplices] # (n,3,3)
# triang mesh calculation taken from
# https://stackoverflow.com/questions/26434726/return-surface-triangle-of-3d-scipy-spatial-delaunay/26516915
inner_pt = np.mean(vertices[:2],axis=0).reshape((1,3))
CoM=np.zeros((3,))
pif("inner_pt is {0}".format(inner_pt))
for triangle in triangle_mesh_hull:
pif("triangle is: n{0}".format(triangle))
tetra=np.concatenate((inner_pt,triangle),axis=0)
CoM_tetra=np.mean(tetra,axis=0)
vol_tetra=volume_tetra(tetra)
CoM+=(CoM_tetra*vol_tetra)
CoM /= volume
# do more with CoM, and volume
Any kind of help is appreciated; if you're not sure why qhull does this or how to get around it, please let me know what you did to make a high-quality mesh from a point cloud
python scipy voronoi qhull scipy-spatial
add a comment |
Why are some Voronoi regions empty?
I have a point cloud of the surface of a human that I'm trying to find the Voronoi diagram of. So I found scipy.spatial.Voronoi()
, including some pretty good documentation. But sometimes vor.regions
includes empty regions, and the documentation doesn't quite explain why they're there. At best it explains the relation to its Delaunay calculation "Note here that due to similar numerical precision issues as in Delaunay triangulation above, there may be fewer Voronoi regions than input points." But if so, it's only because qhull calculates Voronoi using a similar (or the exact same) algorithm as it uses for Delaunay Triangulation that this happens. Mathematically, the only reason a Voronoi region should be empty is if its points are duplicated
Specific goals:
I'm looking to replicate the results from this paper that use the Voronoi diagrams to calculate normal vectors at each input point. So I could do a workaround where I use a similar normal to a nearby point's properly calculated normal, or I could ignore any point that gives a zero Voronoi region. But I'd really like to know how to solve these empty regions so I can use as much of the input data as possible.
Background and other research
This answer suggests Voronoi(points, qhull_options='Qbb Qc Qx')
and in the docs scipy suggests qhull_options="QJ Pp"
input data: http://columbia.edu/~nxb2101/minimal_stickfig_.npy
Code:
import numpy as np; np.set_err(all='raise')
import scipy.spatial
pt_cloud=np.load('minimal_stickfig_.npy')
vor=scipy.spatial.Voronoi(pt_cloud)
for idx in range(len(vor.regions)):
region=vor.regions[idx]
vertices = vor.vertices[region]
hull=scipy.spatial.ConvexHull(vertices)
volume=hull.volume
triangle_mesh_hull=vertices[hull.simplices] # (n,3,3)
# triang mesh calculation taken from
# https://stackoverflow.com/questions/26434726/return-surface-triangle-of-3d-scipy-spatial-delaunay/26516915
inner_pt = np.mean(vertices[:2],axis=0).reshape((1,3))
CoM=np.zeros((3,))
pif("inner_pt is {0}".format(inner_pt))
for triangle in triangle_mesh_hull:
pif("triangle is: n{0}".format(triangle))
tetra=np.concatenate((inner_pt,triangle),axis=0)
CoM_tetra=np.mean(tetra,axis=0)
vol_tetra=volume_tetra(tetra)
CoM+=(CoM_tetra*vol_tetra)
CoM /= volume
# do more with CoM, and volume
Any kind of help is appreciated; if you're not sure why qhull does this or how to get around it, please let me know what you did to make a high-quality mesh from a point cloud
python scipy voronoi qhull scipy-spatial
Why are some Voronoi regions empty?
I have a point cloud of the surface of a human that I'm trying to find the Voronoi diagram of. So I found scipy.spatial.Voronoi()
, including some pretty good documentation. But sometimes vor.regions
includes empty regions, and the documentation doesn't quite explain why they're there. At best it explains the relation to its Delaunay calculation "Note here that due to similar numerical precision issues as in Delaunay triangulation above, there may be fewer Voronoi regions than input points." But if so, it's only because qhull calculates Voronoi using a similar (or the exact same) algorithm as it uses for Delaunay Triangulation that this happens. Mathematically, the only reason a Voronoi region should be empty is if its points are duplicated
Specific goals:
I'm looking to replicate the results from this paper that use the Voronoi diagrams to calculate normal vectors at each input point. So I could do a workaround where I use a similar normal to a nearby point's properly calculated normal, or I could ignore any point that gives a zero Voronoi region. But I'd really like to know how to solve these empty regions so I can use as much of the input data as possible.
Background and other research
This answer suggests Voronoi(points, qhull_options='Qbb Qc Qx')
and in the docs scipy suggests qhull_options="QJ Pp"
input data: http://columbia.edu/~nxb2101/minimal_stickfig_.npy
Code:
import numpy as np; np.set_err(all='raise')
import scipy.spatial
pt_cloud=np.load('minimal_stickfig_.npy')
vor=scipy.spatial.Voronoi(pt_cloud)
for idx in range(len(vor.regions)):
region=vor.regions[idx]
vertices = vor.vertices[region]
hull=scipy.spatial.ConvexHull(vertices)
volume=hull.volume
triangle_mesh_hull=vertices[hull.simplices] # (n,3,3)
# triang mesh calculation taken from
# https://stackoverflow.com/questions/26434726/return-surface-triangle-of-3d-scipy-spatial-delaunay/26516915
inner_pt = np.mean(vertices[:2],axis=0).reshape((1,3))
CoM=np.zeros((3,))
pif("inner_pt is {0}".format(inner_pt))
for triangle in triangle_mesh_hull:
pif("triangle is: n{0}".format(triangle))
tetra=np.concatenate((inner_pt,triangle),axis=0)
CoM_tetra=np.mean(tetra,axis=0)
vol_tetra=volume_tetra(tetra)
CoM+=(CoM_tetra*vol_tetra)
CoM /= volume
# do more with CoM, and volume
Any kind of help is appreciated; if you're not sure why qhull does this or how to get around it, please let me know what you did to make a high-quality mesh from a point cloud
python scipy voronoi qhull scipy-spatial
python scipy voronoi qhull scipy-spatial
asked Dec 31 '18 at 18:58
platonicityplatonicity
24
24
add a comment |
add a comment |
0
active
oldest
votes
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%2f53990605%2fwhy-does-scipy-spatial-voronoi-output-zero-regions-even-if-there-are-no-duplic%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f53990605%2fwhy-does-scipy-spatial-voronoi-output-zero-regions-even-if-there-are-no-duplic%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
pjejZ8K60Q0yiHBAG4afKrq,4Y,cX3H9c,izEFuFMdt8trBDKSkc YnniW0oyAIh329117k1Jcy