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
2answers
866 views

Check if point on circle is in between two other points (Java)

I am struggling with the following question. I'd like to check if a point on a circle is between two other points to check if the point is in the boundary. It is easy to calculate when the boundary ...
8
votes
4answers
810 views

Every polygon has an interior diagonal

How does one prove that in every polygon (with at least 4 sides, not necessarily convex), that it is possible to draw a segment from one vertex to another that lies entirely inside the polygon. In ...
2
votes
3answers
290 views

What does “identity map $id$” mean?

What does "identity map $id$" mean in this context? Two metrics $d_1$ and $d_2$ on $X$ are said to be Lipschitz equivalent if the identity map $id\colon (X,d_1)\to (X,d_2)$ is bilipschitz.
0
votes
2answers
117 views

Finding maximum value of smallest triangles over all triangulations

Given simple polygon we have to find maximum area of smallest triangle in all possible triangulations. I was trying to solve it by generating all possible triangulations, but for complex polygon it ...
3
votes
1answer
133 views

Generating all triangulations of simple polygon

Having simple polygon how can we generate all triangulations of this polygon? How can it be done ? What would be the approach ? I didn't find any paper explaining it, only about planar triconnected ...
8
votes
2answers
125 views

Efficient method for detecting a convex body in $\mathbb{R}^n$

Let $K_0$ be a bounded convex set in $\mathbf{R}^n$ within which lie two sets $K_1$ and $K_2$. Assume that, $K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$. The boundary between $K_1$ and $K_2$ is ...
3
votes
0answers
415 views

Detecting Planes through Point Cloud

Having a point cloud say (10000 points) which are randomly dispersed in 3D unit cube, the question is how to find planes within the cube that include more points with an acceptable tolerance (user ...
1
vote
0answers
75 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
4answers
297 views

What is the name for a maximal convex set of points contained in another set of points?

What is the name for a maximal convex set of points contained in another set of points X? Maximal in terms of inclusion. For the desired set to be unique, X can be restricted to be a simple polygon ...
3
votes
2answers
52 views

Finding how many points to which a certain point is connected

This may be a programming issue, not a mathematical one. If so, please let me know so that I can rewrite it specifically for that audience. Consider a shape with a random border. Each point on its ...
2
votes
0answers
590 views

Is there a formula for the solid angle at each vertex of tetrahedron?

A tetrahedron has four vertices as much as a triangle has three vertices. A tetrahedron therefore can have four solid angles as much as a triangle can have three angles. I am wondering: Is there a ...
1
vote
1answer
86 views

Line segment k-intersection

Could you please help me to design the following algorithm: I have a random-access list of line segments defined by a pair of points $[x^s_i; x^e_i]$. The list is initially unsorted, but of course ...
1
vote
1answer
83 views

Algorithm to compute mesh from intersection of infinite halfspaces

Is there a simple algorithm to compute the convex polyhedron (as a mesh with verticies, edges, and faces) resulting from the intersection of a set of infinite halfspaces? This is essentially a CSG ...
3
votes
2answers
138 views

How do I apply a digital filter to points on a sphere

Given a set of points on a sphere, how can I implement a higher order low pass filter on them? At the moment, I am just multiplying the vectors from the input and output set by their weights and ...
0
votes
1answer
154 views

Explanation of a formula for spherical 3d tag cloud

I am not an expert in mathematics, I am only a young programmer. I am trying to construct a spherical tag cloud and I've found this formula: ...
4
votes
1answer
177 views

Determine if circle is covered by some set of other circles

Suppose you have an existing set of circles $\mathcal{C} = {C_1, .., C_n}$ each with a fixed radius $r$ but varying centre coordinates. Next, you are given a new circle $C_{n+1}$ with the same radius ...
2
votes
0answers
761 views

How to find all intersection points of two splines?

2D-Cubic splines are given in parametric form (X(t), Y(t) and X(s), Y(s)). Every segment has it's own X and Y expression. And I want to find all intersection points. Some segments are intersecting ...
1
vote
0answers
136 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. ...
5
votes
2answers
371 views

Algorithm for positioning rectangles of various size into a larger rectangle

I am working on tool for merging smaller textures into one larger for use on Android app. I have $n$ rectangles of given size $(w_k, h_k)$, where $k=1,\ldots,n$ and I need to position them within ...
3
votes
1answer
147 views

Drawing Triangles from a List of Incircles?

I have drawn the incircles of triangles which were generated through a delaunay triangulation but lost the original delaunay mesh. Is it possible to invert the process and draw the triangles back from ...
1
vote
2answers
167 views

Handling points to get closed Cycles

I have set of line segments, containing only 2 points. I know their point numbers. some point numbers are appeared in many lines according to their connections. So, when joining some end points, I can ...
2
votes
1answer
576 views

How to fit largest circle within Voronoi cells?

I have a list of Voronoi cells and would like to place the largest circle possible within each cell. What is the best way to do that? Many thanks, Arthur
0
votes
1answer
2k views

Point reflection over a line

I'm having trouble understanding the solution presented below (It's from a textbook). I tried to get something similar, but to no avail. Help me find the way he derived those a,b,x2 and y2 ...
4
votes
1answer
220 views

How to predict the tolerance value that will yield a given reduction with the Douglas-Peucker algorithm?

Note: I'm a programmer, not a mathematician - please be gentle. I'm not even really sure how to tag this question; feel free to re-tag as appropriate. I'm using the Douglas-Peucker algorithm to ...
1
vote
2answers
5k 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 ...
2
votes
2answers
757 views

