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
2 votes
0 answers
99 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 ...
hello_darkness's user avatar
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 ...
Akhaim's user avatar
  • 83
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 ...
Fabio's user avatar
  • 121
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 ...
Fabio's user avatar
  • 121
2 votes
1 answer
179 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. ...
chola's user avatar
  • 21
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 ...
jordi's user avatar
  • 31
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 ...
user46385's user avatar
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. ...
Makogan's user avatar
  • 263
0 votes
1 answer
93 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 ...
Makogan's user avatar
  • 263
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 ...
Makogan's user avatar
  • 263
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 ...
Citizen3011's user avatar
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-...
Relja Šegvić's user avatar
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 ...
AlexBatch's user avatar
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 ...
Kbzon's user avatar
  • 251
1 vote
3 answers
283 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 ...
Makogan's user avatar
  • 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 ...
Makogan's user avatar
  • 263
0 votes
0 answers
112 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....
Makogan's user avatar
  • 263
0 votes
1 answer
92 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 ...
Makogan's user avatar
  • 263
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 ...
Spencer Kraisler's user avatar
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....
Makogan's user avatar
  • 263
2 votes
0 answers
209 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 ...
Stéphane Laurent's user avatar
1 vote
0 answers
69 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\}...
ArGenya's user avatar
  • 11
4 votes
1 answer
241 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 ...
doom4's user avatar
  • 143
1 vote
2 answers
59 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 -...
Daniel Shapero's user avatar
0 votes
0 answers
105 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 ...
Amazigh_05's user avatar
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 ...
Lasse Karagiannis's user avatar
1 vote
0 answers
41 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 ...
shivams's user avatar
  • 111
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 ...
Makogan's user avatar
  • 263
0 votes
1 answer
111 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 ...
Culkins's user avatar
-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 ...
Lilla's user avatar
  • 259
1 vote
0 answers
135 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 ...
Daniel's user avatar
  • 99
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 ...
Stamatis's user avatar
  • 121
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 }...
Tom Tenor's user avatar
2 votes
2 answers
130 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. ...
Gulzar's user avatar
  • 121
9 votes
1 answer
771 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 ...
Richard's user avatar
  • 3,961
0 votes
0 answers
46 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 ...
jjg's user avatar
  • 101
14 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 ...
physicsnovice's user avatar
3 votes
0 answers
171 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)$. ...
Nicholas's user avatar
4 votes
2 answers
347 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 ...
Al-Farouq's user avatar
-1 votes
2 answers
140 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 ...
Federico's user avatar
2 votes
1 answer
78 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 ...
user5965026's user avatar
2 votes
0 answers
72 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. ...
Biswajit Banerjee's user avatar
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 ...
Shihab Ullah's user avatar
1 vote
0 answers
78 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 ...
niran90's user avatar
  • 233
0 votes
1 answer
400 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 ...
blunova's user avatar
  • 103
1 vote
2 answers
795 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 ...
Bruce Lee Jun Fan's user avatar
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 ...
zeebeel's user avatar
  • 11
3 votes
0 answers
775 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 ...
CStudent's user avatar
0 votes
1 answer
178 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?...
yemino's user avatar
  • 515
4 votes
1 answer
132 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, ...
Makogan's user avatar
  • 263

1
2 3 4 5 6