Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

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.

Filter by
Sorted by
Tagged with
1 vote
2 answers
65 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 -...
2 votes
0 answers
101 views

Efficiently detect overlaying ellipses in distorted images

I'm currently facing the problem of efficiently detecting (special) ellipses in edge images. These images are given (i.e. previous image processing is impossible) and contain quite some noise. I need ...
2 votes
1 answer
189 views

Need help with the python code: Calculating Madelung constant CsCl crystal structure

Need help with the code to estimate the Madelung constant for CsCl lattice: Cs at (0,0,0) Cl at (0.5, 0.5, 0.5) Answer: Converged value I am getting is 0.465. ...
1 vote
2 answers
108 views

Cover a 3D surface with 2D rectangles of fixed size, allowing overlap

I have a 3D surface, defined as collection of points in a 3D evenly spaced mesh. I have a rectangle of fixed size (height x width), and I need to find a collection of rectangles positions in the 3D ...
3 votes
0 answers
148 views

Population of the coefficient matrix of a linear system Ax=b stemming from the finite differences of an arbitrary geometry

I've been looking into solving a linear system $$Ax=b$$ where $A\in\mathbb{R}$ is the sparse coefficient matrix of size $K\times K$, $b\in\mathbb{R}$ is the right-hand side (i.e., the source term) of ...
1 vote
0 answers
45 views

Find a set of positions of a rectangle of fixed size, which would "cover" a curve on a plane

I have a curve on a plane, and a rectangle with one side much longer than the other (let's say it is a "thick segment). I need to find a set of positions of the rectangle which would include all ...
3 votes
1 answer
150 views

Role of rotation's pivot point in optimization?

In this paper, the authors describe how to use locally rigid transformations (sampled on nodes in space) to deform mesh vertices. In the paper, rotations are relative to the pivot point, which ...
2 votes
1 answer
401 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
1 answer
95 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 ...
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 ...
0 votes
1 answer
49 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. ...
0 votes
0 answers
37 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
1 answer
60 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 ...
0 votes
0 answers
60 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-...
5 votes
1 answer
408 views

Efficient root finding algorithm for monotonic function

I am trying to find the roots of a monotonic function with as few function evaluations as possible. I have approximated a manifold with a piece-wise defined polynomial. The manifold is periodic and so ...
0 votes
0 answers
38 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
29 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
3 answers
301 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 ...
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 ...
0 votes
0 answers
121 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....
0 votes
1 answer
98 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 ...
3 votes
1 answer
95 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 ...
2 votes
1 answer
136 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....
2 votes
0 answers
218 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 ...
1 vote
0 answers
70 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\}...
40 votes
23 answers
10k 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
1 answer
242 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 ...
20 votes
2 answers
6k views

Unstructured quad mesh-generation?

What is the best (scalability and efficiency) algorithms for generating unstructured quad meshes in 2D? Where can I find a good unstructured quad mesh-generator? (open-source preferred)
0 votes
0 answers
109 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 ...
2 votes
0 answers
42 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
42 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 ...
2 votes
1 answer
99 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 ...
3 votes
1 answer
918 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 ...
0 votes
1 answer
112 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 votes
1 answer
66 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 ...
1 vote
2 answers
4k 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 ...
1 vote
0 answers
137 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 ...
2 votes
0 answers
78 views

Geometric interpretation of lemma

I am currently studying eigenvalue problems. I already worked through the minimax-principles and seen why $\lambda_{h, m} \geq \lambda_m$, when comparing the eigenvalues of a discretization and the ...
1 vote
1 answer
59 views

Error in Maple's CellDecomposition Command [closed]

I have a simple system that I want to process with the CellDecomposition command of Maple. I don't know why Maple is giving an error here! The code is ...
2 votes
0 answers
131 views

Closed-form Jacobian of SE(3) element with 6-degrees of freedom

Let $A$ and $B$ be two rigid transformations in 3D space that transform things from global to local coordinates. Let their relative transformation be expressed by $W=AB^{-1}$. $W$ can also be ...
2 votes
0 answers
80 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 ...
0 votes
3 answers
155 views

Problem of half-planes intersection

Consider the half-planes $\{x \leqslant 2\}$ and $\{x+y \leqslant 3\}$. These two half-planes are coded with the R package 'rcdd' as follows: ...
3 votes
0 answers
68 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 }...
2 votes
2 answers
141 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. ...
3 votes
1 answer
202 views

Project to nearest point on convex polytope

I have a point $y \in \mathbb{R}^d$ and a convex polytope $\mathcal{P}$ given as the intersection of half-spaces: $$\mathcal{P} = \{x \in \mathbb{R}^d \mid a_1 \cdot x \le b_1, \dots, a_n \cdot x \le ...
9 votes
1 answer
803 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 ...
0 votes
0 answers
47 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 ...
14 votes
2 answers
4k 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 ...
10 votes
2 answers
2k views

Is there an algorithm to find an almost-convex hull given a tolerance angle?

I'd like to know if there is an algorithm that given a set o points and an angle computes the convex-hull if the angle is $\alpha = 0$ and given an $\alpha > 0$ computes an envelope that follows ...
4 votes
2 answers
357 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 ...

1
2 3 4 5 6