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
0 answers
Traveling Salesperson tour monotonicity
Prove that the travelling salesperson tour TSP of a set S of points
is monotone, that is, if S ⊆ S′, then the length of
TSP(S) is less than or equal to the length of TSP(S′).
user154705
- 11
1
vote
1 answer
Find equation of line without using division
I need an algorithm to find equation of a line without using division.
Given a line by two points on it, with coordinates: $(x_1, y_1),\ (x_2, y_2)$.
We can simply get the line equation by the formula:
$$y=y_1+(y_2−y_1)((x−x_1) /…
Heghine
- 265
1
vote
1 answer
Intersection of two sectors
Is there algorithm that decide if two sectors intersect?
I can transform the sector into polygons and use standard algorithms, but it has some cons.
Any other ideas?
Iko
- 11
1
vote
0 answers
largest polygon from segments
There is a set of segments.
and I want to calculate the area of the largest polygon which can be build using these segments.
I try to search it, but I can't find anything.
thanks
Babak
- 63
1
vote
1 answer
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 parameters that are being passed in the rotx90 variable…
Arjon Arts
- 31
1
vote
0 answers
Largest axis parallel cuboid in boolean array
I have a three dimensional bit array A of dimension N x N x N. The question is to find a maximum volume cuboid in A, i.e. indices i1, i2, i3, j1, j2, j3, such that A(k1, k2, k3) = 1 for all i <= k <= j and volume = prod(j-i+1) is maximum.
The…
1
vote
0 answers
Where to learn more about "closing off spaces"
Closing off spaces isn't even the right term and that's part of the problem. If a pair of scissors was cutting a path in a straight line from xy coordinate to xy coordinate how could i computationally find out when a closed path had been formed and…
Shane Springer
- 21
- 1
1
vote
1 answer
The lifting map and a corresponding plane
Given a point $p = (x,y) \in \mathbb{R}^2$, define its lifting $l(p)$ as the point $l(p) = (x,y, x^2+y^2) \in \mathbb{R}^3$. Then as per the image below, I wish to show that the lifted circle $l(C)$ is contained in a unique plane $h_C \subset…
IntegrateThis
- 3,778
1
vote
2 answers
Efficient data-structure for half-plane queries (2D)
Given a set of 2D points P with no three points that are colinear, no two points have the same x-coordinate, and no two points have the same y-coordinate. Is there a data-structure with O(log n) query time that I can use to test, given a half-plane…
user1760791
- 113
- 3
1
vote
1 answer
Choose irregular polygons from a list of irregular polgyons, to cover a quadrilateral
I have a large set of given irregular convex polygons (with between 3 and 6 sides). I need to write code to chose n of these polygons such that when combined they completely cover a given quadrilateral. The polygons in the given list overlap enough…
foobarbecue
- 713
1
vote
1 answer
Predicting the size of epsilon-net in SU(2)
I'm writing an algorithm that takes as input a finite set of matrices in SU(2) and consequently tries to generate an '$\epsilon$-net' by computing all possible matrix products (up to a given depth). If, in this process, a matrix is encountered that…
JorenB
- 549
1
vote
0 answers
Finding the largest inscribed axis aligned rectangle in a convex polygon
I need to compute the largest inscribed axis aligned rectangle in a convex polygon so I've been following the algorithms laid out in this paper. Using the prune and search method I can narrow the polygon down to the relevant vertices and edges for…
Grahalt
- 11
1
vote
0 answers
intersection of two closed plane polygonal curves
I am developing a program where I need to find the intersection of two closed plane curves.
The curves are exclusively composed of edges (such as triangles, rectangle, right trapezoid, but not circle or ellipse), and they are usually just some…
david z
- 11
- 1
1
vote
2 answers
plane intersection angles to determine if a point is in a plane, floating point and method questions
I have been doing some work to analyze sets of 5 points in the general configuration.
[![5 points in 3 space][1]][1]
[1]: https://i.stack.imgur.com/ln51Z.jpg
One question I am addressing is whether or not points A, B, E, and D are in the same…
LMHmedchem
- 41
1
vote
1 answer
Can I uniquely identify a convex, closed polyhedron given the number of sides in each face?
FYI: I'm coming from a Computer Science/Computer Graphics background, so my terminology might not be 100% precise.
I have a collection of polyhedra that I would like to decompose into tetrahedra. Instead of using a general-purpose algorithm for any…
Justin
- 171