# 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.

206 questions
Filter by
Sorted by
Tagged with
27 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? ...
60 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 ...
36 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 ...
48 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 ...
97 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 ...
51 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 ...
36 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 ...
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 ...
53 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 ...
35 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 ...
68 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: ...
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 ...
70 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 ...
50 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 ...
46 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 ...
123 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 ...
120 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 ...
69 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 ...
69 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 ...
202 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}...
104 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 ...
113 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$ ...
113 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 ...
44 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 ...
248 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 ...
48 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 ...
47 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....
151 views

508 views

### 3D contour mesh computation

I have the value of a function in three dimensions, $f(x, y, z)$, which varies smoothly. I would like to compute a 3D mesh where $f(x, y, z)$ has a particular value. Are there algorithms to do this? ...
208 views

### Integrating/Implementing NURBS-related calculations

Recently, I started to develop some codes that use NURBS (general things I intend to use/already using: spline generation, interpolation, grids, isolines, closest-point find, and many others), both ...
64 views

### Polygon approximation with a circle

There is an article describing how to detect a pupil from an eye photo. A.-H. Javadi, Z. Hakimi, M. Barati, V. Walsh, and L. Tcheang, "SET: a pupil detection method using sinusoidal approximation," ...
86 views

### Fast Algorithms for the Simplicial Decomposition of a Convex Polytope in N-Dimensions

I'm in the process of constructing an algorithm which computes the Voronoi diagram of a set of points, but I now need a method to decompose each Voronoi cell into simplices. The information we have is:...
56 views

### Efficient initial identification of solid or liquid domains for a block structured Cartesian grid generation system

INTRO Within the last 5 days I was able to generate a block structured Cartesian grid generation system with a combination of Fortran,C++ and Python. I am running intersection tests of the ...
112 views

### Which free library should I use to perform cutting/clipping operation?

I have a set of points which forms a closed loop, and I want to perform cutting/clipping a 3D model using this loop. I have used VTK but in some cases, it has a "Cannot follow edges" problem. Is ...
80 views

### Gmsh exporting wrong mesh DATA [closed]

so hopefully I'll be using gmsh to make meshes out of 2-D cross sections with o thickness. I tried to make a structured mesh with quad elements of a rectangular ...
287 views

### Expanding Winding Number algorithm to arcs

I have a problem that I have been attempting to solve for a few days now. I was wondering if I would be able to get some assistance from the community. In order to detect if a point is in a polygon, ...
197 views

### Compute mesh of the projection of a 3D surface triangulation

Given a triangulated surface in $\Bbb{R}^3$ we can simply project it on a plane. This will result in a family of triangles which do not form a mesh of the projection for the following reasons: each ...
2k views

### Efficiently finding all (x,y,z) points within certain distance of point P

I am using Python, and I have a Pandas dataframe with hundreds of thousands, if not millions, of $(x,y,z)$ coordinates. I am looking to find an efficient method to index the original dataframe so that ...
55 views

### Detect all “visible” points on a triangulated surface

I have a triangulated surface that I want to work with. In order to optimize certain quantities related to this surface I want to find all points which are accessible from a given direction. To be ...
110 views

### Algorithm to construct all distances of a system described by $3N-6$ distances

A non-linear molecule has $3N-6$ degrees of freedom ($N$ is the number of atoms; ignoring translation and rotation). Therefore, a set of $3N-6$ distances and/or angles is enough, to describe the whole ...