The study of efficient algorithms and data structures to solve various problems involving point sets, line segments, polygons, polyhedra, simplices, etc.
1
vote
2answers
97 views
Uniform dots distribution in a sphere
I'm trying to implement Barnes-Hut algorithm, with a binary tree. My initial conditions are a uniform mass distribution in a sphere with radius $R$. How can I create uniform dots distribution in a ...
2
votes
1answer
110 views
Can the Power Method be used here?
Given a set of $n$ points on which a triangulation is performed, it is possible to construct coefficients $\lambda_{ij}>0$ such that each point $x_i$ is a convex combination of the points connected ...
2
votes
0answers
58 views
Simultaneous update to barycenters
Suppose a tiling is given in 2D (an embedding of a planar triangulated graph), with all faces convex.
Now suppose one moves each point, one by one, to the barycenter of its neighbors. I think that ...
4
votes
0answers
73 views
What Derivative-free optimization method should I use when my initial guess is very good?
I am trying to minimize a function where my initial guess is quite close to the minimum.
I'm trying to minimize
$$f(q) = \text{angle}(qw_1q*, v_1) + \text{angle}(qw_2q*, v_2) + \text{angle}(qw_3q*, ...
4
votes
2answers
432 views
3D contour mesh computation
I have the value of a function in three dimensions, $f(x, y, z)$, which varies smoothly.
I would like to compute a 3D mesh where $f(x, y, z)$ has a particular value.
Are there algorithms to do this? ...
5
votes
1answer
127 views
Integrating/Implementing NURBS-related calculations
Recently, I started to develop some codes that use NURBS (general things I intend to use/already using: spline generation, interpolation, grids, isolines, closest-point find, and many others), both ...
2
votes
1answer
52 views
Polygon approximation with a circle
There is an article describing how to detect a pupil from an eye photo.
A.-H. Javadi, Z. Hakimi, M. Barati, V. Walsh, and L. Tcheang, "SET: a pupil detection method using sinusoidal approximation," ...
3
votes
0answers
61 views
Fast Algorithms for the Simplicial Decomposition of a Convex Polytope in N-Dimensions
I'm in the process of constructing an algorithm which computes the Voronoi diagram of a set of points, but I now need a method to decompose each Voronoi cell into simplices. The information we have is:...
1
vote
0answers
42 views
Efficient initial identification of solid or liquid domains for a block structured Cartesian grid generation system
INTRO
Within the last 5 days I was able to generate a block structured Cartesian grid
generation system with a combination of Fortran,C++ and Python.
I am running intersection tests of the ...
0
votes
0answers
30 views
Free Form Deformation Library
I am looking for an Open Source Free Form Deformation library to morph / deform existing geometries given as a set of points (vertices of cells).
I came across PyGeM (python) and
mimmo (C++).
I ...
0
votes
1answer
91 views
Which free library should I use to perform cutting/clipping operation?
I have a set of points which forms a closed loop, and I want to perform cutting/clipping a 3D model using this loop. I have used VTK but in some cases, it has a "Cannot follow edges" problem.
Is ...
0
votes
1answer
49 views
Gmsh exporting wrong mesh DATA [closed]
so hopefully I'll be using gmsh to make meshes out of 2-D cross sections with o thickness. I tried to make a structured mesh with quad elements of a rectangular ...
4
votes
1answer
111 views
Expanding Winding Number algorithm to arcs
I have a problem that I have been attempting to solve for a few days now. I was wondering if I would be able to get some assistance from the community.
In order to detect if a point is in a polygon, ...
3
votes
1answer
65 views
Compute mesh of the projection of a 3D surface triangulation
Given a triangulated surface in $\Bbb{R}^3$ we can simply project it on a plane. This will result in a family of triangles which do not form a mesh of the projection for the following reasons:
each ...
6
votes
2answers
487 views
Efficiently finding all (x,y,z) points within certain distance of point P
I am using Python, and I have a Pandas dataframe with hundreds of thousands, if not millions, of $(x,y,z)$ coordinates. I am looking to find an efficient method to index the original dataframe so that ...
0
votes
1answer
52 views
Detect all “visible” points on a triangulated surface
I have a triangulated surface that I want to work with. In order to optimize certain quantities related to this surface I want to find all points which are accessible from a given direction. To be ...
2
votes
2answers
108 views
Algorithm to construct all distances of a system described by $3N-6$ distances
A non-linear molecule has $3N-6$ degrees of freedom ($N$ is the number of atoms; ignoring translation and rotation). Therefore, a set of $3N-6$ distances and/or angles is enough, to describe the whole ...
4
votes
1answer
76 views
Delaunay triangulation for datasets with four or more co-circular points
I am working on a library that requires subdivision of polygons into triangles. The polygons are divided into triangles by (more or less) random points that are inside them. In general, the approach ...
2
votes
2answers
96 views
Find connected circles
I have a problem as follows:
We have a set of circles (we know the radius r and the center point c in Rd of each circle)
We ...
7
votes
2answers
136 views
Generating set of points on a surface defined by constraint
I'm writing a differential geometry library, and one minor convenience I'd like to offer is to generate a set of points on a surface given by a constraint. For example, for a sphere,
$$x^2+y^2+z^2-r^...
0
votes
1answer
63 views
Linear Least-Squares Point-to-Plane ICP degenerative case
I'm trying to implement Linear Least-Squares Optimization for Point-to-Plane ICP Surface Registration
Paper describes linear approximation for point to plane distance for rigid ICP. This approach is ...
0
votes
3answers
45 views
Is it valid to assume the center of a bounding sphere to be also the center of the bounding box?
Computing an axis aligned bounding box of a point set is trivial. Computing a bounding sphere of a point set is also trivial when the center is known. Computing the center of the bounding sphere is ...
3
votes
4answers
221 views
find grid points inside the parallelogram defined by an origin and two vectors
I hope someone knows an efficient computational approach to the following 2D problem:
Given two vectors $\mathbf{A}$ and $\mathbf{B}$, find all grid points that lie within the parallelogram spanned ...
6
votes
4answers
711 views
Generate a set of orthogonal vectors to a given vector
I am looking for an alternative and robust alternative to Gram-Schmidt orthogonalization, but with one constraint:
I have a unit vector $\mathbf{v}_1 \in \mathbb{R}^d \,\text{s.t.} \,\|\mathbf{v}_1^T\...
1
vote
2answers
100 views
Sign of integer determinant 4 by 4
I'm in the context of this publication: http://www.gilbertbernstein.com/resources/booleans2009.pdf
I applied quantization to my point coordinates: All coordinates are integer lying in [0, 2 power 20]....
1
vote
1answer
44 views
Sources for verified Voronoi and power diagrams
In the course of trying to implement algorithms for Voronoi and Laguerre diagrams, I realized I needed to verify if my implementation is working correctly using a point (or circle) configuration with ...
0
votes
1answer
203 views
Algorithms to extract trajectory lines out of 3D point clouds
I am looking for different approaches to extract 3D polylines out of Point Clouds.
We are able to create these point clouds out of different data sources of real world surveys (LIDAR, RADAR, etc...) ...
0
votes
1answer
66 views
What is the expected value of area of intersection of a circle and a rectangle
$r$: cicle C1's radius
$w$,$h$: rectangle R1's edges: $x=w$, $y=h$, $x=0$, $y=0$
$(w>2r, h>2r)$
$S(x,y)$: area of ...
1
vote
0answers
32 views
Algorithms for computing winding numbers of 2-sphere maps
I have a question concerning computational geometry which arises in the simulation of fields with topological defects, and I'd like to know whether there's an efficient algorithm (or any algorithm) to ...
0
votes
1answer
54 views
Optimally “morph” one set of points into another
Given two sets of (two-dimensional) points, say, $A=\{a_1,a_2,\ldots,a_{n_a}\}$ and (you guessed it) $B=\{b_1,b_2,\ldots,b_{n_b}\}$, and $d^2_{i,j}=\mid a_i-b_j\mid^{\ 2}$ the "matrix" (not ...
0
votes
1answer
52 views
Efficient search strategy in a monotonic boolean function wherein the probability of solution location is known apriori
A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$.
$$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in ...
1
vote
1answer
63 views
Distirbution of Points along a Line
I am facing the following problem:
Given is a line of length $L$ which I want to split into $N$ segments. The lengths of the first $(s_1)$ and last segment $(s_N)$ are given.
You can assume that the ...
1
vote
0answers
25 views
Use custom defined metric(not matrix) in Javaplex
I'm about to get started trying to use Javaplex for the first time for some application in topological data analysis (TDA) and I want to use a custom defined metric. From looking over the documents, I ...
0
votes
1answer
99 views
From edge-vertex connectivty to face-vertex connectivity?
I am working on mesh generation and optimization and encountered this problem. For example, in the figure below, we have the edge-vertex connectivity:
0-1
1-4
4-5
2-5
3-2
0-3
1-2
1-6
7-6
4-7
...
1
vote
1answer
95 views
Efficiently determine whether a curve intersects a given rectangle?
Suppose we have a straight line in Cartesian space such that
$$ x_k = x_0 + k \delta x, \quad \quad y_k = y_0 + k \delta y, \quad \quad z_k = z_0 + k \delta z $$
where $k$ can take any real value. If ...
1
vote
1answer
75 views
Why rational numbers in the Lenstra–Lenstra–Lovász algorithm?
The Lenstra–Lenstra–Lovász (LLL) algorithm is a famous one for lattice reduction. But concerning its application, I am always baffled by one point.
The algorithm applies equally well to irrational ...
2
votes
0answers
54 views
How to model pedestrian flow through subway systems?
I'm a New Yorker and take the subways every day. I have a growing interest in understanding the distribution of paths people take on the subways to work every day.
I.e. if there are $n$ subway ...
10
votes
2answers
276 views
Fitting Implicit Surfaces to Oriented Point Sets
I have a question regarding quadric fit to a set of points and corresponding normals (or equivalently, tangents). Fitting quadric surfaces to point data is well explored. Some works are as follows:
...
3
votes
2answers
224 views
How do I find the smallest set of elements that covers a given shape?
Suppose I have a mesh consisting of a set $M$ of conformal elements that fill the region $R=[0,1]\times[0,1]$. Suppose that I also have a 2D shape $S\subset R$ whose boundary $\partial S$ is ...
1
vote
0answers
36 views
Closed-form Jacobian of se3 element w.r.t. 6-dof motion
Let $A$ and $B$ be two rigid transformations in 3D space that transform things from global to local coordinates.
Let their relative transformation be expressed by $W=A*B^{-1}$.
$W$ can also be ...
4
votes
1answer
441 views
Finding Shape Functions for a Triangle in 3D coordinate space
I have a Triangular Plane T given by three points in 3D space $$P_1 = (x_1,y_1,z_1)\\ P_2 = (x_2,y_2,z_2) \\ P_3 = (x_3,y_3,z_3)$$
I want to find the Shape Functions on this plane as $N_1(x,y,z),N_2(...
0
votes
1answer
156 views
Min supporting line for a set of points
I'm trying to solve exercises of the book "Computational Geometry in C" by O'Rourke. Could you please help me with this one?
Design an algorithm to find a line $L$ that:
has all the points ...
2
votes
3answers
556 views
Fit best polygon to a discrete contour
I have a discrete contour represented by a set of points. The contour looks like a polygon but if you zoom you see that the edges are rugged (that's because it was obtained while working on a finite ...
0
votes
1answer
64 views
Loooking for name of this geometrical optimization technique
From my knowledge if you fit geometrical objects into point clouds you want in general minimize the squared distances of the point cloud to your fitted objects. I do so with the downhill simplex ...
1
vote
1answer
96 views
What is a good algorithm, and framework, to calculate centres of gravity or mass (cog)?
I'd like to take an photograph, subdivide it into a tesselation, either of squares, or (ideally), hexagons, and then find the centre of gravity (or, if you prefer, centre of mass) of each cell of the ...
1
vote
0answers
29 views
Find alternative path closest to original
I have a set of points in a 2D space. I want to connect the outer points so I get the convex hull. The problem here is that there is a limit to the distance between two points. Let me clarify that ...
0
votes
1answer
32 views
Parametrization of distorted and dented ellipsoids
My program uses a lot of ellipsoid shaped polygons in 2 and 3 D. So far, I create them by the simple, well-known parametrization about two angles.
Now I'd like to have my ellipses a bit dented and ...
1
vote
0answers
51 views
Mesh partitioner with user-defined overlap
I am looking for a mesh partitioner, where I can specify overlap, for example h = 3.
I have looked into metis, but I wasn't able to find such a functionality.
Is there any other package which ...
3
votes
1answer
403 views
Library for polygon processing in 3D
I need to process some polygons in 3D. They are typically loaded from an OFF or STL file. Then I need to do some transformations (rotation, move, resize), I'd like to check whether points are inside ...
0
votes
1answer
170 views
Heat Equation in 3D mass Matrix set-up
I am solving a 3D heat transfer equation with variable boundaries (insulated, convective, radiative or free) using a F.D.M. technique. My geometry of choice is a cube. The purpose of my work is to get ...
