Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [computational-geometry]

The study of efficient algorithms and data structures to solve various problems involving point sets, line segments, polygons, polyhedra, simplices, etc.

5
votes
3answers
273 views

Closest interior point on integer grid to a vertex of a convex polyhedron

I have a 3 dimensional convex polyhedron whose vertex coordinates are rational. For one of these vertices, I would like to find the nearest integer grid point (under the Euclidean metric) that is ...
3
votes
0answers
88 views

Dissipation and symplectic manifolds

I'm working on an API for simulation of port-Hamiltonian systems. As far as I understand it, a Hamiltonian system is symplectic if it is power conserving, and so including resistive elements would ...
8
votes
1answer
989 views

How to calculate the area of intersection between a 3D volume and a 2D plane

Hello if anyone can offer insight on how to solve my problem that would be great! I am looking to calculate the area of intersection between a 3D volume and a 2D plane. 3D volume: defined by 6 points ...
3
votes
1answer
130 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 ...
4
votes
3answers
455 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
votes
0answers
100 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 ...
2
votes
1answer
44 views

Error in Maple's CellDecomposition Command

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 ...
3
votes
0answers
77 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, ...
5
votes
2answers
193 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 ...
6
votes
1answer
303 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 ...
2
votes
1answer
185 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$ ...
6
votes
1answer
11k 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 ...
2
votes
1answer
288 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 ...
9
votes
2answers
816 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 ...
5
votes
1answer
738 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=...
6
votes
3answers
134 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 ...
4
votes
2answers
174 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 ...
2
votes
2answers
111 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-...
16
votes
3answers
4k 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 ...
1
vote
0answers
96 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 ...
3
votes
1answer
947 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.$$ ...
6
votes
1answer
3k 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 ...
25
votes
5answers
15k 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 ...
7
votes
3answers
211 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 ...
11
votes
4answers
310 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 ...
1
vote
3answers
242 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 (...
3
votes
1answer
67 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 ...
8
votes
5answers
654 views

Some good reading on polygon algorithms

What are some good resources (books, articles, sites) about polygon intersection and union algorithms?
4
votes
0answers
382 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$, ...
11
votes
1answer
1k 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 ...
9
votes
1answer
252 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 ...
6
votes
2answers
869 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 ...
6
votes
2answers
1k 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 ...
7
votes
1answer
2k 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 ...
9
votes
5answers
5k 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 ...
5
votes
1answer
301 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 ...
18
votes
2answers
4k 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)