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.
213
questions
-1
votes
1answer
30 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
33 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, ...
1
vote
1answer
45 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
23 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 ...
2
votes
2answers
78 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 ...
1
vote
2answers
89 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
67 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
66 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
53 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
102 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
57 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
41 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
60 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
36 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
76 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: ...
30
votes
16answers
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 ...
2
votes
0answers
71 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
50 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
153 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
126 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
296 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
117 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
163 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
121 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
45 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
299 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
49 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
49 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
179 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
98 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
425 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
309 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
185 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
907 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
159 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*, ...
4
votes
2answers
522 views
3D contour mesh computation
I have the value of a function in three dimensions, $f(x, y, z)$, which varies smoothly.
I would like to compute a 3D mesh where $f(x, y, z)$ has a particular value.
Are there algorithms to do this? ...
5
votes
1answer
225 views
Integrating/Implementing NURBS-related calculations
Recently, I started to develop some codes that use NURBS (general things I intend to use/already using: spline generation, interpolation, grids, isolines, closest-point find, and many others), both ...
2
votes
1answer
66 views
Polygon approximation with a circle
There is an article describing how to detect a pupil from an eye photo.
A.-H. Javadi, Z. Hakimi, M. Barati, V. Walsh, and L. Tcheang, "SET: a pupil detection method using sinusoidal approximation," ...
3
votes
0answers
92 views
Fast Algorithms for the Simplicial Decomposition of a Convex Polytope in N-Dimensions
I'm in the process of constructing an algorithm which computes the Voronoi diagram of a set of points, but I now need a method to decompose each Voronoi cell into simplices. The information we have is:...
1
vote
0answers
57 views
Efficient initial identification of solid or liquid domains for a block structured Cartesian grid generation system
INTRO
Within the last 5 days I was able to generate a block structured Cartesian grid
generation system with a combination of Fortran,C++ and Python.
I am running intersection tests of the ...
0
votes
1answer
112 views
Which free library should I use to perform cutting/clipping operation?
I have a set of points which forms a closed loop, and I want to perform cutting/clipping a 3D model using this loop. I have used VTK but in some cases, it has a "Cannot follow edges" problem.
Is ...
0
votes
1answer
85 views
Gmsh exporting wrong mesh DATA [closed]
so hopefully I'll be using gmsh to make meshes out of 2-D cross sections with o thickness. I tried to make a structured mesh with quad elements of a rectangular ...
