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
Divide set of points by a plane so sum of distances of points on either side of plane is equal
I have a finite set of points A and another point C. I would like to compute a vector N so that the plane defined by C (point on plane) and N (normal of plane) divides all points in A with the sum of distances of points to the plane on either side…
a593971
- 1
0
votes
0 answers
Accessibility from start position to goal position in 2d plane
Given a vehicle with irregular shape in 2d plane, and its start position and start orientation, like (sx, sy, sori), and also its goal position and goal orientation, like (gx, gy, gori). Between the start and goal, there're several irregular shaped…
Lym Zoy
- 101
0
votes
2 answers
Check Whether a Polygon "Fits into" a 2-D Triangular Mesh
Suppose there is a polygon $\mathcal{P}\subset\mathbb{R}^2$ and a set of triangles $\mathcal{T}\equiv\{T_i\}_i$ that partitions $\mathcal{P}$. My question is, given any polygon $\mathcal{Q}\subset \mathcal{P}$, is there any algorithm (other than…
ArGenya
- 133
0
votes
1 answer
"full coverage" in hyperspherical space
I'm working on a computer algorithm that considers the relationships between data points in a theoretical n-dimensional space.
I am "looking" from the origin in all directions in a programmatic way that will help me cull out some of the unneeded…
Matt
- 101
0
votes
1 answer
Minimum path cost through a line segment
Given point $A$, point $B$, and a line (segment), I am trying to find a point $I$ on the line so that the total cost of a path from $A$ to $I$ and then to $B$ is minimal. I can calculate this in a simple case when I am directly summing the Euclidean…
Juraj Blaho
- 101
0
votes
0 answers
Largest Circle Enclosed In Oriented Minimum Bounding Box But Not Including Points/Lines
I am wondering if someone can suggest a way to find the largest circle that can fit within the oriented minimum bounding box for a set of points/lines, that does not include any of the points/lines.
Consider these two images:
Cross
Tee
Each image is…
0
votes
1 answer
Internal diagonals of polygon
How find all inner diagonals of the non-convex and simple polygon in O(N*N) and better. My solution consisting of two steps
A] throw all intersecting diagonals: test if diagonal intersects any edge of the polygon
b] test, if diagonal is inner/or…
Robo
- 1
0
votes
0 answers
Disk containing all points of one set and none of the other.
One problem states:
Given two sets $A_1$ and $A_2$ with $n_1$ and $n_2$ points respectively, design an algorithm to compute (if it exists) a disk containing all the points in $A_1$ and none in $A_2$.
My idea is to calculate the minimum spanning…
Lecter
- 449
0
votes
1 answer
Does this method of determining whether a point is included in a polygon work, and where can I find a reference?
The problem: given vertices that define a polygon, determine whether another point $P$ lies inside the polygon or not.
Proposed solution: suppose we have a triangle $A, B, C$. Calculate the areas of the triangles that $P$ forms with the other…
Eli Rose
- 8,141
0
votes
1 answer
how can I express a median in terms of barycentric coordinates?
I am trying to understand relationship between Median and barycentric coordinates.
here is a figure (fig_1) comes from wiki
that post gives a good explanation and I am trying to connect the notation in that post to fig_1.
Vertex of such small…
JJJohn
- 1,436
0
votes
0 answers
Is.Obtuse triangle function/algorithm
I am trying to compute a function (in R although what I am looking for is the algorithm) that:
Given 3 points in the plane return a 1 if the triangle formed by these 3 points is obtuse and 0 in other case.
I'd rather prefer not to use the…
0
votes
1 answer
Does a generalized intersection test exist? If yes, how does it work?
I'm looking for an algorithm to test if an N-dimensional object (defined by the convex hull of N+1 vertices) and an M-dimensional object (defined by the convex hull of M+1 vertices) intersect within L-dimensional space (where L is greater than or…
0
votes
4 answers
Maximum distance between a line segment and a polygon
Given a (non-convex) Polygon $P$ and a straight line segment $S$ in $\mathbb{R}^2$, where $S$ and $P$ are disjoint, I am looking for an efficient algorithm to find a point $s$ on $S$ which has the maximum distance from $P$ among all points on $S$…
Doc Brown
- 210
0
votes
1 answer
Algorithm to represent a vector as linear combination $(3d$ to $2d$ plane$)$
Community,
I have a geometric library that allows to do multiple things with $2d$ curves (circle, plane, line segment, etc.) in $3d$ space. For specific operations (like the intersection between $2d$ circle and $2d$ line) it would be easier, to…
Augunrik
- 103
0
votes
0 answers
Cost Function to match 2D Points with Velocity
I have a set of 2D Points at time $T=0$, and another set at time $T=1$. Each point $P$ provides (X,Y,$\dot{X}$,$\dot{Y}$).
I need to basically match points at $T=0$ and $T=1$. A simple L2 metric of $\left \| P^{t=0}, P^{t=1} \right \|$ won't work,…
user1436508
- 376