Tagged Questions
2
votes
1answer
65 views
Computational geometry
Computational geometry?
(Computational geometry) Given a set of n randomly scattered points for even
n = 2,4,6,...,50 . Find the maximum number of lines between the pairs of nodes in
such a way the ...
1
vote
1answer
36 views
Circle Packing: Unsolved Problem in Geometry?
Graham and Sloane minimize the second moment of the centres of a number discs in order to maximize their compactness. They use computational geometry techniques to find the optimal packings for ...
3
votes
1answer
43 views
Linear, Bi-linear or better
I have been writing some code to do some interpolation of 2D data on an irregular grid. So far what I have done is:
Triangulate the known points using Delaunay.
Find the vertices of the triangles ...
1
vote
2answers
50 views
How to find co ordinates of a triangle after increasing the area by a factor of $\alpha$?
i am given with a triangle $\{(x_1,y_1),(x_2,y_2),(x_3,y_3)\}$ and the area need to be increased by a factor $\alpha$. can i anyone let me know formula to find the co ordinates of new triangle? There ...
2
votes
1answer
30 views
How to estimate orientation errors of an image with respect to known data (line features)
I think this is very simple but for me, it is confusing to figure out a way.
Here is my problem.
I have been given a 3d line segment list obtained from a field survey. So I know each end point ...
1
vote
1answer
38 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' ...
0
votes
1answer
38 views
$2$ planes and angle between them
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, ...
5
votes
2answers
47 views
Find the most vertical line in a point set in $O(n \log n)$ time
Input: a set of $n$ points in general position in $\mathbb{R}^2$.
Output: the pair of points whose slope has the largest magnitude.
Time constraint: $O(n \log n)$ or better.
Please don't spoil the ...
2
votes
1answer
89 views
Obtaining Least square adjusted single line by intersecting many 3D planes
I am working with many 3D planes and looking for a Least square solution for below case.
IF I am having many number of 3D planes knowing only one point and the
normal vector (for eg. O1 and N1), ...
1
vote
2answers
132 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 ...
1
vote
3answers
50 views
Are there any Heron-like formulas for convex polygons?
Are there any Heron-like formulas for convex polygons ? By Heron-like I mean formulas without angles as arguments and which takes as arguments only lenghts of sides of polygon - that is - we know no ...
0
votes
1answer
85 views
The equation for the circle defined by two intersecting spheres in 3-space?
We define two spheres, $S_1$ and $S_2$, of radius $r_1$ and $r_2$, centered at 3-space points $p_1$ and $p_2$, respectively. What equation gives the circle in 3-space at the intersection between the ...
1
vote
2answers
49 views
What is the equation stands for in geometry(intuitively)?
I am writing a bilinear interpolation method.
This method can be abstract by solve the equation A*x = b, A is a 4x4 matrix below:
$A=\begin{pmatrix}
1 &x_1 &y_1 &x_1y_1\\
1 ...
-1
votes
1answer
79 views
How to change XYZ axes system into another 'xy' system
I have $3D$ point set lying on a vertical plane. This plane is not parallel to either $X$ or $Y$ axis but makes an angle (say, $\theta$) to $X$ axis. And also it has some ($+$ or $-$) intercept to the ...
0
votes
1answer
54 views
Notation and meaning of coordinate system in geometry
I am trying to understand projective geometry to build a 3d scanner, using this text.
http://mesh.brown.edu/byo3d/notes/byo3D.pdf
When describing an idea pinhole camera it says
In the ideal ...
0
votes
0answers
21 views
best way to estimate deviation of 3d line segments with respect to reference segments
I have set of 3D line segments derived in two different method. These line segments represent edges of several 3d cubs and polygons.
(1) first set of line segments are derived by doing field ...
1
vote
1answer
43 views
$2d$ line equations in polar coordinates
I know in polar coordinates, a $2d$ line equation is given in the form of $$r = x \cdot \cos(\theta) + y \cdot \sin(\theta),$$ where the parameters are defined as in this.
I want to derive an ...
0
votes
1answer
31 views
a line perpendicular to a given line
I am confused now,
I have a 2D line. If its equation is $r = x\cos(\theta) + y\sin(\theta)$,
then what will be the line which is perpendicular to that line?
Where $r, \theta$ is described ...
-1
votes
1answer
60 views
Limiting search space for efficient line matching [closed]
I have 2D line segments extracted from an image. So i know end point coordinates of them. also, i have some reference 2d line segments. Both line segments are now in vector form. comparing to ...
1
vote
1answer
184 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
1answer
40 views
Shortest triangulation is in general not a Delaunay triangulation
Let $P$ be a set of points. The minimal triangulation of $P$ is a triangulation $T$ of the points in $P$ such that the total length of the edges in $T$ is the smallest possible amongst all possible ...
3
votes
1answer
224 views
Star-Shaped polygons
We call a polygon star-shaped if there exists at least one point for which the entire polygon is "visible" from that point. The set of such points we call the kernel of the polygon.
The art-gallery ...
0
votes
1answer
72 views
How to move a one 3D line from three 3d parallel lines
I have 3 parallel line segments (say AB, CD, and EF are line segments and they are nearly horizontal) lay on 2 slanted planes which have been intersected through the CD. If I projected all the line ...
0
votes
1answer
138 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 ...
4
votes
0answers
76 views
How many points does one need for an epsilon-net
Does anyone know, how many points does one need to have an $\varepsilon$-net on a unit sphere sitting in the three-dimensional Euclidean space? Thanks!
3
votes
2answers
70 views
Voronoi Diagrams Proof
I am having a real problem with this proof about voronoi diagrams:
Prove that $V(p_i)$ (i.e., the cell of $\operatorname{Vor}(P)$ which corresponds to $p_i$) is unbounded if and only if $p_i$ is on ...
1
vote
2answers
188 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 ...
3
votes
1answer
217 views
Ellipse center with three points and the semi-axis lengths given
Having three given points in the two-dimensional plane and semi-axis lengths $a$ and $b$ of an ellipse, how to determine the center? By construction (the "Euclidean way") or analytic geometry.
0
votes
0answers
96 views
Maximum diameter of a 2D shape
What is the diameter of an arbitrary 2D figure? (Diameter=The longest distance between two points within the 2D figure). What is the most efficient algorithm? Is it an exact one? Specifically, could ...
0
votes
2answers
169 views
Is this a wrong solution to the smallest enclosing circle problem?
I have a set of points in $\mathbb{R}^2$ and I need to find the smallest enclosing circle, i.e. the circle with the smallest radius that contains all of the points belonging to the set.
I have the ...
-2
votes
4answers
146 views
The equation of the plane [closed]
In geometry 3D, let $A(1,2,1)$, $B(-2,1,3)$, $C(2,-1,1)$, $D(0,3,1)$ be four points. Write the equation of the planes $(P)$ which passes through the points $A$, $B$ and equidistant from the two points ...
1
vote
2answers
33 views
How does one compute the minimal bounding sphere of a k-simplex?
Suppose I have a list of $k+1$ points in $\mathbb{R}^n$, and I let $\sigma^k$ be their convex hull. I want to know two things:
How can I determine, for any $\varepsilon$, whether open balls of ...
0
votes
3answers
127 views
How to find on which outer side of the rectangle falls the point?
Qt has a class QRect which tells whether the point is inside the rectangle or not.
Now, the problem is to find out on which ...
6
votes
7answers
297 views
Detect when a point belongs to a bounding box with distances
I have a box with known bounding coordinates (latitudes and longitudes): latN, latS, lonW, lonE.
I have a mystery point P with ...
8
votes
1answer
232 views
“Cut” (hexagon-like) Reuleaux triangle area
Let me start by giving the reason my question: as part of a 3D printer I'm building (Rostock), I'm trying to figure out the work area of the printer. The printer consists of 3 arms, each attached at ...
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, ...
0
votes
1answer
107 views
distance between a polytope point and a polytope vertex
How to find distance in between any polytope point to the closest vertex of the polytope (the verteces of the polytope are known)?
How to find a distance from the farest polytope point to the closest ...
1
vote
2answers
281 views
Polarity of the Surface Normal of a 3D triangle
I have a triangle (defined in 3D space) that has 3 points (p1, p2 and p3).
Is it possible to work out what the polarity of the surface normal would be for the face knowing it lists each point in an ...
0
votes
2answers
151 views
Gram-Schmidt Orthogonalization - does it distort?
I am writing a 3D solar panel positioning programme and have a section of code where I use the Gram-Schmidt Orthogonalization process to go from 3D to 2D for easier calculations.
(For reference, here ...
1
vote
2answers
491 views
Given a tetrahedron, how to find the outward surface normals for each side?
Say I have a triangle in $3$D space. I can get the surface normal by calculating the vector cross product of two of the edges.
But, lets say I make this a tetrahedron. How can I work out the outward ...
0
votes
1answer
114 views
Calculating the norms of a triangle based pyramid
Hi I have the following co-ordinates, which make up my triangle based pyramid. I need to calculate the normals of each face. However Im struggling to find the best simplest way to do this?
...
0
votes
3answers
379 views
Calculating start/end points of a line segment given by a set of points and normal direction
I have a set of $3$D points representing a line segment. Points are not equidistant distributed on the line segment. Points are also unordered. I also have the center point and the normal to the line ...
0
votes
1answer
112 views
Arc direction in given point
I have an arc with a given center, start angle, end angle, and radius.
I want to draw an arrow showing the arc direction in the arc middle point. What is the easiest way to calculate this direction ...
0
votes
1answer
92 views
Analytic Intersection of Objects Located on a 3D Grid's Vertices
I previously posted this question on stackoverflow, but it's really more of a mathematical question. I have reworked the question for presentation here.
I have a regular 3D unit cubic grid of ...
2
votes
1answer
126 views
Drying blood - an algorithm for calculating the geometry of blood stains
Motivation
A bucket full of blood gets spilled over the floor. Question: What shape will the dried blood stains have?
Abstraction
The blood is modeled by a set of interacting particles (e.g. SPH). ...
0
votes
0answers
165 views
distance to Triangle using barycentric coordinates
So, I'm trying to efficiently calculate the distance of a point to a triangle $d(\omega,T)$ using barycentric coordinates via the method described in this paper A Hybrid GPU Rendering Pipeline for ...
2
votes
1answer
70 views
Maximizing the number of points covered by a circular disk of fixed radius.
Given a set of points in two dimensional space, and a radius r, what is the algorithm to find a disk of radius r that covers the maximum number of points?
1
vote
2answers
135 views
Best fit for 'puzzle' shapes inside a frame
Consider a large rectangle frame, as we want to fill it with small rectangles with variable sizes. How to calculate the best match of inner objects to minimize empty spaces inside the main frame?
...
0
votes
1answer
129 views
How to “stretch” a procedural half-sphere texture on X and/or Y axis
I've implemented an Objective-C function to display the "height" of a half-sphere, with "1.0" being "full-height" and "0.0" being "no-height"
The sphere currently has a few parameters:
Center (x,y: ...
3
votes
4answers
1k views
Find the area of overlap of two triangles
Suppose we are given two triangles $ABC$ and $DEF$. We can assume nothing about them other than that they are in the same plane. The triangles may or may not overlap. I want to algorithmically ...
