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
711 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
610 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
205 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
108 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
62 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
132 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
114 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
93 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
69 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
635 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
2answers
68 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
178 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
373 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
147 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
317 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
92 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
171 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
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
81 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
203 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
409 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
2answers
37 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
214 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
55 views

T-shaped polygons

Is there any coefficient that can indicate T-shaped polygons ? Examples of T-shaped polygons:
1
vote
1answer
21 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
112 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
143 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
75 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
159 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
113 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
52 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
112 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' ...
1
vote
1answer
90 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 ...
1
vote
1answer
266 views

Hausdorff Distance Between Convex Polygons

I'm interested in calculating the Hausdorff Distance between 2 polygons (specifically quadrilaterals which are almost rectangles) defined by their vertices. They may overlap. Recall $d_H(A,B) = ...
1
vote
1answer
79 views

How to find out the control function of a cosine wave with sinusoidal input?

I have a system which is sampling at 100Hz. my input is sinusodial. The output is similar to cosine waveforms with varying frequency. I have no clue how to find out the exact formula to put into the ...
1
vote
1answer
65 views

Polygon: Internal Rays

Suppose I have an arbitrary non-self-intersecting polygon. I want to generate a list of points which lie on the edges of this polygon according to the following procedure: I iterate over each edge ...
1
vote
1answer
184 views

Testing polygon monotonicity

I am looking for an idea of an algorithm for the following problem: Give an efficient algorithm to determine whether a polygon P with n vertices is monotone with respect to some line, not ...
1
vote
1answer
146 views

Algorithm for Triangulation Dual Tree

I am looking for algorithm for the following problem. Given a list of diagonals of a polygon forming a triangulation, with each diagonal specified by counterclockwise indices of the endpoints, ...
1
vote
1answer
73 views

Determine if two polyhedrals are the same shape and if so, map their vertices

I have a polyhedron and want to determine whether it is combinatorially equivalent to another polyhedron. I know how many faces comprise each polyhedron and for each face, I know all of its vertices, ...
1
vote
1answer
195 views

Computing surface normal, floating point arithmetic

If I have a $n$-gon in $\mathbb{R^3}$, and I want to compute the surface normal, how can I get a value that minimizes error in a floating-point system? For example: Would I gain accuracy by first ...
1
vote
1answer
207 views

Ancient astronomers, planetary conjunctions, and epicycles

How did ancient astronomers predict planetary conjunctions? I know they used a system of epicycles to represent the path of planets, but finding the point and time of alignment of two planets still ...
1
vote
2answers
916 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 ...
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
229 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 ...
1
vote
1answer
219 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?
1
vote
1answer
501 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 ...
1
vote
2answers
211 views

Calculating probabilities on a spherical map

A black and white colored sphere is given. We are looking at a random starting point on the sphere below us, which has a certain color. A random rotation can change the color of the spot below us. ...
1
vote
0answers
25 views

Find 3D concave hull based on original model and convex hull

I want to find the concave hull of a 3d model, with a threshold for the maximum edge size. Googling around let me to the following approach (mainly abstracting from 2d approaches): Determine the ...