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
0answers
206 views

Line comparison algorithm advice

Line is array of points (2 or more). I have a plane full of lines. For a given line in plane I need a measure which will tell how much difference there is between this and any other line in plane. I ...
1
vote
0answers
72 views

Questions about interpolating translated points from a grid

I would like to do the following transformations on a very low resolution bitmap (64x64 pixels). I am doing this transformation on a computer images, but it has nothing to do with computers, you can ...
1
vote
0answers
126 views

Nonlinear least squares and polygon area

I found this paper that describes preserving the global area of a polygon given some deformation (section 5): http://www.kunzhou.net/publications/2DShape.pdf I'm trying to do something very similar. ...
1
vote
1answer
529 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
0answers
101 views

Complexity of Counting the number of inducing $n$-gons

Definition: A $n$-gon is simple if it has no self intersection and is in general position if no pair of its edges are parallel. It is clear that by extending the edges of each simple $n$-gon in ...
0
votes
1answer
127 views

2d rotation falls spirally inwards?

I recently started with 2d transformations in my class. I was just working with a program when I realized the formula I am using rotates the object spirally inwards. I have no idea whats over about ...
0
votes
3answers
616 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
2answers
462 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 ...
0
votes
2answers
281 views

Given a Set of Points, Find All the Triangular Faces that Connect Them Together

Let's say I have a list of points( in 2D coordinates!) with the vertex $V$, how to find all the triangular faces $F$ ( which has three edges $E$) that covers all of the points? In other words, I'm ...
0
votes
2answers
113 views

Proof of the following: How many $(n-2)$ dimensional faces from a corner of a hypercube

