1
vote
2answers
82 views

Retrieve the initial cubic Bézier curve subdivided in two Bézier curves

I have a cubic Bezier curve subdivided to two cubic Bezier: Assuming that "t_cut" is the t value where this initial Bezier is cut: example of function subdivision(BezierCurve initialCurve, ...
1
vote
1answer
59 views

Merge two or more cubic Bézier curves for optimization

I am looking for an algorithm which can merge several cubic Bezier curves. For instance, I have a lot of cubic Bezier that are joined to form a poly-Bezier curve. The idea is to merge dynamically some ...
0
votes
1answer
22 views

Convex hulls for a finite amount of points

I'm trying to understand what a convex hull intuitively is, and say given for a set of points $(x,y)\in\mathbb{R}^2$ how is it generated from these points? I tried reading the wikipedia article and ...
0
votes
0answers
10 views

Maximum amount of positional offset caused by noisy distance measurements in Quadrilateration

Quadrilateration is a range-based localization technique applied to wireless sensor networks. It is the equivalent method of trilateration in 2D. Assume that, there are four beacons (the sensors ...
11
votes
3answers
157 views

is there an efficient algorithm for comparing collections of points?

Let's say you have two sets of M points $p_1...p_M$, and $q_1...q_M$, which reside in $\mathbb{R}^N$. Is there an efficient (e.g. polynomial in M and N) algorithm to determine if the point-sets are ...
1
vote
0answers
50 views

Computationnal geometry: vector, basis, point and coordinate system?

I am trying to build a small geometrical library in C++, that is mathematically consistent (not so false). The goal here is to construct two concepts: vectors and points. I am not sure that the ...
1
vote
1answer
36 views

Can convex hulls contain duplicate points?

Given 4 vertices: (-3.2, 0.8), (-3.2, -0.8), (3.2, -0.8), (3.2, 0.8) A function which I did not write, and given vertices, will return the points of a convex hull. Using the points above, it ...
2
votes
1answer
160 views

Vectors Angles from $[0,2\pi]$

Given two vectors $V_1 = (x_1, y_1)$ and $V_2 = (x_2, y_2)$. How to calculate the angles between them in the range of $[0, 2\pi]$? I know the $\cos\theta$ similarity equation could present a $\theta$ ...
0
votes
0answers
58 views

Spherical object with n vertices and no coordinate singularities

I'm programming a tool where I want to track the directions of a unit vector. I want to store the position to which the vector is pointing on a unit ball. Each time the vector points to a position $x$ ...
3
votes
1answer
99 views

Finding the angle of a moving target

I'm developing a submarine game and found a mathematical problem that exceeds my knowledge. A submarine has $x$ and $y$ coordinates in the plane, a speed $v$, and two angles: one indicates the ...
2
votes
3answers
209 views

angle between two intersected plane

If two planes are intersected by making a straight line, like $AB$ then Does the angle between two planes (see figure) always given by the angle between normal vectors ($n_1$ and $n_2$) ?
5
votes
2answers
90 views

Find the most vertical line in a point set in $O(n \log n)$ time

Input: a set of $n$ points in general position in $\mathbb{R}^2$. Output: the pair of points whose slope has the largest magnitude. Time constraint: $O(n \log n)$ or better. Please don't spoil the ...
-1
votes
1answer
78 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
vote
1answer
117 views

Fraction values around the vertices of a Loop's subdivision

In Loop's subdivision scheme, what do the variables $\alpha$ and $n$ refer to? Knowing what the variables refer to will help to derive the fractions around the vertices. But, what do these ...
5
votes
2answers
380 views

Distance between a point and a m-dimensional space in n-dimensional space ($m<n$)

I am trying to find a method with a low computational cost to compute the distance of a point $P$ and a space $S$ that is defined by the origin $O$ and $m$ vectors $v_1, v_2, ..., v_m$ in an ...
1
vote
3answers
185 views

Finding a point above the line in $O(\log n)$

I am trying to solve the following problem. So far with no success. Let $S$ be a set of $n$ points in the plane. Preprocess $S$ so that, given a (non-vertical) line $l$, one can determine whether ...
1
vote
1answer
191 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 ...
8
votes
1answer
3k views

Calculating Distance of a Point from an Ellipse Border

I'm thinking about using oriented ellipses to represent curves (dents/bumps etc.) in my physics engine, and have a few questions about working with them: What methods are there to finding the ...
0
votes
0answers
61 views

Multidimensional simplex meshing

I'm trying to figure how to make a simplex mesh on orthogonal domain. Basically it comes to this: Make (2) triangles of a rectangle Make (5) tetrahedrons of orthogonal prism (cuboid) etc. I don't ...
4
votes
1answer
70 views

Efficiently deciding if any of a set of cylinders in 3-space intersect

Let's say I have a set $C$ of $N$ cylinders in 3-space, $(c_1, ..., c_N) \in C$, where each cylinder, $c_i$, has an associated radius $r_i$ and two coordinates specifying the endpoints of the line ...
1
vote
1answer
181 views

Characterizing and counting the unique vertices in a geodesic sphere based on a triangulated icosahedron

I have a geodesic sphere generated by triangulated an icosahedron to some frequency $\nu$, with a circumscribing sphere of radius $R_c$. Let's define a 'component' of the geodesic sphere to be a ...
1
vote
1answer
389 views

Deforming a truncated icosahedron into its circumscribing sphere

Imagine that I have a truncated icosahedron consisted of 60 vertices, each of degree $deg(v) = 3$, and fixed edge length $L$. I'd like to assign some constant curvature or bending angle $\theta$ to ...
1
vote
1answer
319 views

why does multiplicatively weighted voronoi diagram (mwvd) with 2 sites create a circle?

I want to understand the structure of a multiplicatively weighted voronoi diagram. I found that the bisector between 2 sites is circle shaped, but couldn't formally ...
3
votes
2answers
286 views

How to get 'rectangular size' of arbitrary circular sector?

Given a circular sector defined by sweeping from a 'start' to a 'stop' angle (see diagram below) and a radius, how do you compute the bounds of the rectangle that fits to the edges of the sector? ...
1
vote
2answers
413 views

shadow simulation from buildings

is it possible to calculate shadow areas of buildings or simulate shadows of buildings in a city, using the heights of these buildings and the sun angle and azimuth? the basic light tracing concept ...
1
vote
1answer
101 views

Problem interpretation - Distance Formula?

If you've got multiple arrays like this: (24,36,28,28,16,27) (38,38,45,57,35,50) every array being 6 integers, each integer in range [0,60] I would like to find the distance between those 2 ...
1
vote
1answer
125 views

What is computational geometry and who should take a course on this subject? [closed]

In mathematics, geometry is the topic I like. Just out of curiosity I would like to know what computational geometry is about. Who studies this subject and why. What are its applications, or is it ...