Using computers to solve geometric problems. Questions with this tag should typically have at least one other tag indicating what sort of geometry is involved, such as ag.algebraic-geometry or mg.metric-geometry.
Questions tagged [computational-geometry]
488 questions
8
votes
1 answer
Subtract Rectangle from Polygon
I'm looking for an algorithm that will subtract a rectangle from a simple, concave polygon and return a remainder of polygons. If the rectangle encloses the polygon, the remainder is null. In most cases, it looks like at least one edge will be…
Josh C.
- 325
7
votes
3 answers
Algorithm to compute the Voronoi diagram of points, line segments and triangles in $\mathbb{R}^3$
Is there a known algorithm to compute the (generalized) Voronoi diagram of a set of points, line segments and triangles in $\mathbb{R}^3$? If yes, are there any available implementations?
I know that there are two methods with available code for…
5
votes
2 answers
Checking a Guarding for the Art Gallery Problem
In the Art Gallery Problem, we have given
a polygon $P$ on $n$ vertices and a number $k$ and we
want to know if there exists $k$ guards
such that every point inside the polygon
is seen by at least one of the guards.
We say a point $p$ sees a…
Till
- 469
5
votes
1 answer
Given a polygon with holes, find a maximum distance pair in two subsets
I am curious about the following problem:
Given a polygon with holes and two convex subsets, $S$ and $T$, find points $s \in S, t \in T$ such that the shortest path between the two points has maximal length w.r.t. all point pairs in $S$ and…
Oliver
- 53
4
votes
2 answers
Area of a Convex Polygon (Described via Half-Planes)
The intersection of a collection of half-planes describes a convex polygon, whose vertices can be constructed in $O(n \log n)$ time using a divide-and-conquer approach (e.g., intersect each half-plane with a bounding box and recursively merge the…
TerronaBell
- 3,049
4
votes
1 answer
Volume of a finite union of overlapping balls?
Suppose I have finite list of $n$ 3-dimensional balls, specifying their positions and radii. The balls can have non-empty intersections.
Is there an algorithm to compute the volume of the region resulting from the union of all $n$ balls? How hard is…
valle
- 864
- 4
- 15
3
votes
1 answer
Detecting whether directed cycle is clockwise or counterclockwise
Given a directed cycle in the plane I need to walk it and detect whether it is clockwise or counterclockwise.
My first idea is to gather the sum of the turn angles, where a "left" turn is a negative angle, and a "right" turn is a positive angle. If…
Andy Storck
- 33
3
votes
1 answer
Computing intersections of unit disks
Given $n \geq 2$ points in the plane, how can one efficiently (or even inefficiently!) compute the number of corner-points belonging to the boundary of the intersection of the unit disks centered on those points? (This number is 0 when the…
James Propp
- 19,363
3
votes
1 answer
On using a 3D convex hull to compute a 2D Voronoi diagram
I am working in a computing environment that has the facility to compute general nD convex hulls and not much else in the way of computational geometry. The routine, given a set of points, gives the vertices of the convex hull and edge connectivity…
3
votes
1 answer
split polygon into minimum amount of rectangles and triangles
Hi
is there an algorithm which cuts a polygon into a minimum amount of preferably rectangles and where not possible (e.g. edges) into triangles?
3
votes
1 answer
Find longest segment through centroid of 2D convex polygon?
Given a 2D convex polygon P and its centroid C, how do I find the longest line segment passing through C, where the endpoints of the segment lie on the boundary of P?
Intuitively I imagine there are only a small number of possibilities, so I could…
Ruchira
- 31
2
votes
0 answers
To find the longest circular arc that can lie inside a given convex polygon
Question: Given a convex polygonal region P, to find the longest connected subset of a circle that can lie entirely in P.
For some P, the optimal subset will be a full circle; otherwise, a single arc from a circle.
An O(n) algorithm where n is the…
Nandakumar R
- 5,473
2
votes
0 answers
Biconvex Lens - an 'oriented' convex container for planar point sets
We continue On some optimal containers of a set of points on the 2D plane.
Let us define a biconvex lens as the intersection of two circular disks - not necessarily of the same radii. Such a figure has an 'oriented' nature - the special orientation…
Nandakumar R
- 5,473
2
votes
2 answers
Projection of a point to a convex hull in d dimensions
Hi,
I've got n points in d dimensions (typically n is around 30k-60k and d is 5 or 6). I'm using qhull to calculate the Delaunay triangulation and the convex hull of the set of points.
You can assume each point was drawn from the normal…
user27592
- 71
1
vote
0 answers
Dissection of polygons that preserve boundaries
Ref:
Inside-out polygonal dissections
Further queries on inside-out polygonal dissections
Question: Consider any two polygons P1 and P2 with equal area and equal perimeter. Is it always possible to dissect P1 to P2 in such a way that the every…
Nandakumar R
- 5,473