# 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
Filter by
Sorted by
Tagged with
1 vote
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 ...
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. ...
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 ...
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 ...
1 vote
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 ...
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-...
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 ...
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 ...
1 vote
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 ...
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 ...
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....
73 views

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 ...
1 vote
46 views

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. ...
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 ...
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 ...
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 ...
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)$. ...
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 ...
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 ...
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 ...
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. ...
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 ...
1 vote
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
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?...
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, ...
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—...
1 vote
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 ...
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 ...
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:...
1 vote
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 ...