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 ...

learn more… | top users | synonyms

1
vote
3answers
88 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
458 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
66 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
vote
1answer
149 views

Algorithm Design for Delaunay Triangulation?

I am very much happy after seeing some very good answers in this site. I am trying to design a algorithm for the construction of Delaunay Triangulation using Randomized Incremental Algorithm.(I wont ...
3
votes
0answers
662 views

Turning radius of a vehicle

What's the minimum turning radius of a vehicle, rectangular in shape, with length l units and width w units? One key point to consider, would be that, the inclination of the front wheels can be ...
-1
votes
1answer
265 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 ...
6
votes
4answers
758 views

How to know location of a point?

I have a circle formed with three given points. How can i know whether another given point is inside the circle formed by previous three points. Is it determinant i need to calculate? Then what are ...
0
votes
1answer
173 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 ...
3
votes
0answers
137 views

How can I find a maximal inscribed ellipsoid to a *concave* set of points, in 3D?

I have a set of points which describe the surface of an irregular, natural (i.e., occurs in nature) object. This point set is not necessarily convex, and contains occasional indentations so parts of ...
0
votes
1answer
188 views

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 ...
1
vote
0answers
43 views

problem in dimensionality reduction

I am using multidimensional scaling to plot my data in R. However there is a hierarchy in my dataset which i want to exploit and I am using the delaunay triangulation to visualize the plot. So now I ...
1
vote
1answer
70 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 ...
2
votes
1answer
102 views

What is the mathematical relationship between the number of faces in a mesh and its vertices?

An "open and planar quad mesh" (more description below) with 4 mesh faces has 9 vertices, the same mesh with 8 faces has 15 vertices (2 faces at every X-axis row, 4 faces at every Y-axis ...
0
votes
1answer
52 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 ...
2
votes
0answers
69 views

Finding the smallest nonzero vector perpendicular to $\vec v$ with integer coordinates

Let $\vec v\in\mathbb Q^n$. Is there an efficient algorithm to compute the smallest (in the $\ell_\infty$ norm) nonzero vector $\vec w\in\mathbb Z^n$ such that $\vec v\cdot \vec w=0$? Equivalently, if ...
-1
votes
1answer
82 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
votes
1answer
184 views

Buddhabrot Sewing machine [closed]

The Buddhabrot fractal traces the orbits of the points outside the Mandelbrot set. What design considerations need to be taken into account to create a computerised sewing machine that traces out ...
0
votes
1answer
623 views

Solving vector equations with dot products

I'm working on a triangle-triangle intersection algorithm using this article ("The Line Intersection of Two Planes" part). The problem is that I don't know how to solve vector equations with dot ...
2
votes
0answers
358 views

Algorithm for Collection of Shortest Paths in a Grid without any clash at a point of time.

The efficient algorithm needs to be done and proved for the best solution for the given problem: User inputs: (#) Size of the NxN Grid. (N); (#) No. of Paths: Z; (#) Source and Destination ...
1
vote
1answer
646 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 ...
1
vote
1answer
183 views

Algorithm for computing the plane that passes through three arbitrary points

I'm writing a computer graphics library, and I'd like to compute the plane that passes through three arbitrary points, $p$, $q$ and $r$. I'm defining the plane in the form of $Ax + By + Cz + D = 0$. ...
0
votes
1answer
398 views

Radius of circle coverage of n circles in square packing configuration

Is there a reference about determining the minimum radius of a circle that would cover n circles of radius 1 that are in a square packing configuration ( see Wolfram's MathWorld packing packing ...
3
votes
1answer
223 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 ...
5
votes
1answer
1k 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
119 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
261 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 ...
1
vote
1answer
92 views

Diagonal of a convex polygon such that the obtained cuts have simmilar areas

Let $P$ be a convex polygon represented with a list of vertices specified by some orientation. Consider the following problem Problem. Find in linear time a diagonal of $P$ such that the absolute ...
4
votes
0answers
144 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!
1
vote
0answers
59 views

Integration through a Rotated Square

I have a 2D square S. S is described by s, the side length, theta, the angle it is rotated by, and c, the position of S's center. There is an axis-aligned rectangle R that extends infinitely in the ...
6
votes
2answers
144 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 ...
2
votes
2answers
2k 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
0answers
136 views

Approximating Bezier curves

I would like to approximate one cubic Bezier curve with two quadratic ones. In other words, I would like to split a cubic curve at some parameter t and approximate ...
3
votes
1answer
446 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.
1
vote
2answers
842 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 ...
-1
votes
4answers
201 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
71 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 ...
1
vote
1answer
184 views

Create wind animation

I'm trying to visually illustrate forecast wind speed and direction, the programming is the easy part, the math, I'm fuzzy on. I have a grid of points (lat/lon) , the forecast wind speed and ...
3
votes
1answer
903 views

Finding the virtual center of a cloud of points.

Given: (latitude, longitude) points $P_1, P_2,\ldots, P_n$. Presumably, all the points should form a dense cloud. However, noise is possible. Needed: The virtual center of the points. For ...
0
votes
3answers
280 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 ...
7
votes
7answers
1k 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 ...
88
votes
20answers
26k views

How to check if a point is inside a rectangle?

There is a point $(x,y)$, and a rectangle $a(x_1,y_1),b(x_2,y_2),c(x_3,y_3),d(x_4,y_4)$, how can one check if the point inside the rectangle?
9
votes
1answer
595 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 ...
4
votes
0answers
218 views

Partitioning a triangulated 2-sphere into two triangulated discs

Take a triangulation of the 2-sphere, $S^2$. Let the triangulation be denoted $T$. The Euler characteristic tells you that the number of triangles in $T$ is even. Since triangulations of the ...
2
votes
1answer
151 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
2answers
211 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
1k 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
223 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 ...
0
votes
0answers
69 views

Plot randomly oriented gaussian kernel

I would like to plot with scipy randomly oriented gaussian kernels. For a gaussian kernel along x and y axis (with an angle 0 w.r.t. coordinate system), I simply plot function ...
2
votes
3answers
2k 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
401 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? ...