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
0
votes
0answers
24 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 ...
0
votes
0answers
23 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 ...
1
vote
0answers
66 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 ...
3
votes
3answers
99 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 ...
2
votes
3answers
167 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, ...
4
votes
4answers
153 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 "...
2
votes
1answer
60 views

Project to nearest point on convex polyhedron

I have a point $y \in \mathbb{R}^d$ and a convex polyhedron $\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 \...
0
votes
0answers
44 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 ...
6
votes
0answers
252 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: $$\...
0
votes
2answers
73 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 ...
0
votes
1answer
91 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(...
4
votes
0answers
52 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 ...
0
votes
1answer
177 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 ...
1
vote
1answer
60 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 ...
-1
votes
1answer
53 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.
0
votes
1answer
41 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, ...
2
votes
2answers
334 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(...
1
vote
0answers
26 views

Simplification of vertices and dihedral angle relations of a polygonal chain

I am trying to understand the generation of Cartesian coordinates of polygonal system or poly line with fixed bond angles and fixed link lengths. I assumed the bond angle to be the same and link ...
3
votes
2answers
84 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 ...
2
votes
2answers
96 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 ...
2
votes
1answer
78 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 (...
0
votes
1answer
37 views

Produce vertex displacements from volumetric shrinkage data on unstructured meshes

I was wondering what would be an efficient way to produce compatible displacements for mesh nodes/vertices if the computed data is volume shrinkage of each element/cell in the unstructured mesh? ...
1
vote
0answers
69 views

How to approach geographic data interpolation by distance?

let's say I have a set of geographic locations (lat, lng) resulting from a query. Those locations have some kind of internal ranking, my set is sorted by this number in a descending order. Now I'm ...
0
votes
1answer
41 views

How to find the nearest point inside a list in a given direction

Being $\bar{\mathbf{x}} \in \mathbb{R}^3$ a point and $S =\{\mathbf{x}\}_{i=1}^N \in \mathbb{R}^3$ a sample of N points. I am looking for a simple algorithm to determine the nearest point in $S$ in ...
5
votes
1answer
96 views

Maximum and Minimum distance from query point within bounding box

I'm reading an article regarding approximating sums using KD-trees (similar to FMM). As part of the effort I'm trying to make sense of this article , which is cited. I'm having trouble understanding ...
3
votes
2answers
109 views

Find shortest path around a cylinder represented by 3d triangular mesh

Suppose I have a 3d triangular mesh with the topology of a finite cylinder. Let $C$ be a vertex on that mesh. How can I find the shortest path from $C$ to itself that goes around the cylinder? By ...
1
vote
0answers
66 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
0answers
48 views

Dividing Point Cloud into voxels

I am reading a paper on implementing convolution neural network for a 3D point cloud. In this paper, they are dividing the point cloud into voxels. Is there any easy way to do it using point cloud ...
2
votes
0answers
30 views

Check if two points are symmetrics/asymmetrics

I am working on an Android app which lets a group of children draw whatever they want in a specific area. I need to check if the lines and figure that they draw are symmetric. The problem is that ...
2
votes
0answers
63 views

Efficient algorithm to determine the intersection volume of simple convex polyhedra

TLDR: Is there an efficient algorithm to compute the intersection of polyhedra with 8 or fewer vertices? I have two sets of FEM meshes for one geometry (one exhibiting a skin effect). I have to ...
2
votes
0answers
38 views

Algorithm to join hexahedra and obtain outline volume

I would like to join several hexahedra and obtain an outline volume. First, I started with 2D implementation. In 2D, there are non-intersecting quadrangles which always touch each other as shown in ...
0
votes
0answers
81 views

How to read data from simply formatted text file (c++)?

Mesh information like points, faces and cells is to be stored into separate files: e.g. for points file: # points data: x y z N_Points 100 x1 y1 z1 x2 y2 z2 ... cell file: # cells data: ...
36
votes
18answers
9k 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
1answer
111 views

How can one prove the duality of Voronoi and Delaunay?

Hoping I'm not misunderstanding the concept here, but it is my understanding that Voronoi Diagrams and Delaunay Tesselations are 'dual' to one another, owing to the fact that each' solution makes ...
3
votes
0answers
51 views

Calculating depth mask from different lighting

I have a object which is static, the camera is static and light source is moving. How can the depth mask be calculated ? Concept is to use - calculate height from shadow length Lets imagine a have ...
2
votes
0answers
47 views

Cover a polygon with least amount of parallelograms [closed]

I am solving the task that is as follows: Input: a polygon. Can be any kind of polygon without self intersections. Can be a non-convex and with holes inside. Goal: to cover it with 2 (at least) or ...
7
votes
1answer
260 views

How to calculate the geodesic curvature of a discrete 3D curve?

I have coordinates of a set of points that form a closed loop that lies in a 3D surface. I know the equation of the surface and I can calculate it's surface normal at any point. I found that for a ...
0
votes
2answers
135 views

Ordering points from X Y coordinates

I have series of points extracted from a regular grid, with their X/Y coordinates. A previous algorithm (that I cannot modified!) output a list of these coordinates, but the ordering of these point is ...
2
votes
2answers
79 views

projective reconstruction from orthogonal views

This is a problem from projective geometry. Suppose I have a vector $z \in R^k$ of unit length $\| z \| =1$ inside a $k$-dimensional hypercube. I don't know its value but do know its projection upto ...
3
votes
1answer
72 views

Smoothness regularisation of a 2D field on a triangular mesh?

I'm working on an inverse problem where the solution is the values of a 2D scalar field at the vertices of a 2D triangular mesh, such that the field can be defined continuously inside the mesh via ...
2
votes
1answer
470 views

A robust algorithm to sort a non-convex polygon vertices

Let v_{0},...,v_{N-1} be N points in a Cartesian xy plane defining the vertices of closed polygon (i.e. v_{N} = v_{0}). Let P_{0}...
1
vote
1answer
142 views

Node renumbering in a 2D mesh

I have a 2D domain which is discretized using Q4 elements. I have the nodal positions and the element connectivity matrix. I would now like to renumber the nodes in such a way that all the interior ...
1
vote
1answer
275 views

How to generate a face list from vertices?

I have a little background in writing toy finite volume CFD codes. In 2D Cartesian scenarios, I typically take $x_{\min}$, $x_{\max}$, $y_{\min}$, $y_{\max}$, and the number of points in $x$ and $y$ ...
2
votes
1answer
164 views

Efficient root finding algorithm for monotonic function

This is my first time asking a question here, so I may not be asking this in the right place. I am trying to find the roots of a monotonic function with as few function evaluations as possible. I ...
3
votes
0answers
48 views

Minimum axis aliged bounding box of convex polytope

I need to compute a $n-$dimensional integral with $n<10$ on a convex polytope. Since most numerical integration libraries (e.g. Cuba) expect the function to be integrated defined inside an axis ...
3
votes
1answer
376 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 ...
3
votes
0answers
51 views

Approximate the largest simplex in N-dimensional Delaunay triangulation

I am working on determining the spatial information of a set of $M$ points in $N$-dimensional space. It is well-known that the construction of Delaunay triangulation is expensive in high dimensional ...
1
vote
0answers
50 views

Uniformly sample a point per polytope

I want to uniformly sample a point within each of $10^5$ convex polytopes in each iteration of a solver. The polytopes in one iteration are completely different from the polytopes in another iteration....
2
votes
0answers
235 views

How to numerically optimize affine transformations?

I need to optimize affine transformations for of a set of triangles using energy function based on the connectivity. The energy of an edge $e_j$ between triangles $T_a, T_b$ is given by $$ E_j = \...
0
votes
1answer
106 views

Compute outward normal and surface area for 8 noded brick element in FEA

I have a cube which is divided into 8 small cubes by bisecting each edge, I am trying to find out the surface area of each of the faces and the corresponding outward normals for them. This operation ...

1
2 3 4 5