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
0
votes
1 answer
How do I find the average point of contact between overlapping boxes?
I am trying to write a physics simulator and have had a problem for weeks now.
I have two oriented bounding boxes in 3D space. An oriented bounding box is just a box of any dimension, location, and orientation. I am able to tell when these two boxes…
user8272
0
votes
0 answers
Find algorithm to produce integer points in a polygon
Algorithm to find integer co-ordinate points inside the convex polygon.
I have tried to find the intersection of horizontal and vertical line but failed the time complexity.
hEcuLE
- 39
0
votes
2 answers
How to get the coordinates to create a triangle?
I will create an equilateral triangle.
The starting point of the triangle will have coordinates x and y that can be any real number.
The starting point, geometrically, will be the vertex above the triangle.
Then, given a position (x, y)
What will…
0
votes
1 answer
Algorithm to compute the volume of a finite union of overlapping balls?
Suppose I have finite list of $n$ 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 this…
a06e
- 6,665
0
votes
1 answer
How to check whether an orthogonal intersection exists between two line segments
I'm working on an implementation of the MINDIST2POLY algorithm (see Pirzadeh, H. (1999) Computational geometry with the rotating calipers), to calculate the minimum distance between two non-intersecting convex polygons. A key step in the algorithm…
urschrei
- 145
- 4
0
votes
0 answers
Smallest enclosing circle proof
Can someone explain to me the proof of Lemma 1 (iii) in this paper http://www.stsci.edu/~RAB/Backup%20Oct%2022%202011/f_3_CalculationForWFIRSTML/Bob1.pdf
I'm having trouble understanding the reasoning behind the infinitesimal perturbation.
MadChickenMan
- 793
0
votes
1 answer
Volume of many randomly intersecting spheres
What is the optimal algorithm (or a fast one) to compute the volume of a large collection of spheres placed randomly in a large box? (No gravity, spheres can intersect, radius is small compared to box size)
I have around 2000 spheres.
Later I want…
its_me
- 11
0
votes
1 answer
The Mathematics of Putting TextBox Nicely on a Graph
I have a line graph, Given some certain points on the graph, I wish to add some explanation on them, such as this:
Is there any mathematical algorithm that allows me to overlay my explanation textbox "nicely" on the graphs, avoiding self…
Graviton
- 2,292
0
votes
3 answers
What does the letter $t$ stands for in "$t$-value of a curve"?
The "$t$-value of a curve" is the parameter of a point on a curve. For example if a curve's domain is form $0$ to $1$, then a t-value of $0.5$ would be a mid point. What does the letter $t$ stand for?
0
votes
3 answers
How to traverse circle coordinates?
The problem I have is:
Fill a circle by drawing one-pixel-wide horizontal lines across its inside area.
My initial thought is to generate the circles' coordinates symmetrically to a vertical axis passing through its centre, using the parametric…
Ziezi
- 631
0
votes
1 answer
Wrapping polyhedral of a volumetric mesh
How can I calculate and find the wrapping polyhedral of a mesh which is hexahedral? I mean I have to remove inner elements from my mesh and just have the faces and elements that can be seen from outside.
Kayhan Asghari
- 103
0
votes
1 answer
Voronoi diagram of a set of vertices of a mesh.
i have a triangulated mesh. I have some vertices which are part of the vertices of the mesh. Is there any algorithm to compute the voronoi diagram of these set of vertices. The triangulated mesh surface is non-planar. The resulting voronoi diagram…
user243654
0
votes
0 answers
What is the shape of the set of integer sided acute triangles with largest side n?
I played around with Gauss circle problem and found that if you take a certain sum in reverse and "in forward" and subtract the resulting sequences you get the OEIS sequence:
https://oeis.org/A247588
starting:
1, 2, 3, 5, 6, 8, 11, 13, 15, 17, 21,…
Mats Granvik
- 7,396
0
votes
0 answers
What does "maximum geometric error of a chunk" mean?
In this paper, on the top of page 7 it says,
Where $\delta$ is the maximum geometric error of a chunk ...
What does that mean? Thanks :D
0
votes
0 answers
How to navigate around a smooth surface?
Suppose I want to find the shortest path between two points in $\Bbb{R}^3$ with smooth obstacles in the way? I understand things like Dijkstra's algorithm for shortest paths on a graph. But what about in smooth land? In real life I could stretch a…
amcalde
- 4,674