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

200 questions
Filter by
Sorted by
Tagged with
1answer
253 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, ...
2answers
1k 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 ...
1answer
71 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 ...
1answer
254 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 ...
5answers
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 ...
1answer
181 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 ...
1answer
54 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 ...
2answers
308 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}$ ...
1answer
133 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 ...
1answer
156 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 ...
2answers
140 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 ...
2answers
158 views

1answer
70 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 ...
1answer
1k 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 ...
0answers
26 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 ...
2answers
276 views

1answer
48 views

### Find a consistent cyclic orientation on a conic section

I have a conic section in the real projective plane. This is represented by its real symmetric 3×3 matrix. I verify that the conic section is real and non-degenerate by computing the eigenvalues of ...
1answer
1k views

### Fitting a rectangle to a point set

I have an ordered list of (2d-)points that are forming a (not axis aligned) rectangle and I'd like to recover that rectangle. Approximations like a minimal enclosing rectangle can't be used so that I'...