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.
Questions tagged [computational-geometry]
1170 questions
229
votes
23 answers
How to check if a point is inside a rectangle?
There is a point $(x,y)$, and a rectangle $a(x_1,y_1),b(x_2,y_2),c(x_3,y_3),d(x_4,y_4)$, how can one check if the point inside the rectangle?
Freewind
- 2,515
- 3
- 16
- 12
68
votes
6 answers
How to generate random points on a sphere?
How do I generate $1000$ points $\left(x, y, z\right)$ and make sure they land on a sphere whose center is
$\left(0, 0, 0\right)$ and its diameter is $20$ ?.
Simply, how do I manipulate a point's coordinates so that the point lies on the sphere's…
Filip
- 689
- 1
- 6
- 5
29
votes
6 answers
Is it possible to solve any Euclidean geometry problem using a computer?
By "problem", I mean a high-school type geometry problem.
If no, is there other set of axioms that allows that?
If yes, are there any software that does that?
I did a search, but was not able to find a single program that allows that. It is strange…
Artium
- 940
- 1
- 9
- 18
19
votes
1 answer
Geometry of nose in and nose out parking in parking lots
I would like some computational evidence in favor of my observation that one can park a car in tighter (parking lot) spaces by backing in rather than nose in. I have been doing this successfully for some 15 years, but see few others trying this.…
Will Jagy
- 135,540
- 7
- 139
- 258
19
votes
3 answers
How to union many polygons efficiently
I've asked this question at SO, but only answer I got is a non-answer as far as I can tell, so I would like to try my luck here.
Basically, I'm looking for a better-than-naive algorithm for the constructions of polygons out of union of many…
Graviton
- 2,272
- 4
- 35
- 53
16
votes
3 answers
Check if a point is inside a rectangular shaped area (3D)?
I am having a hard time figuring out if a 3D point lies in a cuboid (like the one in the picture below). I found a lot of examples to check if a point lies inside a rectangle in a 2D space for example this on but none for 3D space.
I have a cuboid…
Faas
- 173
- 1
- 1
- 6
13
votes
5 answers
Every polygon has an interior diagonal
How does one prove that in every polygon (with at least 4 sides, not necessarily convex), that it is possible to draw a segment from one vertex to another that lies entirely inside the polygon.
In particular, I'm having trouble rigorously defining…
Potato
- 39,026
- 17
- 128
- 263
13
votes
6 answers
"Surface Area" of $k$ simplex in $\mathbb{R}^{k}$?
Consider the $k+1$ vertices $(x_1,\ldots,x_{k+1})$ with $x_i\in\mathbb{R}^k,i=1,\ldots,k+1$. I know that the "volume" of the $k$-dimensional simplex formed by these vertices is proportional to
$$\left|\det\left( \begin{array}{ccc}
1 & \ldots & 1…
user1963
- 535
- 3
- 17
13
votes
1 answer
Automorphism group of a lattice's Voronoi cell
Let $\Lambda$ denote a lattice of $\mathbb{R}^n$, i.e.
$$\Lambda = \left\{\sum_{k=1}^n n_i\mathbf{a}_i\ \bigg|\ n_i\in\mathbb{Z}\right\},$$
for $n$ linearly independent vectors $\{\mathbf{a}_i\}$ in $\mathbb{R}^n$. The Voronoi cell of the lattice…
EuYu
- 40,571
- 9
- 88
- 131
12
votes
3 answers
is there an efficient algorithm for comparing collections of points?
Let's say you have two sets of M points $p_1...p_M$, and $q_1...q_M$, which reside in $\mathbb{R}^N$. Is there an efficient (e.g. polynomial in M and N) algorithm to determine if the point-sets are the same up to some orthogonal transformation?…
NickC
- 121
- 4
12
votes
4 answers
Find whether two triangles intersect or not in 3D
Given 2 set of points
((x1,y1,z1),(x2,y2,z2),(x3,y3,z3)) and
((p1,q1,r1),(p2,q2,r2),(p3,q3,r3)) each forming a triangle in 3D space.
How will you find out whether these triangles intersect or not?
One obvious solution to this problem is to find the…
Atishay
- 221
- 2
- 3
12
votes
2 answers
Point closest to a set four of lines in 3D
Given four lines in $3D$ (represented as a couple of points), I want to find the point in space which minimizes the sum of distances between this point and every line.
I'm trying to find a way to formulate this as a problem of Least Square, but I'm…
Prateek
- 121
- 1
- 1
- 3
12
votes
3 answers
Algorithm to compute the area of a convex set in 2 dimensions
I am interested in an algorithm to compute the area of a compact, convex body $K \subset \mathbb{R}^2$, up to an error $\epsilon > 0$. I am curious about the optimal running time of such an algorithm, but I would be happy with a simple algorithm…
J Richey
- 631
- 9
- 23
12
votes
5 answers
Find the area of overlap of two triangles
Suppose we are given two triangles $ABC$ and $DEF$. We can assume nothing about them other than that they are in the same plane. The triangles may or may not overlap. I want to algorithmically determine the area (possibly $0$) of their overlap; call…
AakashM
- 567
- 1
- 7
- 19
11
votes
3 answers
Unique characterization of convex polygons
Question
I am looking for a unique characterization of a convex polygon with $n$ vertices, relative to a feature point $p$ in the interior of the polygon. This characterization would be a vector of numbers. Suppose a polygon is described by its…
Victor Liu
- 3,661
- 16
- 25