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.

Filter by
Sorted by
Tagged with
10
votes
3answers
2k 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 ...
29
votes
16answers
9k views

Good examples of “two is easy, three is hard” in computational sciences

I recently encountered a formulation of the meta-phenomenon: "two is easy, three is hard" (phrased this way by Federico Poloni), which can be described, as follows: When a certain problem is ...
0
votes
0answers
27 views

Dividing Point Cloud into voxels

I am reading a paper on implementing convolution neural network for a 3D point cloud. In this paper, they are dividing the point cloud into voxels. Is there any easy way to do it using point cloud ...
2
votes
0answers
29 views

Check if two points are symmetrics/asymmetrics

I am working on an Android app which lets a group of children draw whatever they want in a specific area. I need to check if the lines and figure that they draw are symmetric. The problem is that ...
2
votes
0answers
43 views

Efficient algorithm to determine the intersection volume of simple convex polyhedra

TLDR: Is there an efficient algorithm to compute the intersection of polyhedra with 8 or fewer vertices? I have two sets of FEM meshes for one geometry (one exhibiting a skin effect). I have to ...
2
votes
0answers
33 views

Algorithm to join hexahedra and obtain outline volume

I would like to join several hexahedra and obtain an outline volume. First, I started with 2D implementation. In 2D, there are non-intersecting quadrangles which always touch each other as shown in ...
0
votes
0answers
63 views

How to read data from simply formatted text file (c++)?

Mesh information like points, faces and cells is to be stored into separate files: e.g. for points file: # points data: x y z N_Points 100 x1 y1 z1 x2 y2 z2 ... cell file: # cells data: ...
9
votes
1answer
466 views

How to sample points in hyperbolic space?

Hyperbolic space in the Poincaré upper half space model looks like ordinary $\Bbb R^n$ but with the notion of angle and distance distorted in a relatively simple way. In Euclidean space I can sample a ...
6
votes
2answers
945 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(...
13
votes
4answers
325 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 ...
3
votes
1answer
294 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 ...
1
vote
2answers
364 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 ...
3
votes
1answer
202 views

Smallest circumscribed circle in spherical geometry

I work in Python 3 on astrophysics projects. I need to compute the smallest circumscribed circle of a set of points in the sky (so described by Right Ascension and Declination). I have found a code ...
0
votes
3answers
101 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 ...
7
votes
4answers
213 views

How can I find a line segment with the most intersections along with the coordinates of the intersection points?

There are $n$ points in a 2-D plane and each is given by its $x$ and $y$ coordinates. They are stored in an array in an ascending order with respect to $x$. All points are connected together by line ...
2
votes
0answers
69 views

How can one prove the duality of Voronoi and Delaunay?

Hoping I'm not misunderstanding the concept here, but it is my understanding that Voronoi Diagrams and Delaunay Tesselations are 'dual' to one another, owing to the fact that each' solution makes ...
3
votes
0answers
49 views

Calculating depth mask from different lighting

I have a object which is static, the camera is static and light source is moving. How can the depth mask be calculated ? Concept is to use - calculate height from shadow length Lets imagine a have ...
2
votes
0answers
45 views

Cover a polygon with least amount of parallelograms [closed]

I am solving the task that is as follows: Input: a polygon. Can be any kind of polygon without self intersections. Can be a non-convex and with holes inside. Goal: to cover it with 2 (at least) or ...
7
votes
1answer
110 views

How to calculate the geodesic curvature of a discrete 3D curve?

I have coordinates of a set of points that form a closed loop that lies in a 3D surface. I know the equation of the surface and I can calculate it's surface normal at any point. I found that for a ...
0
votes
2answers
110 views

Ordering points from X Y coordinates

I have series of points extracted from a regular grid, with their X/Y coordinates. A previous algorithm (that I cannot modified!) output a list of these coordinates, but the ordering of these point is ...
2
votes
2answers
533 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...) ...
11
votes
3answers
469 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: ...
2
votes
2answers
67 views

projective reconstruction from orthogonal views

