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]
1221 questions
1
vote
1 answer
Algorithm to consolidate multiple smaller rectangular areas into fewer larger rectangular areas
Consider the 3 rectangles stored as 2 opposing corners.
$ r_1 = (0,0,2,1)$ , $ r_2 = (1,1,2,2)$ , $ r_3 = (2,0,3,1)$
The area covered by these 3 rectangles can be represented using 2 rectangles
$ r_4 = (0,0,3,1)$, $ r_5 = (1,1,2,2) $
Is there…
1
vote
1 answer
Algorithm for computing the plane that passes through three arbitrary points
I'm writing a computer graphics library, and I'd like to compute the plane that passes through three arbitrary points, $p$, $q$ and $r$. I'm defining the plane in the form of $Ax + By + Cz + D = 0$.
My algebra is rather rusty, but I suspect this is…
brendanzab
- 153
- 6
1
vote
1 answer
Determine a 4d vector $\langle N, D\rangle$ corresponding to the a plane with three points
I'm having trouble understanding why i'm getting a different result than the book for the given problem.
Determine a 4d vector $\langle N, D\rangle$ corresponding to the plane that passes through the three points $A = \langle 1, 2, 0 \rangle$, B = …
TigerChan
- 13
1
vote
1 answer
Volume of a simplex by using LP or MIP
Is there any way to calculate the volume of a simplex by using LP or MIP when we have its extreme points? Is there any paper that gives me some clues?
CH.S
- 13
1
vote
1 answer
Boundary of Delaunay Triangulation is the convex hull of sites
A Delaunay triangulation for a set $P$ of points in a plane is a triangulation $DT(P)$ such that no point in $P$ is inside the circumcircle of any triangle in $DT(P)$.
A Voronoi diagram is a partitioning of a plane into regions based on distance to…
Arman Malekzadeh
- 4,108
1
vote
2 answers
superellipsoid: problem in understanding parametric formula
i've found this interesting page: superellipse and superellipsoid
and i used the formula for one of my computer graphics applications.
i used (the most usefull for computer graphics) the parametric formula:
but for correclty draw the superellipsod…
nkint
- 1,823
1
vote
1 answer
Hausdorff Distance Between Convex Polygons
I'm interested in calculating the Hausdorff Distance between 2 polygons (specifically quadrilaterals which are almost rectangles) defined by their vertices. They may overlap.
Recall $d_H(A,B) = \max(d(A,B), d(B,A))$ where $d$ is the Hausdorff…
Alex Chamberlain
- 111
1
vote
1 answer
How many techniques are there to test collinearity of $n$ points?
How many techniques are there to test coliniariry of n points?
For example, suppose we have 4 points A, B , C, D. How many ways can it be tested that they are collinear?
This answer lists 03 techniques:…
user6704
1
vote
1 answer
Polygon: Internal Rays
Suppose I have an arbitrary non-self-intersecting polygon.
I want to generate a list of points which lie on the edges of this polygon according to the following procedure:
I iterate over each edge of the polygon and extend a ray from each vertex on…
Steve
- 177
1
vote
1 answer
Testing polygon monotonicity
I am looking for an idea of an algorithm for the following problem:
Give an efficient algorithm to determine whether a polygon P with n vertices is monotone with respect to some line, not necessarily a horizontal or vertical one.
Monotonicity is…
com
- 5,612
1
vote
1 answer
Using Chazelle's simplicity test to verify simple polygons intersection
Is there a way to verify whether a non-empty intersection exists between two simple polygons (not necessarily convex) using the Chazelle's simplicity test ?
user4444
- 51
1
vote
1 answer
Prove that there is a set of $n$ points such that a Voronoi cell contains $n-1$ vertices.
We need to prove the following claim:
There exists a set of $n$ points such that a Voronoi cell of one of the points contains $n-1$ vertices.
I think in the following case the Voronoi cell for point $C$ contains $n-1$ vertices, but I'm unable to…
rizwanhudda
- 113
1
vote
0 answers
ellipsoid and paraboloid relation
My task was to programme a paraboloid and an ellipsoid. I implemented paraboloid as a set of points that's distance from the focal point and the distance from the plane is the same. After running the compiler, I got something that looked like an…
Bence Szabó
- 11
0
votes
1 answer
Geometry (Convex Polygons)
Let P be a set of points in the plane. Let P1 be the convex polygon whose vertices are points from P and that contains all points in P. Prove that this polygon P1 is uniquely defined, and that it is the intersection of all convex sets containg P
Cory
- 91
0
votes
1 answer
Fast 2D line triangle intersection test
In a 2D plane, I have a line segment ($P_0$ and $P_1$) and a triangle, defined by three points ($t_0$, $t_1$ and $t_2$).
My goal is to test, as efficiently as possible ( in terms of computational time), whether the line touches, or cuts through, or…
Graviton
- 2,292