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
1
vote
1answer
200 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
123 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
45 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
50 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
50 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
195 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
102 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
518 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
324 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
189 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
265 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
160 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
68 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
83 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
533 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
110 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
235 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
240 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
71 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
804 views

Some good reading on polygon algorithms

What are some good resources (books, articles, sites) about polygon intersection and union algorithms?
17
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
93 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
57 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 ...
4
votes
1answer
349 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, ...
7
votes
2answers
2k 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
93 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 ...
7
votes
1answer
265 views

Does some form of documentation of GMSH exist?

I am looking to implement GMSh into a simualtor that I am going to create. I am looking to integrate the geo, mesh, and post processor modules. However, looking online, it appears the documentation ...
27
votes
5answers
16k 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 ...
3
votes
1answer
227 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 ...
0
votes
1answer
55 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 ...
5
votes
1answer
322 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}$ ...
5
votes
1answer
157 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 ...
0
votes
1answer
193 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 ...
2
votes
2answers
213 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 ...
6
votes
2answers
173 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^...
3
votes
4answers
660 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 ...
7
votes
4answers
3k 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
169 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
86 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
80 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
37 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 ...
4
votes
3answers
219 views

K-nearest neighbours search in subspaces of a high-dimensional space

I'm looking for a good way to partition a large, fairly high-dimensional dataset in order to perform fast kNN searches not just in the full $N$-dimensional space, but also in lower-dimensional ...
0
votes
1answer
328 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 ...
0
votes
1answer
54 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
71 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 ...
3
votes
1answer
2k views

Translate a 3D point along a heading

I need to translate a point (P1) in 3D a certain amount, call it stepSize, along a vector described by a heading composed of ...
1
vote
0answers
30 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 ...
3
votes
2answers
553 views

How to determine if a point is outside or inside a curve

Let curve $C_1$ be defined parametrically $$\begin{aligned} &x(t)=0.5\cos(t)-0.3\cos(3t),\\ &y(t)=1.2+0.6\sin(t)-0.07\sin(3t)+0.2\sin(7t) \end{aligned}$$ How do I find if an arbitrary point $...
0
votes
1answer
128 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 ...