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 ...
60
votes
18answers
5k views
How to check if a point is inside a rectangle?
There is a point (x,y), and a rectangle a(x1,y1),b(x2,y2),c(x3,y3),d(x4,y4), how can one check if the point inside the ...
12
votes
5answers
949 views
Is it possible to solve any Euclidean geometry problem using a computer?
By "problem", I mean a high-school type geometry problem.
If no, is there other set of axioms that allows that?
If yes, are there any software that does that?
I did a search, but was not able to ...
3
votes
0answers
366 views
Circle Packing Algorithm
I have question related to circle-packing. The problem is to find the circle of minimum radius enclosing four non-overlapping circles of arbitrary radius. I have to write a program in C for this ...
2
votes
3answers
87 views
Formal proof for detection of intersections for constrained segments
They told me it was off-topic at stackoverflow.
So I am trying my luck here. Yes, it's a homework, but I'm looking for some guidance (or related literature) instead of complete solutions.
Please see ...
2
votes
2answers
229 views
Uniform thickness border around skewed ellipse?
I have an ellipse with a given major and minor 'radius'. I then apply a 2D skew affine transformation to it. Then, I want to draw a uniform border inside this new shape, as if a circle were rolled ...
1
vote
1answer
181 views
How to find the intersection of the area of multiple triangles
I have a couple of questions regarding finding the intersection of triangles. I have a system of 16 projectors that all have slightly different color gamuts. The color gamuts are represented by a ...
2
votes
2answers
1k views
How to multiply vector 3 with 4by4 matrix, more precisely position * transformation matrix
All geometry in computer graphics are transformed by position * transform matrix; The issue is the fact that position is a vector with 3 components (x,y,z); And transform matrix is a 4 by 4 with one ...
2
votes
2answers
112 views
Did I write the right “expressions”?
$9$. Consider the parametric curve $K\subset R^3$ given by
$$x = (2 + \cos(2s)) \cos(3s)$$
$$y = (2 + \cos(2s)) \sin(3s)$$
$$z = \sin(2s)$$
a) Express the equations of K as polynomial ...
3
votes
2answers
202 views
What is the average rotation angle needed to change the color of a sphere?
A sphere is painted in black and white. We are looking in the direction of the center of the sphere and see, in the direction of our vision, a point with a given color. When the sphere is rotated, at ...
2
votes
1answer
222 views
Finding points on ellipse
I have ellipse in 2D. I want to compute fixed number of points on this ellipse with constant angular seperation between those points.
My first idea was to generate line equations from center of the ...
2
votes
2answers
308 views
Equation to check if a set of vertices form a real polygon?
Whats the equation to make sure a set of vertices, in clockwise or counterclockwise winding, actually form a polygon (without overlapping edges)?
2
votes
1answer
473 views
Solid body rotation around 2-axes
I am trying to understand how to describe the rotation of a solid body flying in 3D space. From physics forums, I understand that the rotation of any solid object in space, is around 2 axes ...
1
vote
2answers
131 views
Determing the distance from a line segment to a point in 3-space
Imagine I have a line segment defined by endpoints $p_1$ and $p_2$, and some 3-space coordinate $q$.
Is there a robust (in the sense of never giving divide-by-zero errors) way to quickly determine ...
3
votes
1answer
155 views
What is the complexity of computing the minimum distance between two convex polyhedra that both have $n$ faces?
EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity $O(n)$ (which is what my question is about) ...
2
votes
1answer
93 views
Showing: point of polytope which maximizes the minimum distance to a vertex is a barycentre?
Let $T_1$ and $T_2$ be two regular $(n-1)$-dimensional simplices with vertices $$(t,0,\ldots,0), (0,t,\ldots, 0),\ldots, (0, 0, \ldots, t),$$ and $$(t-n+1,1,\ldots, 1), (1, t-n+1, \ldots, 1), \ldots, ...
2
votes
1answer
131 views
Volume of n-dimensional convex hull
I have 2 algorithms for a problem. A solution to the problem is a set of n-dimensional vectors of 0/1's. A given solution covers any point inside the convex hull of the n-dimensional solution vectors. ...
2
votes
1answer
162 views
Prove ( or disprove) that for all kinds of simple polygon, the centroid lies inside the polygon
Is it possible to prove that for all kinds of simple polygon, regardless of whether it is convex or concave and with no opening, the centroid of the polygon must ( or may not) lie inside the polygon?
...
1
vote
1answer
37 views
angle between steepest gradient of two plane
IF I have two 3d planes such as Oab and Oa'b'. If these two planes intersect a horizontal plane and the intersection of each plane makes AB and A'B' lines. then,
Does the angle between AB, A'B' ...
1
vote
2answers
185 views
Proof that the Convex Hull of a finite set S is equal to all convex combinations of S
In $C^n$, how would you prove that the convex hull of a finite set $S$(convex hull being the intersection of all convex sets which contain $S$) is equal to the set consisting of all convex ...
1
vote
1answer
215 views
Meaning of this 4x4 determinant
Let $p,q,r$ and $s$ be four points on the plane. Moreover, $p,q,r$ are given in clockwise order. My book said that the following determinant is positive if and only if $s$ lies inside the circle ...
1
vote
0answers
194 views
differentiation of polygons, having cross borders
I have point data set and I segmented the data into different planar objects. after that, using contouring (convex hull), I obtained the boundary points. Please assume all points relevant to one ...
1
vote
1answer
347 views
Find out the border of a planar figure for given a set of points – 2D case
Original post is edited after getting some suggestions;
I am looking for a fast algorithm which is able to detect outer most boundary of a plane for given set of points. Suppose, I have 3D point ...
1
vote
2answers
179 views
Calculating probabilities on a spherical map
A black and white colored sphere is given.
We are looking at a random starting point on the sphere below us, which has a certain color. A random rotation can change the color of the spot below us.
...
1
vote
2answers
309 views
Fitting data to a portion of an ellipse or conic section
Is there a straightforward algorithm for fitting data to an ellipse or other conic section? The data generally only approximately fits a portion of the ellipse. I am looking for something that doesn't ...
0
votes
1answer
136 views
making three parallel lines (3d) with equal distance seperation
I have three parallel lines (3d lines). say AB, CD, EF. The center line i.e. CD is given by intersecting the two planes by which the AB, DE lie on. The shortest distance between AB and CD (say d1) is ...
0
votes
0answers
75 views
Minimize the number of ellipses to cover a region
Suppose I have n ellipses, $\left\lbrace E_i \right\rbrace_{i=1}^n $; each ellipse, $E_i$, has the same area $A_1$. I want to completely cover a region (assume a rectangle) , $R$, with the least ...
0
votes
2answers
508 views
Ellipse fitting methods.
I have set of points and want to fit ellipse to this set.
I have found only function which fits ellipse in least squares sense. In this set of points there are some noise points which should not be ...
0
votes
1answer
181 views
Visibility and Kernel of Polygon
I have an exercise to a give very rigorous prove to two observations of computation geometry. Obviously there are related. I've tried to prove them and wrote few ideas. Please take a look at them, and ...
0
votes
2answers
2k views
How to find the third coordinate of a right triangle given 2 coordinates and lengths of each side
p2
|\
|b\
| \
A| \C
| \
|c___a\
p1 B p3
If given point p1 & p2, side A & B how would you find point p3? I know given this information you ...
0
votes
1answer
148 views
Detect Abnormal Points in Point Cloud
Given a list of point cloud in terms of $(x,y,z)$ how to determine abnormal points?
The motivation is this. We need to reconstruct a terrain surface out from those point cloud, which the surveyors ...
