All Questions
334 questions
3
votes
1
answer
177
views
How to treat hexahedral element with shifted hanging node?
When using the Hexpress grid generator one gets hexahedral cells, possibly with hanging nodes. Because of a smoothing step, the hanging nodes can be shifted: they are not necessarily on the straight ...
- 1,045
4
votes
3
answers
875
views
Backward stable projection and normalization of a vector
Given a machine precision unit vector $n$, and an arbitrary vector $v$, I want an unconditionally backward stable method to compute
$$f(v) = \frac{v-nn'v}{\left|v-nn'v\right|}$$
In other words, ...
- 3,969
3
votes
0
answers
115
views
exact area resampling [closed]
I do image processing, and right now I need to resample some images taken from slightly different perspectives so I can match up features. The pixel intensities have scientific significance, so I want ...
- 131
1
vote
1
answer
60
views
Error in Maple's CellDecomposition Command [closed]
I have a simple system that I want to process with the CellDecomposition command of Maple. I don't know why Maple is giving an error here! The code is
...
- 19
3
votes
0
answers
88
views
Conservative field mapping between two topologically disconnected surface meshes
Some background: the Front-Tracking method uses a triangular surface mesh to describe the boundary between two immiscible fluids. To deal with the breakup and coalescence of the fluid interface, ...
- 1,916
5
votes
2
answers
238
views
Restrict Voronoï diagram to a polygon
I managed to build the Voronoï diagram of n points using Fortune's algorithm.
This gives me a set of half-edges, some of which being infinite (no starting point and/or no end point).
I'd like to ...
- 151
6
votes
1
answer
406
views
Ray casting algorithm for multiple disjoint polygons is still valid?
We're dealing with country borders, that is the set of multiple disjoint domains that is made of polygons.
To extract the different point on the map by a given country we've been said to implement ...
- 161
2
votes
1
answer
216
views
Recovering coordinates by eigendecomposition without double-centering
Suppose an Euclidean distance $D\in\mathbb{R}^{n\times n}$ matrix between a set of $n$ objects is given. To obtain inner-products (which will be further be used to recover coordinates), entries of $D$ ...
- 1,703
6
votes
1
answer
12k
views
Concave polygon 'hull' finding
I implemented an algorithm to find the alpha shape of a set of points. The alpha shape is a concave hull for a set of points, whose shape depends on a parameter alpha deciding which points make up the ...
- 343
3
votes
1
answer
304
views
Random placement of euclidean points with constrained inter-point distances in a fixed area
I'd like to place as many random points as possible in a 2D square $S=[0,1]x[0,1]$ such that the euclidean distance $d$ between any two points $d$ is greater than a given value $b$ (b is small). I'm ...
- 12.2k
10
votes
2
answers
2k
views
Is there an algorithm to find an almost-convex hull given a tolerance angle?
I'd like to know if there is an algorithm that given a set o points and an angle computes the convex-hull if the angle is $\alpha = 0$ and given an $\alpha > 0$ computes an envelope that follows ...
- 203
5
votes
1
answer
1k
views
Convex polytope volume and centroid calculation
I have troubles imagining how to compute a volume and centroid of an n-dimesional convex polytope.
For a polygon (especially for convex polygon) the area and centroid are described in (wiki) by
$$
A=...
- 151
6
votes
3
answers
147
views
How can I detect which among N bodies with different velocities will collide?
Suppose I have N different airplanes traveling on a two dimensional rectangular plane of size 400km x 400km (i.e. it is as if all planes travel at the same altitude). Assume each airplane has a ...
- 12.2k
5
votes
2
answers
279
views
Is there a special algorithm for computing the convex hull ordering when the candidate points are on the hull?
I'm dealing with a set of points which are already placed on the 2D hull boundary: a convex polygon. I know this for sure. However, the point set is not ordered, and I need the polygon points to be ...
- 1,916
2
votes
2
answers
143
views
A sufficient number of distances to recover relative positions of n points
On several places I found different claims on a sufficient number of distances to recover relative positions of $n$ points in $d$-dimensional space.
For instance, work from
http://www.dimitris-...
- 1,703
15
votes
3
answers
6k
views
Finding which triangles points are in
Suppose I have a 2D mesh consisting of nonoverlapping triangles $\{T_k\}_{k=1}^N$, and a set of points $\{p_i\}_{i=1}^M \subset \cup_{k=1}^N T_K$. What is the best way to determine which triangle each ...
- 3,225
1
vote
0
answers
106
views
Anisotropic cover with n-cuboids
I'm working on an algorithm for which I would like to cover an $n$-dimensional unit cube by a set of $n$-cuboids (i.e., $n$-dimensional rectangles). The size and orientation of these cuboids is ...
- 590
3
votes
1
answer
2k
views
Application of an orthogonal matrix to a 3D configuration of point
Suppose a 3D configuration of points is given, $X\in\mathbb{R}^{n\times 3}$, and a matrix $Q\in\mathbb{3\times 2}$, with orthonormal columns. Now, suppose a mapping to 2D is obtained as
$$Y=XQ.$$ ...
- 1,703
8
votes
2
answers
5k
views
How to get all intersections between two simple polygons in O(n+k)
Basically the formulation of the problem I'd like to solve is very simple. Given 2 simple polygons (without self-intersections) report all intersecting edge pairs in O(n+k) time, where n - is a total ...
29
votes
5
answers
21k
views
Fastest Delaunay triangulation libraries for sets of 3D points
Which is the fastest library for performing delaunay triangulation of sets with millions if 3D points? Are there also GPU versions available? From the other side, having the voronoi tessellation of ...
- 711
7
votes
3
answers
262
views
Converting from planar polynomial domain to planar polygon
Let's assume we have a planar domain whose boundary can be described with a polynomial curve (like Bezier curves).
Now assume that you want to produce a discretization of the boundary, i.e. you want ...
- 233
14
votes
4
answers
378
views
How to create a random 3D domain representing a plant's root structure?
I would like to model laminar flow of water from roots to the stem of a plant. At the very end of the roots, the tubes vary from millimeter to centimeter scale in diameter and length. As we get closer ...
- 141
1
vote
3
answers
296
views
Unique coordinates (solutions) in a single Gauss-Seidel iteration
I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$ are weighted Laplacian matrices (...
- 1,703
3
votes
1
answer
78
views
2D Jacobi line maintenance?
Suppose a linear system is given
$$AX=B,$$
where $A\in\mathbb{R}^{n\times n}$ is a symmetric strictly diagonal matrix, and $X, B\in\mathbb{R}^{n\times 2}$. Therefore, the 2D Jacobi iterative solver is ...
- 1,703
8
votes
5
answers
1k
views
Some good reading on polygon algorithms
What are some good resources (books, articles, sites) about polygon intersection and union algorithms?
- 81
5
votes
0
answers
476
views
Why is my lower convex hull extraction algorithm not working?
Recently, I wrote an algorithm to obtain a delaunay triangulation of a random point set in $I=[-10,10]$x$[-10,10] \subset R^2$ by projecting these points onto the 3 dimensional paraboloid $z=x^2+y^2$, ...
- 12.2k
12
votes
1
answer
2k
views
Sort a cloud of points with respect to an unstructured mesh of hexahedral cells
Question
How would you sort a cloud of points with respect to an unstructured mesh of hexahedral cells?
Each cell has a centre and a unique label to represent it. There are two cloud points ...
- 1,916
9
votes
1
answer
376
views
Given values on a mesh, what algorithm can I use to construct efficiently level set contours?
I have a mesh, faces $F$, edges $E$, and vertices $V$, and I have a list of predefined level set contours.
What algorithm can I use to construct contours in the most efficient manner?
A plot of the ...
- 478
6
votes
2
answers
1k
views
Is there any 2D shape repository?
As far as I see, there are many repositories for 3D shapes. But in FEM and many other applications, a planar mesh domain is also very common. However, I did not find a mesh repository specially ...
- 115
8
votes
2
answers
2k
views
Shape regularity in higher dimensions
In Finite Element theory, and other methods in scientific computing for PDEs, one uses meshes which fulfill several regularity criteria, many of them being equivalent.
It is of interest to have ...
- 3,720
8
votes
1
answer
4k
views
How to efficiently determine the intersection of a vertical cutting plane with a mesh
I have a list of vertical cut planes, and I have a polygonal mesh ( it's a 2D+0.5D mesh, something like a 2D mesh with an extra dimension, $z$ attached to each point). One can assume that the mesh ...
- 478
10
votes
5
answers
7k
views
How are the Voronoi Tesselation and Delaunay triangulation problems duals of each other?
I have always been told that the Voronoi diagram is the dual of the Delaunay triangulation problem. In what sense can they be duals of each other? I thought that dual problems (i.e. in linear ...
- 12.2k
6
votes
1
answer
407
views
What efficient algorithms are there to generate arbitrary dimensional meshes of simplices?
I know that delaunay triangulation can be extended into arbitrary dimensions by solving the convex hull problem in $(p+1)$ dimensions and projecting the lower hull into dimension $p$ to obtain a mesh ...
- 12.2k
20
votes
2
answers
6k
views
Unstructured quad mesh-generation?
What is the best (scalability and efficiency) algorithms for generating unstructured quad meshes in 2D?
Where can I find a good unstructured quad mesh-generator? (open-source preferred)
- 3,226