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

Can Centroid Lies on the Edge of a Polygon?

This question is similar to the one here. Now the question is, given a simple polygon with $Area>0$, regardless of whether it is convex or concave and with no opening, can we prove that the ...
1
vote
2answers
220 views

Find outline of $N$ points in a plane

If I have $N$ point coordinates $P_i = ( x_i, \, y_i ) $ and I want to draw the outline connecting only the points on the "outside", what is the algorithm to do this? This is what I want to do: ...
1
vote
2answers
719 views

superellipsoid: problem in understanding parametric formula

hi i've found this interesting page: superellipse and superellipsoid and i used the formula for one of my computer graphics applications. i used (the most usefull for computer graphics) the parametric ...
1
vote
2answers
44 views

Circumcenter of Tetrahedron (in 4D)

I am trying to calculate the circumcenter of a tetrahedron in 4 dimensional space. Basically what I am looking for is the center of the smallest sphere which passes through all 4 vertices of the ...
1
vote
2answers
65 views

Estimating the missing points of a 3D point cloud

Consider a cloud of N points (forming a smooth 3D object), in which n points are missing. Also, consider that there is no prior knowledge about the original shape of the point cloud. The only ...
1
vote
2answers
112 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 ...
1
vote
2answers
297 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? ...
1
vote
2answers
49 views

Tetrahedra from it's inscribed sphere

I'm facing a geometrical problem: Given a sphere S, I want to calculate the vertices of the tetrahedra T whose inscribed sphere is S. In other words I want to calculate a tetrahedra from it's ...
1
vote
2answers
45 views

Point as an element of an affine space vs point as an element of a topological space?

