Questions tagged [computational-geometry]
The study of efficient algorithms and data structures to solve various problems involving point sets, line segments, polygons, polyhedra, simplices, etc.
220
questions
1
vote
0answers
34 views
Surface mesh from labeled 3D points
I'm trying to figure out how to create a surface mesh from a set of labeled 3D points. The 3D object could be something like part of a cave system or asteroid where there would be parts of the surface ...
5
votes
0answers
236 views
Finding points inside cells of power (generalized Voronoi) diagram
Suppose we have a set of points $p_1,\ldots,p_n\in\mathbb R^d$ as well as a set of weights $w_1,\ldots,w_n\in\mathbb R$. Recall that the power cell associated to the pair $(p_k,w_k)$ is given by:
$$\...
0
votes
2answers
68 views
How to minimize $(x-a)^2+(y-b)^2$ subject to $ \sqrt{a}+\sqrt{b}=\sqrt{2}$?
I am not sure if this is on-topic here, but I am trying.
Let $x,y$ be positive real numbers. I am trying to find
$$ \min_{\sqrt{a}+\sqrt{b}=\sqrt{2}}(x-a)^2+(y-b)^2$$
I tried using Mathematica for ...
0
votes
1answer
88 views
Applying weak form
I have two dimensional equation and I want to solve it using Finite Element Methods.
$$ \nabla . (\alpha(x,y)\nabla u(x,y)) + \dfrac{\partial u(x,y)}{\partial x}+\dfrac{\partial u(x,y)}{\partial y}+u(...
4
votes
0answers
49 views
Why does the naive barycentric hodgestar fail?
The discrete exterior calculus is defined first using circumcentric dual cells, because the primal and dual edges are orthogonal and thus the dual cells are convex. This leads to a diagonal hodge star ...
0
votes
1answer
61 views
Desmos saying there are too many variables [closed]
I wasn't sure if this is a Computational Science SE question or a Stack Overflow question but I think it's more of this one.
I wanted to make a graph where I can rotate a hyperbola (not parabola or ...
1
vote
1answer
52 views
How do I find the portion of a cell/voxel lying within a defined surface?
We have a 3-dimensional grid of voxels (or cells), with individual voxels being of volume $dx\,dy\,dz$ where $dx=dy=dz=1$.
A cone-like surface is defined by some function, $z = f(x, y)$, which in ...
-1
votes
1answer
46 views
Detecting degenerate triangles with very thin structures
Between the two ears in the following bunny images, there are some degenerate triangles I want to detect. It looks like a volume-less thin slits.
If the question is not clear, please let me know.
0
votes
1answer
36 views
Systematically outputting sign vectors of restricted hyperplane arrangement
(I previously asked this question on Sage's dedicated Q&A site, but got no response, so I figured it would be worth trying here.)
I have a way of constructing hyperplane arrangements in Sage, ...
2
votes
2answers
204 views
How to determine the Jacobian Ratio for triangle element?
I am trying to implement an algorithm to find the Jacobian ratio for each triangle in mesh as a part of mesh quality check.
Let's say that I have vertices of the triangle: $P_1(x_1, y_1, z_1)$, $P_2(...
1
vote
0answers
25 views
Simplification of vertices and dihedral angle relations of a polygonal chain
I am trying to understand the generation of Cartesian coordinates of polygonal system or poly line with fixed bond angles and fixed link lengths. I assumed the bond angle to be the same and link ...
3
votes
2answers
84 views
Packing spheres inside a geometry
I am looking for packing spheres (can be monodisperse or polydisperse with known radii distribtuions) inside a geometry. I am sure this is a well explored scientific problem with applications in ...
2
votes
2answers
93 views
Is the similar subdivision of a delaunay mesh still delaunay?
I have a delaunay triangulation for a 2d box with say an airfoil inside. If I uniformly refine this mesh by subdividing each triangle in the mesh into 4 triangles by halving each edge, is the ...
2
votes
1answer
70 views
How to divide points on a 3D complex surface into two regions based on a closed curve defined on this surface?
My problem seems simple but I can't find an algorithm that will do that for me for any 3D complex surface.
I have a really complex shape 3D surface and a closed curve on it defined by some points (...
0
votes
1answer
34 views
Produce vertex displacements from volumetric shrinkage data on unstructured meshes
I was wondering what would be an efficient way to produce compatible displacements for mesh nodes/vertices if the computed data is volume shrinkage of each element/cell in the unstructured mesh?
...
1
vote
0answers
67 views
How to approach geographic data interpolation by distance?
let's say I have a set of geographic locations (lat, lng) resulting from a query. Those locations have some kind of internal ranking, my set is sorted by this number in a descending order.
Now I'm ...
0
votes
1answer
39 views
How to find the nearest point inside a list in a given direction
Being $\bar{\mathbf{x}} \in \mathbb{R}^3$ a point and $S =\{\mathbf{x}\}_{i=1}^N \in \mathbb{R}^3$ a sample of N points. I am looking for a simple algorithm to determine the nearest point in $S$ in ...
5
votes
1answer
74 views
Maximum and Minimum distance from query point within bounding box
I'm reading an article regarding approximating sums using KD-trees (similar to FMM).
As part of the effort I'm trying to make sense of this article , which is cited.
I'm having trouble understanding ...
3
votes
2answers
107 views
Find shortest path around a cylinder represented by 3d triangular mesh
Suppose I have a 3d triangular mesh with the topology of a finite cylinder. Let $C$ be a vertex on that mesh.
How can I find the shortest path from $C$ to itself that goes around the cylinder? By ...
1
vote
0answers
61 views
Derivatives over a Finite Element mesh
I have a data extracted from Comsol on some node points and I know the coordinates of each node.
Does anyone know how Comsol calculate the partial derivative from the values at each node and also ...
0
votes
0answers
44 views
Dividing Point Cloud into voxels
I am reading a paper on implementing convolution neural network for a 3D point cloud. In this paper, they are dividing the point cloud into voxels. Is there any easy way to do it using point cloud ...
2
votes
0answers
30 views
Check if two points are symmetrics/asymmetrics
I am working on an Android app which lets a group of children draw whatever they want in a specific area. I need to check if the lines and figure that they draw are symmetric. The problem is that ...
2
votes
0answers
62 views
Efficient algorithm to determine the intersection volume of simple convex polyhedra
TLDR: Is there an efficient algorithm to compute the intersection of polyhedra with 8 or fewer vertices?
I have two sets of FEM meshes for one geometry (one exhibiting a skin effect). I have to ...
2
votes
0answers
37 views
Algorithm to join hexahedra and obtain outline volume
I would like to join several hexahedra and obtain an outline volume.
First, I started with 2D implementation. In 2D, there are non-intersecting quadrangles which always touch each other as shown in ...
0
votes
0answers
77 views
How to read data from simply formatted text file (c++)?
Mesh information like points, faces and cells is to be stored into separate files:
e.g. for points file:
# points data: x y z
N_Points 100
x1 y1 z1
x2 y2 z2
...
cell file:
# cells data: ...
35
votes
18answers
9k views
Good examples of “two is easy, three is hard” in computational sciences
I recently encountered a formulation of the meta-phenomenon: "two is easy, three is hard" (phrased this way by Federico Poloni), which can be described, as follows:
When a certain problem is ...
4
votes
1answer
106 views
How can one prove the duality of Voronoi and Delaunay?
Hoping I'm not misunderstanding the concept here, but it is my understanding that Voronoi Diagrams and Delaunay Tesselations are 'dual' to one another, owing to the fact that each' solution makes ...
3
votes
0answers
51 views
Calculating depth mask from different lighting
I have a object which is static, the camera is static and light source is moving. How can the depth mask be calculated ?
Concept is to use - calculate height from shadow length
Lets imagine a have ...
2
votes
0answers
47 views
Cover a polygon with least amount of parallelograms [closed]
I am solving the task that is as follows:
Input: a polygon. Can be any kind of polygon without self intersections. Can be a non-convex and with holes inside.
Goal: to cover it with 2 (at least) or ...
7
votes
1answer
203 views
How to calculate the geodesic curvature of a discrete 3D curve?
I have coordinates of a set of points that form a closed loop that lies in a 3D surface. I know the equation of the surface and I can calculate it's surface normal at any point. I found that for a ...
0
votes
2answers
131 views
Ordering points from X Y coordinates
I have series of points extracted from a regular grid, with their X/Y coordinates. A previous algorithm (that I cannot modified!) output a list of these coordinates, but the ordering of these point is ...
2
votes
2answers
74 views
projective reconstruction from orthogonal views
This is a problem from projective geometry. Suppose I have a vector $z \in R^k$ of unit length $\| z \| =1$ inside a $k$-dimensional hypercube. I don't know its value but do know its projection upto ...
3
votes
1answer
70 views
Smoothness regularisation of a 2D field on a triangular mesh?
I'm working on an inverse problem where the solution is the values of a 2D scalar field at the vertices of a 2D triangular mesh, such that the field can be defined continuously inside the mesh via ...
2
votes
1answer
364 views
A robust algorithm to sort a non-convex polygon vertices
Let v_{0},...,v_{N-1} be N points in a Cartesian xy plane defining the vertices of closed polygon (i.e. v_{N} = v_{0}).
Let P_{0}...
1
vote
1answer
136 views
Node renumbering in a 2D mesh
I have a 2D domain which is discretized using Q4 elements. I have the nodal positions and the element connectivity matrix. I would now like to renumber the nodes in such a way that all the interior ...
1
vote
1answer
217 views
How to generate a face list from vertices?
I have a little background in writing toy finite volume CFD codes. In 2D Cartesian scenarios, I typically take $x_{\min}$, $x_{\max}$, $y_{\min}$, $y_{\max}$, and the number of points in $x$ and $y$ ...
2
votes
0answers
125 views
Efficient root finding algorithm for monotonic function
This is my first time asking a question here, so I may not be asking this in the right place. I am trying to find the roots of a monotonic function with as few function evaluations as possible.
I ...
3
votes
0answers
46 views
Minimum axis aliged bounding box of convex polytope
I need to compute a $n-$dimensional integral with $n<10$ on a convex polytope. Since most numerical integration libraries (e.g. Cuba) expect the function to be integrated defined inside an axis ...
3
votes
1answer
345 views
Smallest circumscribed circle in spherical geometry
I work in Python 3 on astrophysics projects. I need to compute the smallest circumscribed circle of a set of points in the sky (so described by Right Ascension and Declination). I have found a code ...
3
votes
0answers
51 views
Approximate the largest simplex in N-dimensional Delaunay triangulation
I am working on determining the spatial information of a set of $M$ points in $N$-dimensional space. It is well-known that the construction of Delaunay triangulation is expensive in high dimensional ...
1
vote
0answers
50 views
Uniformly sample a point per polytope
I want to uniformly sample a point within each of $10^5$ convex polytopes in each iteration of a solver.
The polytopes in one iteration are completely different from the polytopes in another iteration....
2
votes
0answers
208 views
How to numerically optimize affine transformations?
I need to optimize affine transformations for of a set of triangles using energy function based on the connectivity.
The energy of an edge $e_j$ between triangles $T_a, T_b$ is given by
$$
E_j = \...
0
votes
1answer
103 views
Compute outward normal and surface area for 8 noded brick element in FEA
I have a cube which is divided into 8 small cubes by bisecting each edge, I am trying to find out the surface area of each of the faces and the corresponding outward normals for them. This operation ...
0
votes
1answer
586 views
Connectivity matrix in Finite Element Method in Triangular elements
Imagine a simple triangular base mesh in finite element method with an unknown number of elements (varying by the user). How can connectivity matrix be coded to be generated automatically?
6
votes
1answer
335 views
Putting N hard spheres randomly in given volume
I need to put $N$ spheres with given radius $R$ randomly in a Volume $[-0.5,0.5]^3$, without any overlap of spheres.
If I choose values so that all the spheres will occupy ~57% of the total volume, I ...
1
vote
0answers
191 views
Use of Morton Key to reduce number of grid points
I asked a question on Stack Overflow Performance Issue with VP Trees and Nearest Neighborsand I was not satisfied with the answer and so I thought I would reword my question for this site and post ...
1
vote
2answers
1k views
Uniform dots distribution in a sphere
I'm trying to implement Barnes-Hut algorithm, with a binary tree. My initial conditions are a uniform mass distribution in a sphere with radius $R$. How can I create uniform dots distribution in a ...
2
votes
1answer
161 views
Can the Power Method be used here?
Given a set of $n$ points on which a triangulation is performed, it is possible to construct coefficients $\lambda_{ij}>0$ such that each point $x_i$ is a convex combination of the points connected ...
2
votes
0answers
68 views
Simultaneous update to barycenters
Suppose a tiling is given in 2D (an embedding of a planar triangulated graph), with all faces convex.
Now suppose one moves each point, one by one, to the barycenter of its neighbors. I think that ...
4
votes
0answers
83 views
What Derivative-free optimization method should I use when my initial guess is very good?
I am trying to minimize a function where my initial guess is quite close to the minimum.
I'm trying to minimize
$$f(q) = \text{angle}(qw_1q*, v_1) + \text{angle}(qw_2q*, v_2) + \text{angle}(qw_3q*, ...