This is a problem from projective geometry. Suppose I have a vector $z \in R^k$ of unit length $\| z \| =1$ inside a $k$-dimensional hypercube. I don't know its value but do know its projection upto ...
3
votes
1answer
67 views

Smoothness regularisation of a 2D field on a triangular mesh?

I'm working on an inverse problem where the solution is the values of a 2D scalar field at the vertices of a 2D triangular mesh, such that the field can be defined continuously inside the mesh via ...
2
votes
1answer
147 views

A robust algorithm to sort a non-convex polygon vertices

Let v_{0},...,v_{N-1} be N points in a Cartesian xy plane defining the vertices of closed polygon (i.e. v_{N} = v_{0}). Let P_{0}...
1
vote
1answer
89 views

Node renumbering in a 2D mesh

I have a 2D domain which is discretized using Q4 elements. I have the nodal positions and the element connectivity matrix. I would now like to renumber the nodes in such a way that all the interior ...
1
vote
1answer
103 views

How to generate a face list from vertices?

I have a little background in writing toy finite volume CFD codes. In 2D Cartesian scenarios, I typically take $x_{\min}$, $x_{\max}$, $y_{\min}$, $y_{\max}$, and the number of points in $x$ and $y$ ...
2
votes
0answers
111 views

Efficient root finding algorithm for monotonic function

This is my first time asking a question here, so I may not be asking this in the right place. I am trying to find the roots of a monotonic function with as few function evaluations as possible. I ...
3
votes
0answers
38 views

Minimum axis aliged bounding box of convex polytope

I need to compute a $n-$dimensional integral with $n<10$ on a convex polytope. Since most numerical integration libraries (e.g. Cuba) expect the function to be integrated defined inside an axis ...
3
votes
0answers
48 views

Approximate the largest simplex in N-dimensional Delaunay triangulation

I am working on determining the spatial information of a set of $M$ points in $N$-dimensional space. It is well-known that the construction of Delaunay triangulation is expensive in high dimensional ...
1
vote
0answers
46 views

Uniformly sample a point per polytope

I want to uniformly sample a point within each of $10^5$ convex polytopes in each iteration of a solver. The polytopes in one iteration are completely different from the polytopes in another iteration....
0
votes
1answer
112 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 ...
2
votes
0answers
109 views

How to numerically optimize affine transformations?

I need to optimize affine transformations for of a set of triangles using energy function based on the connectivity. The energy of an edge $e_j$ between triangles $T_a, T_b$ is given by $$ E_j = \...
0
votes
1answer
90 views

Compute outward normal and surface area for 8 noded brick element in FEA

I have a cube which is divided into 8 small cubes by bisecting each edge, I am trying to find out the surface area of each of the faces and the corresponding outward normals for them. This operation ...
0
votes
1answer
138 views

Connectivity matrix in Finite Element Method in Triangular elements

Imagine a simple triangular base mesh in finite element method with an unknown number of elements (varying by the user). How can connectivity matrix be coded to be generated automatically?
6
votes
1answer
245 views

Putting N hard spheres randomly in given volume

I need to put $N$ spheres with given radius $R$ randomly in a Volume $[-0.5,0.5]^3$, without any overlap of spheres. If I choose values so that all the spheres will occupy ~57% of the total volume, I ...
1
vote
0answers
175 views

Use of Morton Key to reduce number of grid points

I asked a question on Stack Overflow Performance Issue with VP Trees and Nearest Neighborsand I was not satisfied with the answer and so I thought I would reword my question for this site and post ...
7
votes
5answers
260 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 ...
2
votes
1answer
141 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
67 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
82 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
495 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? ...
2
votes
2answers
109 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 ...
5
votes
1answer
177 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 ...
3
votes
2answers
234 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 ...
2
votes
1answer
63 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," ...
8
votes
5answers
733 views

Some good reading on polygon algorithms

What are some good resources (books, articles, sites) about polygon intersection and union algorithms?
15
votes
4answers
3k views

Selecting most scattered points from a set of points

Is there any (efficient) algorithm to select subset of $M$ points from a set of $N$ points ($M < N$) such that they "cover" most area (over all possible subsets of size $M$)? I assume the points ...
3
votes
0answers
77 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
54 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 ...