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
0 answers
35 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 ...
user avatar
  • 89
0 votes
0 answers
28 views

Compute harmonic (isothermal) coordinates u-v from harmonic function field

I am trying to implement a harmonic map from a surface with a boundary to a unit circle in python. I found this algorithm by Xianfeng Gu, which is almost straight forward: harmonic mapper algorithm ...
user avatar
2 votes
0 answers
48 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 ...
user avatar
  • 121
3 votes
0 answers
57 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 }...
user avatar
2 votes
2 answers
68 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. ...
user avatar
  • 121
9 votes
1 answer
480 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 ...
user avatar
  • 3,111
0 votes
0 answers
35 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 ...
user avatar
  • 101
12 votes
2 answers
1k 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 ...
user avatar
3 votes
0 answers
78 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)$. ...
user avatar
4 votes
2 answers
191 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 ...
user avatar
-1 votes
2 answers
75 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 ...
user avatar
2 votes
1 answer
73 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 ...
user avatar
2 votes
0 answers
50 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. ...
user avatar
0 votes
0 answers
138 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 ...
user avatar
1 vote
0 answers
57 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 ...
user avatar
  • 213
0 votes
1 answer
187 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 ...
user avatar
  • 103
1 vote
2 answers
291 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 ...
user avatar
0 votes
0 answers
76 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 ...
user avatar
  • 11
3 votes
0 answers
386 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 ...
user avatar
0 votes
1 answer
79 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?...
user avatar
  • 503
4 votes
1 answer
121 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, ...
user avatar
  • 143
3 votes
0 answers
69 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—...
user avatar
  • 81
1 vote
1 answer
112 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 ...
user avatar
3 votes
1 answer
90 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 ...
user avatar
  • 131
4 votes
1 answer
310 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:...
user avatar
  • 145
1 vote
0 answers
38 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 ...
user avatar
0 votes
0 answers
51 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 ...
user avatar
  • 11
0 votes
3 answers
139 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: ...
user avatar
4 votes
3 answers
530 views

How to determine if 2 rays intersect?

We are given the 2D coordinates of 2 points: the first point is where the ray starts and it goes through the second point. We are given another ray in the same way. How do we determine if they have a ...
user avatar
0 votes
0 answers
22 views

Minimal covering of rectangle with fixed, overlapping rectangles

A finite set $R$ of fixed, axis aligned 2-D rectangles $r_i=\left\{x_{0i},y_{0i},W_i,H_i \right\}$ is given. These rectangles are potentially overlapping. Given a new axis aligned rectangle $t$, I ...
user avatar
  • 301
0 votes
0 answers
45 views

Hi I am trying to model a 2D Lug angle using Gmsh 4.6. How can I combine transfinite quad and regular full quad meshes in the following geo file?

I need transfinite mesh a small section of the bolt hole to insert a crack. However, The transfinite mesh and regular full quad mesh seem being incompatible and throwing errors. How can I combine ...
user avatar
0 votes
0 answers
80 views

Producing Voronoi diagram in three dimensional

A Voronoi diagram is a kind of tesselation that divided the medium into polygons in 2D and polyhedrons in 3D. Although there are many algorithms to construct a Voronoi diagram, some of them are faster ...
user avatar
  • 11
1 vote
0 answers
164 views

Fortune algorithm for voronoi diagram

Although there are many algorithms to construct Voronoi diagram, some of them are faster than others. Based on my knowledge Fortune algorithm is fastest for construct Voronoi diagram either in two ...
user avatar
  • 11
3 votes
3 answers
353 views

What are some algorithms to calculate the width of an arbitrary polygon when a bounding box approximation is inaccurate

What are some alternative algorithms to creating a bounding box for finding the max width of a concave, simple winding polygon, like the one in the below image? I prefer solutions that are more ...
user avatar
  • 131
2 votes
3 answers
258 views

For traditional FEM and FVM, why can't we use mesh to represent geometry and use the mesh which represent the geometry to do the computation directly?

Isogeometric analysis [1] has the advantage of integrating geometric and mesh models using NURBS or Spline. At the same time, I would like to ask a question to my friends: for traditional FEM and FVM, ...
user avatar
  • 105
4 votes
4 answers
242 views

Can the mesh generation methods in FVM and FEM be totally based on the knowledge of the mesh generation theory in computer graphics?

The main references of mesh generation methods in computer graphics (CG) I found are discrete Differential Geometry [1] and a famous book "Polygon Mesh Processing" [2], while the "...
user avatar
  • 105
3 votes
1 answer
166 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 ...
user avatar
  • 350
0 votes
0 answers
146 views

Surface mesh from labeled 3D points

I'm trying to figure out how to create a surface mesh from a set of labeled 3D points. The 3D object could be something like part of a cave system or asteroid where there would be parts of the surface ...
user avatar
7 votes
0 answers
278 views

Finding points inside cells of power (generalized Voronoi) diagram

Suppose we have a set of points $p_1,\ldots,p_n\in\mathbb R^d$ as well as a set of weights $w_1,\ldots,w_n\in\mathbb R$. Recall that the power cell associated to the pair $(p_k,w_k)$ is given by: $$\...
user avatar
0 votes
2 answers
129 views

How to minimize $(x-a)^2+(y-b)^2$ subject to $ \sqrt{a}+\sqrt{b}=\sqrt{2}$?

I am not sure if this is on-topic here, but I am trying. Let $x,y$ be positive real numbers. I am trying to find $$ \min_{\sqrt{a}+\sqrt{b}=\sqrt{2}}(x-a)^2+(y-b)^2$$ I tried using Mathematica for ...
user avatar
0 votes
1 answer
100 views

Applying weak form

I have two dimensional equation and I want to solve it using Finite Element Methods. $$ \nabla . (\alpha(x,y)\nabla u(x,y)) + \dfrac{\partial u(x,y)}{\partial x}+\dfrac{\partial u(x,y)}{\partial y}+u(...
user avatar
5 votes
0 answers
69 views

Why does the naive barycentric hodgestar fail?

The discrete exterior calculus is defined first using circumcentric dual cells, because the primal and dual edges are orthogonal and thus the dual cells are convex. This leads to a diagonal hodge star ...
user avatar
  • 587
0 votes
1 answer
1k views

Desmos saying there are too many variables [closed]

I wasn't sure if this is a Computational Science SE question or a Stack Overflow question but I think it's more of this one. I wanted to make a graph where I can rotate a hyperbola (not parabola or ...
user avatar
  • 103
1 vote
1 answer
147 views

How do I find the portion of a cell/voxel lying within a defined surface?

We have a 3-dimensional grid of voxels (or cells), with individual voxels being of volume $dx\,dy\,dz$ where $dx=dy=dz=1$. A cone-like surface is defined by some function, $z = f(x, y)$, which in ...
user avatar
-1 votes
1 answer
144 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.
user avatar
  • 215
0 votes
1 answer
59 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, ...
user avatar
  • 109
2 votes
2 answers
1k 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(...
user avatar
3 votes
2 answers
112 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 ...
user avatar
  • 151
3 votes
2 answers
126 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 ...
user avatar
  • 1,902
2 votes
1 answer
95 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 (...
user avatar

1
2 3 4 5 6