Questions tagged [computational-geometry]
The study of computer algorithms which admit geometric descriptions, and geometric problems arising in association with such algorithms. The two major classes of problems are (a) efficient design of algorithms and data classes using geometric concepts and (b) representation and modelling of curves and surfaces.
1,193
questions
1
vote
0
answers
17
views
Number of Centroidal Voronoi tessellations
I'm interesting in Voronoi tessellations. It is often claimed that there are, for example, 3 CVT for a square.
It is easy to check it numerically, but then we can only confirm that there are at least ...
- 762
0
votes
1
answer
44
views
Hull Representation of a PointCloud on a Mesh Surface
I got a manifold, watertight 3D triangle mesh. On a small subset of that mesh the surface is sparsely sampled, which results in a 3D pointcloud.
I now want to compute a boundary or concave hull ...
- 1
0
votes
1
answer
28
views
Maximize coverage of a polygon with a circle of specified radius
I have a set of various irregular polygons with between 3-5 sides. I need to fit a circular wafer of a specific radius inside each of these polygons, but I want to maximize the amount of usable area ...
- 11
0
votes
1
answer
79
views
Constructing operator for mesh fairing, are these 2 approaches equivalent?
There is a 2004 paper in computer graphics called "An Intuitive Framework for Real-Time Freeform Modeling" which explains how to make fairing operators to smooth out meshes. In particular ...
- 3,088
2
votes
2
answers
86
views
Is it possible to define a single parametric curve that equals three other related curves for specific inputs?
The Curves
I have worked out parametric equations for the curves of involute gear profiles using the seven gear parameters given in the "Background" section below. However, currently the ...
- 1,217
3
votes
1
answer
145
views
Enumerating the "discrete straight lines" in an $n \times n$ grid.
This question is related to this other question.
I would like to write an algorithm to enumerate all subsets of the $n^2$ squares of an $n \times n$ grid such that, for each subset, there exists a ...
- 2,761
5
votes
0
answers
116
views
Minimize enclosing perimeter subject to minimum distance between nodes
I have a collection of nodes $N_i$ and minimum distances $d_{i,j}$ between them like this (not all $d_{i,j}$ shown for visual clarity).
The task is to find a 2D graph (the (x,y) positions of each ...
- 137
3
votes
1
answer
40
views
Visual software of Riemannian metric on $S^2$
Consider the unit sphere in $\mathbb R^3$, let $\theta$ be polar angle, $\varphi$ be azimuthal angle. Then, the standard metric is
$$
g=
\begin{pmatrix}
1 & 0 \\
0 & \sin^2\theta
\end{pmatrix}...
- 5,783
30
votes
4
answers
945
views
Minimum number of straight lines to cover $n \times n$ grid?
I want to know the minimum number of lines needed to touch every square of an $n \times n$ grid. The only added rule is that the line has to pass inside the square, not on the edge/corner. I have ...
- 201
0
votes
1
answer
64
views
Computational geometry - BSP tree
I am doing some exercises from my textbook and I have stuck by this one. Any help would be great
Give an example of a set S of n non-intersecting line segments in the
plane for which a BSP tree of ...
- 25
0
votes
0
answers
24
views
Orthogonal Projection Area of a Zonogonal Cylinder
A zonogon is a convex polygon that is made up of pairs of parallel line segments that are congruent. A zonogonal cylinder is a cylinder with identical and identically aligned zonogons as the end caps. ...
- 141
0
votes
0
answers
17
views
Extremal problems for (non-convex) polygons on hexagonal lattices
I am interested in non-convex polygons and extremal properties thereof, specifically on hexagonal (honeycomb) lattices (or three valent and three colorable lattices in general).
In particular, I am ...
- 21
0
votes
1
answer
25
views
Package to enumerate all regular triangulations for point configuration
I am trying to enumerate the regular triangulation of some point configurations. The sage-math can enumerate all triangulations, but cannot check if each one is regular or not.
It seems TOPCOM can ...
- 137
1
vote
1
answer
115
views
Orthogonal Projection Area of a 3D Cuboid
This problem is asking the same as this problem, but is a cuboid instead of a cube and the independant variables are the roll, pitch, and yaw. I wrote some Mathematica code that finds the area ...
- 141
1
vote
2
answers
64
views
Finding closest edge to a point on a rectangle
In the image below I have a rectangle (with corners 1-4). I have a blue point. I'm trying to find which side is closest to this point. Finding one of the corners (that make up the side) seems easy. As ...
- 13
2
votes
2
answers
78
views
Maximization of average pairwise distance
May be this is some already some standard problem but i do not know.Consider $n$ variable points points $ P_1,P_2,...P_n$ in the
closed disc $x^2+y^2 \leq 1.$ Now define the average pairwise ...
- 1,592
2
votes
1
answer
115
views
Every polygon with the more than 3 vertices has a diagonal
This is an excerpt from the book
Discrete and Computational Geometry"
by Devadoss and O'Rourke.
Lemma 1.3: Every polygon with more than three
vertices has a diagonal.
"Proof: Let v be the ...
- 69
0
votes
0
answers
25
views
How to determine the reflex angles in a concave polygon in 3D?
For a concave polygon in 2D, it's easy to use the cross product to determine the reflex angles, which are greater than $180^{\circ}$, but I wonder if there is a simple way to do it in 3D.
- 6,117
-1
votes
1
answer
25
views
Count neighbors at radius $r_m$
I have a point cloud of $50,000$ points in a 3D space.
I want to count the number of neighbors each point $\{(x_1,y_1,z_1), (x_2,y_2,z_2), (x_3,y_3,z_3), ... ...,(x_N,y_N,z_N)\}$ has at radii $\{r_1, ...
- 1,573
0
votes
0
answers
35
views
Delaunay graph and hamiltonian paths
Does the Delaunay graph (dual of Voronoi) always contain a hamiltonian path (traceable)? I know the answer is negative for hamiltonian cycles since there are several examples such as the one gave by ...
1
vote
2
answers
89
views
Find the conditions which guarantee a polyhedron is bounded (i.e., a polytope)?
Note, a polyhedron is the intersection of finitely many half spaces in $\mathbb{R}^n$ and a polytope is a bounded polyhedron.
Preliminary: Consider a hyperplane $C_1x_1 + C_2x_2 + \dots + C_nx_n + D = ...
- 107
1
vote
0
answers
44
views
Find the constraints which guarantee that 6 planes in 3D space form a convex box containing the origin?
I ever asked a question to find the constraints which ensure 4 lines in 2D space form a convex quadrilateral; see link and it has been solved by @YNK author perfectly.
Now I hope to extend it and came ...
- 107
0
votes
0
answers
40
views
Girard's Formula for Arbitrary Spherical Polygons (concave, self-intersecting, etc.)
In every reference I've seen, the area of an $n$-sided spherical polygon is given by the sum of all interior angles, minus some amount of spherical excess, or
$$\text{Area}(\text{polygon}) = \sum_{i} ...
3
votes
0
answers
45
views
What's meant by a 'reversible Boolean formula' in this context?
I don't think I understand correctly what it means for a Boolean formula to be reversible. By my current understanding, if a Boolean formula is satisfiable, then there exists a setting of variables ...
- 41
0
votes
1
answer
82
views
How to detect if a tetrahedron has a flat-like shape
Creating tetrahedra
I have this OpenSCAD code that creates tetrahedra by getting its points:
...
- 195
2
votes
0
answers
20
views
Geometric interpretation of the definition of a net-tree
Motivation
I have been trying to digest the paper "Fast Construction of Nets in Low Dimensional Metrics, and Their Applications", which has relevance to many problems in computational ...
- 2,102
0
votes
0
answers
15
views
The connectivity of reflexive polytopes from just their vertices?
I'm working with the Kreuzer-Skarke database of 4-dimensional reflexive polyhedra. It lists almost half a billion polytopes, each represented by its vertex list and a few properties (Hodge numbers and ...
- 1
1
vote
0
answers
49
views
Pinhole camera model definitions
As I were implementing the pinhole camera model based on Tsai, I noticed that there were two conventions used. For opencv and others, the following is used:
$$
\begin{pmatrix}
u_{c} \\\ v_{c} \\\ h_{...
- 11
4
votes
0
answers
72
views
How can I find a point outside a spherical polygon?
Say we have a spherical polygon consisting of a series of vertices $v_1, v_2, \ldots, v_i$ on the unit sphere connected by great-circle arcs and are given a point $X$ on the unit sphere which is ...
- 141
0
votes
0
answers
27
views
Maximum number of cells in arrangement of $d$ polytopes?
An arrangement of polytopes (analogous to an arrangement of hyperplanes) $\mathcal{P}$ is just a set of polytopes in $\mathbb{R}^d$. Suppose $|\mathcal{P}| = n$.
Then a cell is a connected component ...
- 2,410
0
votes
1
answer
46
views
Visual Methods for Dividing a Closed Plane using n Lines for Animation with Manim
I am planning to use Manim to animate the process of dividing a closed plane into $\frac{n(n+1)}{2} + 1$ regions using $n$ lines. The formula is derived from this recurrence relation:
\begin{align}
...
- 145
1
vote
1
answer
55
views
Non-delaunay triangulation of a set of points and its convex hull boundary
I have a set of n random points on a 2D plane, and its convex hull boundary. Some points lie interior to the convex hull boundary. I want to triangulate this in a non-delaunay random fashion, such ...
- 63
0
votes
1
answer
53
views
Prove that the median level of the dual of a set of non-degenerate points is formed by the duals of all points in the set. [closed]
Given a non-degenerate set of points, if we take the dual of each point and look at the median level of this line arrangement, how can one prove that the median level includes the duals of all the ...
- 63
0
votes
1
answer
36
views
Second closest red-blue theorem
I want to prove/disprove that for a set $S = R \cup B$ of $n \geq 3$ colored (red and blue) points in general position (no 3 are collinear, no 4 are cocircular, and the distances between the $n \...
- 63
1
vote
0
answers
154
views
How to calculate the Arithmetic Zeta function?
I consider the equation $x^2+y^2+z^3=xyz+2$ over the integers. As a variety this only has a singularity in characteristic $2$. Now I am interested in calculating the arithmetic zeta function of this ...
- 53
1
vote
0
answers
16
views
Compute intersection with box in toroidal domain
Consider the box $[0, 1)^d$ with wrap around; for example, $1 + .05 = .05$ in each dimension.
Given a point $x\in[0,1)^d$ and a positive constant $\epsilon$ (between $0$ and $.5$), I want to obtain a ...
- 13.4k
1
vote
1
answer
43
views
CGAL: rotate Nef Polyhedron
CGAL gives an example of how to rotate a Nef_polyhedron 90 degrees around the x-axis (https://doc.cgal.org/latest/Nef_3/Nef_3_2transformation_8cpp-example.html). I am not exactly sure what the ...
- 31
3
votes
0
answers
43
views
Identifying the delaunay simplex the point resides in without computing all the possible simplices
My question is whether it is possible to identify the delaunay simplex the point $\mathbf{x}_{\textrm{query}}$ resides in without pre-calculating all the possible simplices by triangulation?
Can we ...
- 31
3
votes
0
answers
26
views
Algorithm choices for trapezoidal decomposition
Most textbooks and papers in the computational geometry area use randomized incremental algorithms for trapezoidal decomposition in default instead of other algorithms that are easier to understand ...
- 41
0
votes
2
answers
35
views
Sum of fractions in the form $\frac{1}{n}$ from $\frac{1}{2^n}$ to $\frac{1}{3*2^{(n-1)} - 1}$ less than $\frac{1}{2}$?
https://mathoverflow.net/a/278290/501460
I've been trying to figure out why this works, and why the tiles don't go past the middle, considering all the squares together have an infinite side length.
...
- 3
0
votes
0
answers
27
views
Aligning more than two sets of 3D points
We have a good solution for the problem of aligning two sets of 3D points with known correspondences, assuming each set has more than three points. It consists of centering the points around the ...
- 143
0
votes
0
answers
23
views
Does a Binary Space Partition of a 3D model denote which leaves are inside or outside the volume of the model?
If I were to start with a 3D polygonal model of a building and build a Binary Space Partition (BSP) from its faces, would the tree tell me which points in space are inside or outside the model? In ...
1
vote
2
answers
64
views
Marching cubes generates surface triangles. How to adapt it to generate tetrahedra throughout the volume of a 3D model?
Background
There is a source code that generates surface triangles. The isosurface is generated for the iso-value of 0. The source code uses a table for ...
- 195
0
votes
1
answer
29
views
Generate cycle graph from vertices
I have K vertices and I need to connect them to form a graph. I am currently generating a complete undirected graph that looks like these:
However, I only need the ...
- 113
0
votes
1
answer
69
views
Compute the separating line given by the linear SVM solution in the form $𝑥_2=𝑘⋅𝑥_1+𝑑$ :
Consider the following binary classification problem in ℝ2:
The points ($𝑥_1, 𝑥_2$)
labeled with +1 are: {(1,2),(0,2),(0,1),(1,1)}
The points ($𝑥_1, 𝑥_2$)
labeled with -1 are: {(5,3),(8,3),(8,6),(...
- 1,114
0
votes
2
answers
34
views
Compute an oriented angle in an abstract plane.
I am coding something a bit esoteric.
I have a stream of points which are guaranteed to be planar, however the points are embedded in some high dimensional space (e.g. 3D).
I need to define a notion ...
- 3,088
1
vote
1
answer
63
views
Prove: For any pair of positive integers $(v,f)$ satisfying $f≤2v−4$ and $v ≤ 2f − 4$ there exists a polyhedron with $v$ vertices and $f$ faces
Finding examples is one thing, but I don't get how to prove it broadly, though I'm fairly certain it should be true.
- 11
2
votes
1
answer
119
views
How to check if two cylinders are overlapping [closed]
I have two cylinders defined by their end points with a fixed radius $r$ of 0.01.
Say
$$
Cyl_1 = \left\{\begin{matrix}
p_{\rm start} = \left\{x_1, y_1, z_1 \right\} \\
p_{\rm end} = \left\{x_2, y_2, ...
- 23
0
votes
0
answers
42
views
How can I check if a Point Intersect A Moving Sphere?
My problem is that I can't find all the points that intersect the sphere during its linear motion. What I did was to check starting with the starting point, from point to point until the final point, ...
- 9
0
votes
0
answers
20
views
Common outer tangents of two ellipses
This question is a follow up to @Futurologist's answer to this question. I've found that @Futurologist's algorithm works extremely well for most cases. However, when the two ellipses approach being ...
- 1