I asked a question earlier regarding the number of $(n-2)$ dimensional faces exiting a corner of an $n$ dimensional hypercube. (For example the number of points in a corner of a square, or the number ...
0
votes
3answers
204 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 ...
0
votes
3answers
53 views

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
1answer
517 views

Area of Union of n circles

I am trying to calculate the area of union of n circles in a plane when it is known that all circles are of equal radii and their centers are also known(of all n circles). I was trying to follow the ...
0
votes
1answer
163 views

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 ...
0
votes
2answers
109 views

Computational Geometry journals

What are good computational geometry journals? I'm also counting geometric modeling as part of computational geometry. Are there any good journals that are considered to be non-mainstream in the US?
0
votes
1answer
413 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 ...
0
votes
1answer
106 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
120 views

How can a Bézier curve be periodic?

As I know it, a periodic function is a function that repeats its values in regular intervals or period. However Bézier curves can also be periodic which means closed as opposed to non-periodic which ...
0
votes
1answer
109 views

Draw a polygon that satisfies this criterion

Draw a picture of a simple polygon and a set of guards, such that the guards can see every point on every edge of the polygon, but the guards cannot see every point in the interior of the polygon. I ...
0
votes
1answer
101 views

Prove that there is a set of n points such that a voronoi cell contains n-1 vertices

We need to prove the following claim: There exists a set of n points such that voronoi cell of one of the points contains n-1 vertices. I think in the following case voronoi cell for point C ...
0
votes
1answer
316 views

Computing the average coordinate for more than 2 points on a 3d line segment

Suppose, I have many 3d line segments which suppose to be intersected with another given line segment. So, I wish to take a line segment and the given line to get the intersection point. Again, I wish ...
0
votes
1answer
220 views

plane intersection in practical sense

suppose i want to model a 3D plane intersections when they make a corner. that is three or more than three planes will be intersected at some corners of cubes or other volumetric objects. i can find ...
0
votes
1answer
64 views

“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 ...
0
votes
1answer
116 views

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 ...
0
votes
1answer
50 views

Transforming a circle to get a parabola

On http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/geometry/geo-tran.html I am unable to understand the following point Obviously, this transformation sends (x,y,w)=(1,0,1) to (x',y',w') = ...
0
votes
1answer
34 views

Desargues Theorem with integer coordinates

Desargues' theorem involves a set of ten points in a plane or in three-dimensional space. (It's true in higher dimensions, but the affine span of the ten points involved never has a dimension more ...
0
votes
1answer
206 views

How to find whether the line is inside the polygon or outside.

I have a polygon How can i prove whether the black color line lies outside the polygon or inside the polygon . Given the coordinates of the black line and all the vertices of the polygon.
0
votes
1answer
72 views

Packingof Spheres in 3D

I am looking to find out the size of the largest sphere , that can fit in the voids created by packing spheres ( hcp) of radius R.
0
votes
1answer
69 views

Correcting plane parameters with the fixed azimuth angles

I am trying to reconstruct specific 3d objects such as cubes, pyramids and so on. For this, i am using point cloud data and then fitting planar surfaces for the segmented point patches. Planes ...
0
votes
1answer
826 views

How to find rotation angles along X,Y,Z axes with a known vector to bring the axes to correct situation

I am working with 3d point data. When I checked the data I realized that there is some error on my data and need to do some kind of rotational rectification because the points which should be ...
0
votes
1answer
173 views

my plane is not vertical, How to update 3D coordinate of point cloud to lie on a 3D vertical plane

I have a bunch of points lying on a vertical plane. In reality this plane should be exactly vertical. But, when I visualize the point cloud, there is a slight inclination (nearly 2 degrees) ...
0
votes
1answer
241 views

closest pair in N-Dimensional

I have to find the closest pair in n-dimension, and I have problem in the combine steps. I use the divide and conquer.I first choose the median x, and split it into left and right part, and then find ...
0
votes
1answer
140 views

Perpendicular to a vector at point on the vector

I am working with a model where I have to calculate a perpendicular to a vector through two points $\mathrm{P_1}$ and $\mathrm{P_2}$ (3d) at point $\mathrm{P_3}$ on the line joining these points. ...
0
votes
1answer
61 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, ...
0
votes
1answer
68 views

obtainig a line 3D from multi view geometry

If I have been given multiple view images having known orientation parameters, then from a selected image line segment (corresponding line segments from each image) how could I compute a line 3D in ...
0
votes
1answer
317 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 ...
0
votes
1answer
127 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
1answer
45 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 ...
0
votes
1answer
289 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 ...
0
votes
2answers
197 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
1answer
245 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
1answer
216 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
61 views

What are the $\{x,y,z\}$ values of a vector?

A vector is often described as $\{x,y,z\}$ similarly to a $3$D point's cartesian coordiantes in CAD tools which is quite confusing. What are the $x$, $y$ and $z$ values in the case of a vector?
0
votes
1answer
197 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: ...
0
votes
1answer
71 views

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 ...
0
votes
1answer
373 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
1answer
131 views

What is the X, Y, Z “resolution” of a three-dimensional grid of points?

I came accross a software which requires the X, Y and Z resolution of a three-dimensional grid of points as Integer. What is a "3D grid resolution" and how do I find it? From what I understand, the ...
0
votes
1answer
434 views

Improving Gift Wrapping Algorithm

I am trying to solve taks 2 from exercise 3.4.1 from Computational Geometry in C by Joseph O'Rourke. The task asks to improve Gift Wrapping Algorithm for building convex hull for the set of points. ...
0
votes
1answer
97 views

How to find a parametrization of a equation and to draw its picture.

I was wondering how to find a parametrization of $(x-t)^2+(y-t^2)^2-t^2=0$, and how to use a software like Mathematica to draw a picture of this equation based on the parametrization. Thanks in ...
0
votes
1answer
131 views

“Way” to decide if points are in a rectangle.

Suppose $P_1=(x_1,y_1)$, $P_2=(x_2,y_2)$ are two points. Also suppose that we have a rectangle which we just know the value of its sides $a$ and $b$. I am looking for some kind of formulation which ...