I am searching for the "most natural" definition of a (geometrical/space) point as an element of "something" in mathematics (I am trying to design a small computational geometry library on strong ...
1
vote
2answers
609 views

Finding the tangents common to two rotated ellipses?

Is there a way to find the four tangents that two rotated ellipses share? I believe that if two ellipses do not intersect and do not contain one another, they will have four tangents in common and I ...
1
vote
2answers
99 views

Approximating Euclidean geometry, restricted to $\mathbb{Q}$

I'm having trouble putting this into a fully coherent question, so I'll give the broad question, then a few bullet points to give you a better idea of what I'm asking. I'm looking for a line of ...
1
vote
3answers
95 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 ...
1
vote
1answer
166 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 ...
1
vote
2answers
3k 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 ...
1
vote
1answer
937 views

The dual graph of the triangulation

I study Polygon Triangulation and have an execise. Prove or disprove: The dual graph of the triangulation of a monotone polygon is always a chain, that is, any node in this graph has degree at ...
1
vote
2answers
695 views

how can one calculate the minimum and maximum distance between two given circular arcs?

how can one calculate the minimum and maximum distance between two given circular arcs? I know everything of each arc: startangle, endangle, center, radius of arc. The only thing I don't know how to ...
1
vote
1answer
69 views

T-shaped polygons

Is there any coefficient that can indicate T-shaped polygons ? Examples of T-shaped polygons:
1
vote
1answer
233 views

Ellipse arcs. Draw a tangent line in the end point or make arc longer?

I read this article: link It describes how to draw ellipse arcs at all from svg. Each ellipse is described with the following params (and I know them): x1, y1, x2, y2 - arc from point (x1, y1) to ...
1
vote
1answer
121 views

Graphics clipping: How can repeated half-space clipping fail?

Hi I am currently going through the past exam problems and I am stuck on this clipping problem. Could you give me some hint on how to solve it? If we clip a polygon to a window, it is inadequate ...
1
vote
1answer
66 views

Center of Distance

I am given $N$ points in a 2D plane($x$ and $y$ coordinates). I have to find a point in this plane with coordinates $X$ and $Y$ such that: $$\sum_{i=1}^N \max\{|X - A_i|, |Y - B_i|\}\text{ is ...
1
vote
2answers
137 views

Checking convexity from outside

Is there any method or algorithm to determine convex (or non-convexity) property of a region from outside (perimeter) ? One way is plotting tangent line in each point of perimeter and discuss how ...
1
vote
1answer
128 views

Winding a space curve

Can I find parametric equations for a curve that is winding another curve, which I know -- let's say it's $\vec{f}(t) = (x(t), y(t), z(t)) = \{\sin (t)+2 \sin (2 t), \cos (t)-2 \cos (2 t), -\sin (3 ...
1
vote
1answer
109 views

Predicting the size of epsilon-net in SU(2)

I'm writing an algorithm that takes as input a finite set of matrices in SU(2) and consequently tries to generate an '$\epsilon$-net' by computing all possible matrix products (up to a given depth). ...
1
vote
1answer
71 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 ...
1
vote
1answer
718 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
202 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$. ...
1
vote
2answers
77 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
202 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 ...
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 ...
1
vote
1answer
452 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
2answers
157 views

General Proof Of Intersection Of Two Segments

Sorry for a silly question, I am trying to prove the fact of intersection of two segments on the plane. For example, $(d_1,d_2)$ is the first segment, where $d_1$ and $d_2$ are endpoint of the ...
1
vote
1answer
398 views

How to get a projected 3d line segment, lie on another 3d line parallel to that line segment.

I have a 3D line segment and another 3D position which locate slightly away from the line segment. I want to get the projected line segment (3D) which lies on imaginary 3D line which passes through ...
1
vote
1answer
98 views

Maximum number of points with a fixed minimum distance in a $d$-dimensional ball

Let $c \leq r$ be real numbers greater than $0$, $d \in \mathbb{N}$ and $B_r(0) = \lbrace x \in \mathbb{R}^d \mid \Vert x \Vert \leq r \rbrace$, the ball with radius $r$ at point $0$ ($\Vert \cdot ...
1
vote
1answer
105 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 ...
1
vote
2answers
172 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 ...
1
vote
1answer
85 views

Cutting a d-simplex

Why is it possible to get any possible subset of nodes of a d+1 simplex in IR^d using halfspaces?
1
vote
1answer
212 views

Algorithm to Choose Consistent Normals for All Faces on a Polyhedron

I have a polyhedron $P$, in 3D, which consists of $f$ faces, each face consists of $V$ vertexes. My question is, how to choose a consistent normal orientation for all the faces? Consistent here means ...
1
vote
1answer
427 views

Using Chazelle's simplicity test to verify simple polygons intersection

Is there a way to verify whether a non-empty intersection exists between two simple polygons (not necessarily convex) using the Chazelle's simplicity test ?
1
vote
1answer
35 views

Convex hull solving using a rubber band?

The convex hull can be found by stretching a rubber band so that it contains all the points and then releasing it. So my question is : lets assume that we have a robot (a theoretical robot) to solve ...
1
vote
1answer
34 views

Why simple polygons in plane have this property?

If we are given a simple polygon $P$ in the plane by the points $A_1, A_2, \dots, A_n$. How can we prove that there are $3$ consecutive points $A_i, A_{i+1}, A_{i+2}$ (if $i = n$, for $A_{i + 1}$ and ...
1
vote
2answers
39 views

Determining points on a circle in a particular plane

This is more of a computer graphics question really, but I was just wondering the efficient way to determine n equally spaced points on a circle, given a normal vector to the circle and the radius of ...
1
vote
1answer
326 views

Equation of hyperplane in Matlab

Given $n$ points in $n$-dimensions, using MatLab, how should we find the equation of the $(n-1)$-dimensional hyperplane passing through these $n$ points.
1
vote
1answer
22 views

find set of points for lots of triangulations

I should find a set of $n$ points $Q$ in a plane, so that $t(Q)$ (the number of possible triangulations) the following equation holds: $$t(Q) \ge 2^{n-2\sqrt{n}}$$ I solved the problem using the ...
1
vote
1answer
123 views

Calculate base and coefficient for power curve through 3 non-linear points

I have a formula that takes a 0-based bounded single dimensional input and transforms it to a specific power curve. EDIT This is single dimensional. There is no $y$. In the image, I'm showing how ...
1
vote
1answer
194 views

3D Convex Hull and The Gift Wrapping Principle

I am currently trying to implement a 3D convex hull algorithm that is based on the paper Convex Hulls of Finite Sets of Points in Two and Three Dimensions by F.P. Preparata and S.J. Hong, but I’ve run ...
1
vote
1answer
90 views

When is a convex polygon inscribable?

Defining the diameter of a convex polygon as the maximum possible distance between all pairs of vertices, can we conclude that the convex polygon is inscribable (i.e has all its sides as chords of a ...
1
vote
1answer
170 views

On finding the nondominated set of vectors. How to understand this algorithm?

L et us denote by $x_i(v)$ the $i$th coordinate of $v \in \mathbb{R}^d$. Then $v = \left [ x_1(v), x_2(v), \dots ,x_d(v) \right ]$ We say that a $v \in \mathbb{R}^d$ dominates another vector $w \in ...
1
vote
1answer
145 views

What is the typical method for sampling uniformly in a convex polytope

The polytope in my case is the intersection of the k-plane $Ax=b$ and $\{x>0\}$ where $A$ is the constraint matrix and $b$ is some solution. I'd like to find a method that is fast and efficient for ...
1
vote
1answer
59 views

What do we call the angular arcs between two edges of triangles?

I've been trying to find a geometry library for java which is as high level as describing angles between adjacent sides of triangles given 3 sides. So, what do we call such kind of arcs. In many ...
1
vote
1answer
124 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' ...