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

learn more… | top users | synonyms

3
votes
4answers
79 views

Plane constraints in R3

I have multiple plane constraints in $\mathbb{R}^3$ of the form: $$n_i \cdot x \ge \delta_i$$ Where $n_i$ is the $i$th plane normal (in form (x, y, z)), $x$ is a point in space, and $\delta_i$ is ...
0
votes
1answer
50 views

How to model waterflow when only a couple of sample points available

Figure below depicts a cross section of a creek for which I am trying to measure the water flow for that section. What we have as inputs are a bunch of sample points on the river. For each sample ...
2
votes
1answer
72 views

Best incremental multidimensional Delaunay tessellation algorithm

I'm looking for a specific type of Delaunay tessellation algorithm. The algorithm should be: incremental so that I can add new sites inside known simplexes (i.e. no searching for the right simplex ...
5
votes
1answer
90 views

Finding closed equipotential surfaces on a 3D grid

In short, I'm looking for either: (1) Publications or other sources dealing with contour/isosurface finding algorithms, so that I can write my own implementation (and parallelize as best I can), or ...
2
votes
1answer
49 views

The closed form solution of a point on a plane

Given a plane in 3D Euclidean space is $\pi$: $ax+by+cz+d=0$ and a point $P$:$(X,Y,Z)\in \mathbb{R}^3$. Find a point $Q:(X^*,Y^*,Z^*)\in \pi$ such that: $$Q= ...
3
votes
1answer
35 views

Extract 3D lower hull from convex hull

For my problem I need to extract the lower convex hull of a set of 3D points (X,Y,Z). In Matlab, one can find the convex hull using the convhull function as follows: K = convhull(X,Y,Z). Could ...
3
votes
0answers
25 views

Auto labeling algorithm

I have a set of points (2D space), and for every point there's a label (like city names on a map). I want to find a real-time algorithm that allows labels to avoid overlapping, moving them from their ...
2
votes
2answers
64 views

How can I generate shell elements to a mesh

I have a program that generates mesh for given 3d models. The generated mesh must use quadrangle elements. It is required to add "shell elements generation capabilities". The requirement is as ...
3
votes
1answer
54 views

how to do geometry clean up in paraview? [closed]

I have a vtk file which has a bunch of points, I would like to delete a few points because, those distort my geometry (basic geometry clean up), is there a way I can do it in paraview? I just want to ...
0
votes
0answers
43 views

Creating ruled surfaces bounded by Bsplines and how to obtain intersections

I'm just learning gmsh from the tutorial, and I have some questions regarding gmsh geometry design, I have two Bsplines with common start and end points that are not coplanar to each other. A ruled ...
1
vote
1answer
51 views

Inclined plate capacitor grid/ mesh

You can calculate the electric potential over every point in a defined space by solving Laplace's equation. To do this in a computer program you set up an 2-d array/ matrix and loop the internal ...
0
votes
1answer
418 views

Vertical and horizontal segments intersection (Line Sweep)

Introduction: I have a vertical segment S That i want to move across a plane (Left --> Right), and find intersections with horizontal lines. Problem : The problem which i am having is the ...
0
votes
1answer
90 views

Line segment straddle

What is exactly the definition of "Straddle"? Can you please explain what do they mean exactly or a sketch? A segment P1P2 Straddles a line if point P1 lies on the one side of the line and point P2 ...
0
votes
0answers
36 views

How can i find the coordination number with voro++?

Could anybody please help with voro++ cause i am new to this software?My problem is how can i find the coordination number of an atom ,cause i checked it for a bcc lattice and it gave me 24 for all ...
5
votes
4answers
157 views

Computational science contests. Why arent there any?

I was wondering why there are no online or offline computational science contests? At least I couldn't find much by googling. I mean, like a topcoder for computational sciences. I assume one reason is ...
1
vote
1answer
55 views

Equal Area Sampling on Curved Surface:

I have a quantity $\beta(\mathbf{x}) \in \mathbb{R}$ that I wish to compute on a curved, smooth surface defined by $\{\mathbf{x}: \Gamma(\mathbf{x})=0\} \subset \mathbb{R}^{3}$. (This surface is ...
1
vote
0answers
52 views

Environment for implementing/testing Computer Graphics algorithms [closed]

I need to code up a computer graphics algorithm for Surface Registration. Briefly surface registration is the process of finding "optimal" one-one correspondence between surfaces, where the meaning ...
5
votes
3answers
305 views

Volume of 3D convex hull of small point sets all on the hull

I have a question that is similar to this one asked before except in 3D, and I only need the volume, not the actual shape of the hull. More precisely, I'm given a small set of points (say, 10-15) in ...
1
vote
0answers
121 views

MATLAB Detection of the point where regions meet

A totally beginner here. I've read all the coordinates of nodes of a face from the corresponding file into an [X Y Z] array and displayed as a mesh. The top-most node of the nose i.e. the tip of the ...
9
votes
3answers
198 views

N-dimensional Delaunay Tesselation Software Libraries

I have a set of known points/nodes irregularly spaced in N-Dimensional space (N>=2), and I would like a way to generate the Delaunay triangulation of these points, and return the corresponding ...
2
votes
1answer
198 views

Fast nearest neighbor search, Latitude Longitude

Is there a fast nearest neighbor search algorithm that generates the nearest neighbors, not based on Euclidean distances but based on geographic distances over a set of latitudes/longitudes. The fast ...
3
votes
1answer
241 views

Minimal surface solution in Python

Note: this question was also posted in StackOverflow and math.stackexchange. I have a set of 3D points defining a 3D contour, as shown below. The points in this contour lie in their best-fit plane ...
3
votes
1answer
135 views

Compute spatial second derivatives in Isogeometric analysis

Motivation: In isogeometric analysis, state variables(e.g. displacement) are defined in the parametric domain, which can be mapped to the physical domain by $\boldsymbol{\xi}\mapsto \boldsymbol{x}$ ...
4
votes
1answer
60 views

Fastest method for evaluating the limit of the sign of a polynomial

Consider a multivariate polynomial $f(x) = f(x_1, \ldots, x_n)$ with maximum degree $d$. Following the linear symbolic perturbation scheme described in Seidel 1998, I want to evaluate the limit ...
4
votes
2answers
74 views

Library for closest point on a polyhedron

I need to compute a closest point on a nonconvex polyhedron to a given point in 3D space. I need a simple algorithm or library. I search in CGAL but did not find a suitable function and the package is ...
5
votes
3answers
164 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
51 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
198 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
94 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
162 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
53 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
39 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
53 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
129 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 ...
5
votes
1answer
136 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
120 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
2k 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 ...
1
vote
1answer
96 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 ...
8
votes
2answers
203 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 ...
4
votes
1answer
153 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 $$ ...
5
votes
3answers
115 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 ...
2
votes
2answers
77 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
88 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 ...
9
votes
3answers
964 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
79 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
224 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.$$ ...
5
votes
1answer
1k 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 ...
22
votes
4answers
3k 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
162 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
210 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 ...