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

219 questions
Filter by
Sorted by
Tagged with
200 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$ ...
123 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 ...
45 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 ...
50 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 ...
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....
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 ...
195 views

533 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? ...
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 ...
235 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 ...
240 views

### How do I find the smallest set of elements that covers a given shape?

Suppose I have a mesh consisting of a set $M$ of conformal elements that fill the region $R=[0,1]\times[0,1]$. Suppose that I also have a 2D shape $S\subset R$ whose boundary $\partial S$ is ...
71 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," ...
804 views

### Some good reading on polygon algorithms

What are some good resources (books, articles, sites) about polygon intersection and union algorithms?
3k views

### Selecting most scattered points from a set of points

Is there any (efficient) algorithm to select subset of $M$ points from a set of $N$ points ($M < N$) such that they "cover" most area (over all possible subsets of size $M$)? I assume the points ...
93 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:...
57 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 ...
349 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, ...
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 ...
93 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 ...
265 views

### Does some form of documentation of GMSH exist?

I am looking to implement GMSh into a simualtor that I am going to create. I am looking to integrate the geo, mesh, and post processor modules. However, looking online, it appears the documentation ...
16k views

### Fastest Delaunay triangulation libraries for sets of 3D points

Which is the fastest library for performing delaunay triangulation of sets with millions if 3D points? Are there also GPU versions available? From the other side, having the voronoi tessellation of ...
227 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 ...
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 ...
322 views

### Compute spatial second derivatives in Isogeometric analysis

Motivation: In isogeometric analysis, state variables(e.g. displacement) are defined in the parametric domain, which can be mapped to the physical domain by $\boldsymbol{\xi}\mapsto \boldsymbol{x}$ ...
157 views

### Delaunay triangulation for datasets with four or more co-circular points

I am working on a library that requires subdivision of polygons into triangles. The polygons are divided into triangles by (more or less) random points that are inside them. In general, the approach ...
193 views

### Linear Least-Squares Point-to-Plane ICP degenerative case

I'm trying to implement Linear Least-Squares Optimization for Point-to-Plane ICP Surface Registration Paper describes linear approximation for point to plane distance for rigid ICP. This approach is ...
213 views

### Find connected circles

I have a problem as follows: We have a set of circles (we know the radius r and the center point c in Rd of each circle) We ...
173 views

71 views

### Distirbution of Points along a Line

I am facing the following problem: Given is a line of length $L$ which I want to split into $N$ segments. The lengths of the first $(s_1)$ and last segment $(s_N)$ are given. You can assume that the ...
2k views

### Translate a 3D point along a heading

I need to translate a point (P1) in 3D a certain amount, call it stepSize, along a vector described by a heading composed of ...
30 views

### Use custom defined metric(not matrix) in Javaplex

I'm about to get started trying to use Javaplex for the first time for some application in topological data analysis (TDA) and I want to use a custom defined metric. From looking over the documents, I ...
Let curve $C_1$ be defined parametrically \begin{aligned} &x(t)=0.5\cos(t)-0.3\cos(3t),\\ &y(t)=1.2+0.6\sin(t)-0.07\sin(3t)+0.2\sin(7t) \end{aligned} How do I find if an arbitrary point \$...