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

233 questions
Filter by
Sorted by
Tagged with
31 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:...
26 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 ...
69 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: ...
38 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 ...
78 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 ...
75 views

58 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 ...
93 views

115 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 ...
516 views

121 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 ...
70 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 ...
307 views

### Shape measure for C-shaped objects

There are many well defined measures for many basic geometrical objects such as rectangularity (area coverage of minimum bounding rectangle), triangularity (area coverage of minimum enclosing triangle)...
2k views

### Volume of 3D convex hull of small point sets all on the hull

I have a question that is similar to this one asked before except in 3D, and I only need the volume, not the actual shape of the hull. More precisely, I'm given a small set of points (say, 10-15) in ...
57 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 ...
64 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 ...