Finding the/a point within an irregular polygon which is furthest from polygon's line segments?

I'd like to determine which point(s) within an irregular polygon are furthest from the edges. Is there an existing algorithm to determine this? Also, if it's already out there, I'd like to do a ...
1
vote
1answer
221 views

Cover a polygon using a minimal set of rectangles

Given some polygon and rectangles all of a fixed height and width, how I can calculate the number and placement of the rectangles so that no point within or on the polygon is not contained within at ...
4
votes
3answers
310 views

Is it always possible to simply expand a simple 2D polygon with any point?

Given a simple 2D polygon P = ( M1 .. Mn ) and a point M, is it always possible to construct a new simple polygon P' by "adding" M to P as a new vertex? If so, is this always possible without ...
1
vote
1answer
214 views

Intersection of two sectors

Is there algorithm that decide if two sectors intersect? I can transform the sector into polygons and use standard algorithms, but it has some cons. Any other ideas?
3
votes
1answer
230 views

Delaunay-like algorithm to get four sided polygons instead of triangles?

Is there an algorithm similar to the Delaunay triangulation which can organize a set of points into a set of four sided polygons instead of triangles?
1
vote
2answers
2k views

Two plane intersection and angle between 2 planes

I am trying to implement my problems in different ways. So, may be though this question has some relation to some other questions, please answer me. We know; Intersection of two planes will be given ...
2
votes
1answer
211 views

What is the most accurate method to get intersection point in 3D?

I have been given 3D point data, belonging to different planar segments. Points are not exactly laid on the planes so that I have fitted best planes using least square solutions. Now, I want to find ...
3
votes
2answers
1k views

How to calculate volume of 3d convex hull?

Convex hull is defined by a set of planes (point on plane, plane normal). I also know the plane intersections points which form polygons on each face. How to calculate volume of convex hull?
9
votes
4answers
2k views

Find whether two triangles intersect or not in 3D

Given 2 set of points ((x1,y1,z1),(x2,y2,z2),(x3,y3,z3)) and ((p1,q1,r1),(p2,q2,r2),(p3,q3,r3)) each forming a triangle in 3D space. How will you find out whether these triangles intersect or not? ...
3
votes
2answers
185 views

How do I prove that the following method to find whether a point lies within a polygon is correct?

I came across the following method to determine whether a given point lies inside a convex polygon - however, I'm not sure how to prove it. Given any three points on the plane $(x_0,y_0)$, ...
0
votes
1answer
302 views

Obtaning a quality intersection line in 3D and variance-covariances contribution

I have edited the original post and then the question look like as follows; I have been given set of points having x,y,z coordinates and they already grouped into ...
0
votes
1answer
227 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 ...
5
votes
2answers
238 views

Test for intersection of two N-dimensional ellipsoids

Let's say I have two $N$-dimensional ellipsoids: $$ \sum_{i=1}^{N} \frac{(x_i - b_i)^2}{c_i^2} = 1 $$ $$ \sum_{i=1}^{N} \frac{(x_i - b'_i)^2}{c_i'^2} = 1 $$ How can I tell if the two ...
3
votes
2answers
180 views

Testing Whether a Vertical Line Intersects a Plane

Okay, so, I'm not the greatest with geometry (I actually need this for game development), but basically, I need to be able to test whether a vertical (the y-axis is my vertical axis for this) line ...
1
vote
1answer
475 views

3 line / 3 plane intersection

I am confused on a very simple thing, so I need your clarifications. Here is my doubt: I want to find the intersection point of three straight lines. Alternatively, I can find it by using three ...
2
votes
1answer
352 views

alpha shapes for polygonal boundary detection - for point cloud data

i am trying to implement alpha shape algorithm but the theories is quite hard to undestand. so, if any one know (or have) pseudo codes to implement alpha shape (2d) algorithm please post us. thanks
2
votes
1answer
187 views

Need line generalization method like Dougles Peuker, that is able to keep turning points along closed polygon boundaries (for 2d or 3d point data)

I have set of point clouds, representing boundaries of different closed polygons. These polygons contains 3d points. But they also can be considered as a 2d case once boundary points are projected to ...
3
votes
2answers
822 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)?
1
vote
1answer
2k views

Can Cox-de Boor recursion formula apply to B-splines with multiple knots?

We know that Cox-de Boor recursion formula can be used to compute the B-spline basis function. $$ N_l^n(u)=\frac{u-u_{l-1}}{u_{l+n-1}-u_{l-1}}N^{n-1}_l(u)+ ...
1
vote
1answer
597 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 ...
2
votes
1answer
954 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 ...
0
votes
1answer
561 views

Vertices of intersection between N spheres

Just wanted to know what is the best algorithm (in terms of speed and accuracy) to determine the intersection of N spheres (in 3D). With intersection I mean the following; in 2D and in the case of two ...
0
votes
1answer
51 views

How can I count waypoints between a curve?

I have curve that is drawn between point A and B. I want to divide this curve to 100 smaller waypoints. How can I determine what these 100 waypoints are as coordinates, when I only know points A and ...
5
votes
1answer
199 views

Efficient algorithm for finding how many times a point is inside the triangles formed by given points

Given n 2D points and a special point p, what would be the best way to find how many times p is inside among those $^nC_3$ triangles formed by the n points.
0
votes
1answer
65 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 ...