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.
280
questions
1
vote
0
answers
20
views
Order in a subset
Lets consider a range of "K" binary digit numbers. In that range, we want to take a subset of those values which have (<="n" consecutive 0s) AND (<="n" consecutive ...
- 11
0
votes
1
answer
43
views
How do you build a polyharmonic discrete system?
Polyharmonic equations, to my understanding, are defined as:
$$\Delta ^k u = 0$$
i.e. one repeatedly applies the laplace operator to the function a certain number of times and the result must be 0.
...
- 263
0
votes
1
answer
78
views
Computing discrete laplacian matrix for mesh fairing
I asked this question on the math stack exchange and got an answer, but I am just as utterly confused as before. My fundamental goal is to actually construct the matrix, that is, a series of steps I ...
- 263
0
votes
0
answers
32
views
Constructing generalized Laplacian matrix?
I am staring intently at this paper by Botsch and Kobbelt.
In particular, I want to make the matrix specified in equation 5. I am trying to understand the specific computations I must instruct a ...
- 263
1
vote
1
answer
53
views
Optimization: Find minimizer along linestring
Given some function f(x) and a set of points A representing a linestring (or polygonal chain), I am searching for the point on ...
- 11
0
votes
0
answers
57
views
Algorithm for 1-dimensional minimal surfaces
Consider a set of points. For simplicity, let's say that those are 2D points (although the problem works in higher dimensions as well). The goal is to find the minimum possible length of a connected 1-...
0
votes
0
answers
36
views
Equilibrium position finding with DSM
I've coded a framework that can be used to simulate the dynamic behavior of a system discretized by particles (nodes) that are connected by spring-damper elements. However, I want to compare it to a ...
0
votes
0
answers
28
views
Parallel Block-Structured class abstraction for FDM
I’m currently developing a FDM/FVM (using contravariant coordinates) code using Fortran and Co-Arrays (SIMD, in general), and so far I have all sparse matrix (BiCGStab, working on AMG) solvers and ...
- 251
1
vote
3
answers
197
views
Partial derivatives for triangular meshes (in 3D)
A grid offers an obvious definition for the partial derivatives at a grid point, given
$x$ the value of a point $p$ in an $n$ dimensional grid, the forward partial derivative that point for coordinate ...
- 263
0
votes
1
answer
49
views
Finding maximums in mesh of graph?
I have a triangle mesh which is an approximation of a smooth graph. i.e. a scalar function of $xy$.
I am interested in finding extrema. One naive way I did it was to look at some number of points ...
- 263
0
votes
0
answers
77
views
Adding stability to MPM simulation?
I am writing a 2D implementation of MLS-MPM, I have fluids working perfetly fine, solids technically work as well, at low time steps.
This is the fluid simulation at a large time step:
https://i.stack....
- 263
0
votes
1
answer
73
views
How to get a normalized gradient with FreeFem++?
I am trying to use FreeFem++ to solve the heat geodesics algorithm.
The algorithm is:
solve $\dot u = \Delta u$ at a specific time $t$.
compute $X = \frac{\nabla u_t}{|\nabla u_t|}$
solve $\Delta\phi ...
- 263
3
votes
1
answer
86
views
Suggestions for libraries that can numerically compute geodesics from a given Riemannian metric?
I am dealing with a non-trivial Riemannian metric $H$ defined on a particular subset of Euclidean space ($E \subset \mathbb{R}^n$). I was able to show the Riemannian manifold $(E,H)$ is geodesically ...
- 131
2
votes
1
answer
134
views
Computing numerical derivatives
I am trying to create a sweeping surface, for which I need the frenet frame of a curve. I am trying to compute this for arbitrary curves but for testing I am just using the parametric unit half circle....
- 263
2
votes
0
answers
116
views
Delaunay-based isosurface extraction vs marching cubes
I recently tried the isosurface extraction algorithm provided by the C++ library CGAL. This is new to me. It is based on Delaunay triangulations.
I have some experience with the marching cubes, I ...
- 283
1
vote
0
answers
65
views
Maximal "Convex Augmentation" of a Triangle in 2D Mesh
Consider a convex polygon in $\mathbb{R}^2$ with multiple convex holes in it and suppose that, for now, we have a 2D triangular mesh of the polygon, which is represented by $\mathcal{T} \equiv\{T_i\}...
- 11
4
votes
1
answer
228
views
Selecting most points from a set of points with distance constraint
I am looking for an algorithm to select the largest subset of $M$ points from a set of $N$ points ($M < N$) such that no point is within a certain minimal distance d to any other point in $M$? I ...
- 143
1
vote
1
answer
46
views
robustness of geometric predicates in Euclidean vs homogeneous coordinates
The signed volume of the triangle formed by the points $p, q, r$ in the plane is defined to be
$$\text{volume}(p, q, r) \equiv \det\left[\begin{matrix}q_1 - p_1 & r_1 - p_1 \\ q_2 - p_2 & r_2 -...
- 9,813
0
votes
0
answers
81
views
Open source implementations of the medial axis transform for vector shapes
Are there any open source implementations of the medial axis transform for vector shapes?
I have searched without finding any useful results. It seems that CGAL library doesn't have it implemented nor ...
- 101
2
votes
0
answers
39
views
How to generate coordinate points of a smallcircle on earth
I am looking up celestial navigation, and according to
https://youtu.be/-ARXW8InStY?t=3320
a specific sun angle reading (sun angle above the horizon) will be the same on a small-circle with the centre ...
1
vote
0
answers
37
views
Difference between Numeric, Combinatorial, and Geometric Computing
In the paper [1], author has discussed a distinction between the 3 types of computations: numeric, combinatorial, and geometric. The author says that Geometric computation is one that has elements of ...
- 111
2
votes
1
answer
88
views
Min supporting line of a set of points
I am following along Rourke's book and I am trying to do the excercies mentioned in this SO post:
Min supporting line for a set of points
Design an algorithm to find a line 𝐿 that:
has all the ...
- 263
0
votes
1
answer
106
views
Aerofoil study using CFD, struggling to find aerofoil coordinates
I’ve been messing around with Ansys and I’m struggling to find the aerofoil coordinates for a NACA 66-012?
I looked on Airfoil tools, but it doesn’t allow you to generate a 6 series aerofoil, only 4 ...
- 1
0
votes
1
answer
64
views
Convergence of FEM on curved boundaries, and inhomogenous boundary data
In a smooth domain in $\mathbb{R}^{2}$ or $\mathbb{R}^{3}$ let's consider $-\Delta u = f$ with $u=g$ on a part of the boundary and $\partial_\nu u = w$ on another part of the boundary, which is far ...
- 127
1
vote
0
answers
94
views
From 3D to 2D with a STL file
I would like to do a 2D projection from a 3D geometry saved in a stl file and know the distance between the two projected planes. In order to explain better the concept I will start with an almost ...
- 99
2
votes
0
answers
74
views
Geodesic approximation algorithms for minimal geodesic curvature
Introduction
I am building an application in which, given a surface and a pair of points on it, an analytic expression of some geodesic arc between them is needed, preferably the one with the shortest ...
- 121
3
votes
0
answers
64
views
Change in Variables applied to biharmonic equation
Background
I want to solve the following biharmonic equation:
$$\frac{ \partial^4 s }{ {\partial \xi}^4 }+\frac{ \partial^4 s }{ {\partial \xi}^2{\partial t}^2 }+\frac{ \partial^4 s }{ {\partial t}^4 }...
- 31
2
votes
2
answers
87
views
How to find fundamental matrix based on other fundamental matrix and camera movement?
I am trying to speed up some multi-camera system that relies on calculation of fundamental matrices between each camera pair.
Please notice the following is pseudocode. ...
- 121
9
votes
1
answer
654
views
How to find the smallest ellipse covering a given fraction of a set of points?
I have a set of points $P$ and want to find the ellipse with the smallest area that covers at least a fraction $f$ of these points. How can I do this?
These questions ask the same thing, but folks ...
- 3,891
0
votes
0
answers
45
views
Find tuples of points from multiple sets
Given n sets of points in general position in dimension 2 (n typically small, 2-6), can one find tuples of points, one from each of the sets, which are close in some sense (the closest, mutual ...
- 101
12
votes
2
answers
3k
views
How do I find the minimum-area ellipse that encloses a set of points?
I have a set of points that resembles more of an ellipse than a circle. I implemented the optimization formulation below and the solution gives a circle. I tried with various initial values, still to ...
- 123
3
votes
0
answers
142
views
The implicit form of a NURBS curve
I am trying to evaluate and analyse a NURBS curve to generate a mechanism. I understand that the general form of a NURBS curve is commonly written as a parametric equation in the form of $f_{par}(t)$.
...
- 31
4
votes
2
answers
329
views
Computation of the tensor of curvature on surface mesh
Is there a formula which enables the computation the tensor of curvature knowing the following at each vertex and cell of a triangulated mesh:
Normal vector
Two arbitrary vectors in the tangent space
...
- 65
-1
votes
2
answers
119
views
Calculating versors of a plane from the normal versor
I'm trying to calculate the 2 perpendicular versors (unit vectors), $\vec{n_1}$ and $\vec{n_2}$, that define a plane whose normal versor (unit vector) is $\vec{n_n}$.
For example, assuming that the ...
- 3
2
votes
1
answer
76
views
Dividing a continuous domain into small squares; how to perform storage and querying?
I recently had a software engineering interview and was asked a series of questions that was a bit outside of knowledge realm, and I feel like there's some scientific computing principles here (I took ...
- 143
2
votes
0
answers
68
views
Extracting a mid-plane for thick shell analysis
I have a complex part that contains features of the form shown in the figure below.
Because of the cost of 3D finite element simulation of the part, I want to try an analysis with 2D thick shells.
...
0
votes
0
answers
141
views
Getting euclidean distance between vector A and C without anyway of retrieving them when their distances with a common vector B is known
Motivation:
My plan is to get the overall euclidean distance matrix for all the vectors in N number of dataset. Each dataset is basically an array of n-dimensional points. For e.g: A dataset can be ...
- 11
1
vote
0
answers
76
views
How to determine the orientation of convex/concave hexahedra?
I am writing a code that checks the orientation of a list of vertices (along with face connectivity) describing both convex and concave hexahedra. The face connectivity table stores the list of vertex ...
- 233
0
votes
1
answer
324
views
Algorithm to convert STL files to STEP files
My goal is to learn the algorithms that allow to convert STL files to STEP files.
I am struggling to find learning materials.
Can you suggest here research papers, books, open source code about this ...
- 103
1
vote
2
answers
616
views
Dyadic operations, fourth order tensors and Tensor algebra
I am trying to understand the dyadic operation for a while since I am interested in Elasticity problems. I believe an intuitive understanding (rather than assuming) will give me good problem solving ...
0
votes
0
answers
79
views
How to distinguish primary hosts (stars) and orbiting satellites (planets) and tertiary bodies (moons) by their mass and trajectory?
I posted this question in the astronomy stackexchange. There are no responses, and it was suggested that I pose the question here. The "too long, didn't read" was taken from a comment, and ...
- 11
3
votes
0
answers
640
views
Jacobian Matrix of 2D element mapped to 3D
Note: I previously posted this question to MathStackExchange, but got no attention there. So I'm rewritting and trying over here.
Problem summary
Given a common¹ set of shape functions defined at ...
- 39
0
votes
1
answer
159
views
Parametric surface in 3D
I want to create a mesh for a 3D surface with coordinates defined by a parametric function. Is it possible to define this mesh using Gmsh? If it is not possible, what free software do you recommend me?...
- 515
4
votes
1
answer
131
views
Solving geodesics on triangular meshes gives negative distances
I have implemented the heat method for geodesics:
https://www.cs.cmu.edu/~kmcrane/Projects/HeatMethod/paperCACM.pdf
When I run it I am getting a solution that, visually, seems correct:
In this image, ...
- 263
3
votes
0
answers
90
views
Why is bounding a surface with a capsule is better than with a cylinder to detect intersections?
In this article:
https://www.geometrictools.com/Documentation/IntersectionOfCylinders.pdf
the writer says: "If you plan on using cylinders
for bounding volumes in a real-time graphics engine—...
- 81
1
vote
1
answer
149
views
Calculate the arc length of a Steinmetz curve numerically
I'd like to know the length made by the intersection curve of two orthogonal cylinders of different radii a and b where a > b >0.
I came across this post that provides a solution with an ...
3
votes
1
answer
103
views
Good rectangular covering of an SDF
I have a 2D SDF describing my shape, but it's fine to think of it as a black/white image (black="inside" white="outside").
I want to generate a small set of rectangles (say, 8 of ...
- 131
5
votes
1
answer
1k
views
Algorithm to merge two polygons (using connectivities)?
I am struggling with implementing an algorithm that does one simple thing:
Consider two polygons (one can just draw any two polygons and number their vertices), whose connectivities in a node list are:...
- 155
1
vote
0
answers
58
views
Largest triangle that contains a point
Given the location of $n$ points on a 2D plane ($P_1, P_2, \ldots, P_n$); and the location of a special point $X$.
Find three points $P_i,P_j,P_k$ ($i \neq j \neq k$) such that point $X$ is inside the ...
0
votes
0
answers
56
views
Storing and retrieving two-dimensional and three-dimensional data
I work on computational geometry.
A huge number of two-dimensional and three-dimensional data are found in my project. Coordinates of polygon and polyhedrons vertices consisted of two-dimensional and ...
- 11