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.

55 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7
votes
0answers
263 views

Finding points inside cells of power (generalized Voronoi) diagram

Suppose we have a set of points $p_1,\ldots,p_n\in\mathbb R^d$ as well as a set of weights $w_1,\ldots,w_n\in\mathbb R$. Recall that the power cell associated to the pair $(p_k,w_k)$ is given by: $$\...
5
votes
0answers
59 views

Why does the naive barycentric hodgestar fail?

The discrete exterior calculus is defined first using circumcentric dual cells, because the primal and dual edges are orthogonal and thus the dual cells are convex. This leads to a diagonal hodge star ...
5
votes
0answers
86 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*, ...
5
votes
0answers
429 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$, ...
3
votes
0answers
52 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 ...
3
votes
0answers
51 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
52 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 ...
3
votes
0answers
103 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:...
3
votes
0answers
2k views

Algorithm to determine if two polygons intersect

I'm working on an algorithm which should check if two polygons, described by their vertex coordinates, are: one inside the other, are intersecting or are separated image below describe this three ...
3
votes
0answers
105 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 ...
3
votes
0answers
80 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, ...
2
votes
0answers
50 views
+50

Why is bounding a surface with a capsule is better than with a cylinder to detect intersections?

In this article: https://www.geometrictools.com/Documentation/IntersectionOfCylinders.pdf the writer says: "If you plan on using cylinders for bounding volumes in a real-time graphics engine—...
2
votes
1answer
77 views

Project to nearest point on convex polyhedron

I have a point $y \in \mathbb{R}^d$ and a convex polyhedron $\mathcal{P}$ given as the intersection of half-spaces: $$\mathcal{P} = \{x \in \mathbb{R}^d \mid a_1 \cdot x \le b_1, \dots, a_n \cdot x \...
2
votes
0answers
30 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
67 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
39 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 ...
2
votes
1answer
231 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 ...
2
votes
0answers
287 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 = \...
2
votes
0answers
69 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 ...
2
votes
0answers
61 views

How to model pedestrian flow through subway systems?

I'm a New Yorker and take the subways every day. I have a growing interest in understanding the distribution of paths people take on the subways to work every day. I.e. if there are $n$ subway ...
2
votes
0answers
1k views

Center of mass in systems with periodic boundary conditions

I have a question about the calculation of center of mass (COM) in systems with periodic boundary conditions. There is a method introduced here: https://en.wikipedia.org/wiki/Center_of_mass#...
2
votes
0answers
146 views

Area of convex n-dimensional polytope

I am looking for an efficient algorithm to calculate the surface area of an irregular N-dimensional polytope. I have a description of this polytope both as coordinates of the vertices as as linear ...
2
votes
0answers
71 views

interpolate the circle going through three points using splines

It is known from Geometry that any 3 points determine a circle. This is the problem of Appolonius Programming solutions try to approximate using Bezier curves. Can you not draw conics as Bezier ...
2
votes
0answers
89 views

Bracket Algebra, Straightening Algorithm

My apologies if the question is simple. I need to write a code for straightening algorithm. Which includes defining bracket algebra. I tried to write it in CoCoA-5, but it wasn't possible because ...
2
votes
0answers
179 views

NURBS surface fitting for a closed region on mesh

I'm developing a tool that allows users to select a closed boundary (a polygon) on the triangle mesh and then from this boundary, generate a NURBS surface fitting the original mesh surface. My idea ...
2
votes
0answers
81 views

About Convex Geometry

A consistency notion in constraint programming: Let $P = (X, D, C)$ be a CSP. Given a set of variables $Y \subseteq X$ with $|Y| = k -1$, a locally consistent instantiation $I$ on $Y$ is $k$-...
1
vote
0answers
82 views

Fortune algorithm for voronoi diagram

Although there are many algorithms to construct Voronoi diagram, some of them are faster than others. Based on my knowledge Fortune algorithm is fastest for construct Voronoi diagram either in two ...
1
vote
1answer
88 views

How do I find the portion of a cell/voxel lying within a defined surface?

We have a 3-dimensional grid of voxels (or cells), with individual voxels being of volume $dx\,dy\,dz$ where $dx=dy=dz=1$. A cone-like surface is defined by some function, $z = f(x, y)$, which in ...
1
vote
0answers
27 views

Simplification of vertices and dihedral angle relations of a polygonal chain

I am trying to understand the generation of Cartesian coordinates of polygonal system or poly line with fixed bond angles and fixed link lengths. I assumed the bond angle to be the same and link ...
1
vote
0answers
71 views

How to approach geographic data interpolation by distance?

let's say I have a set of geographic locations (lat, lng) resulting from a query. Those locations have some kind of internal ranking, my set is sorted by this number in a descending order. Now I'm ...
1
vote
0answers
73 views

Derivatives over a Finite Element mesh

I have a data extracted from Comsol on some node points and I know the coordinates of each node. Does anyone know how Comsol calculate the partial derivative from the values at each node and also ...
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....
1
vote
0answers
197 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 ...
1
vote
0answers
59 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 ...
1
vote
0answers
43 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 ...
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 ...
1
vote
0answers
65 views

Closed-form Jacobian of se3 element w.r.t. 6-dof motion

Let $A$ and $B$ be two rigid transformations in 3D space that transform things from global to local coordinates. Let their relative transformation be expressed by $W=A*B^{-1}$. $W$ can also be ...
1
vote
0answers
37 views

Find alternative path closest to original

I have a set of points in a 2D space. I want to connect the outer points so I get the convex hull. The problem here is that there is a limit to the distance between two points. Let me clarify that ...
1
vote
0answers
85 views

Mesh partitioner with user-defined overlap

I am looking for a mesh partitioner, where I can specify overlap, for example h = 3. I have looked into metis, but I wasn't able to find such a functionality. Is there any other package which ...
1
vote
0answers
36 views

Detecting and joining series of line segments that run along each other

Given: Several circular series of map GPS coordinates for several bus routes. The GPS coordinates are not all equal when they run along the same road. The number of GPS coordinates for a single bus ...
1
vote
0answers
43 views

Interior nodes of a closed graph?

Does anybody know if any graph partitioner library such as Metis, Scotch, or Zoltan can (besides splitting a domain), differentiate between internal (i) and boundary (b) nodes?
1
vote
0answers
541 views

Equilateral triangle based mesh generation by intersection

In work I am currently working on I need to mesh some structure with equilateral triangles to study it using a kind of discrete element method known as spring networks or Lattice model. To mesh the ...
1
vote
0answers
148 views

Checking if convex polytope is nonempty

I am currently running a linear program with MATLAB to determine, by the exitflag of linprog, if two rotated and shifted hypercubes have nonempty intersection. I wondered if this is a waste of time, ...
1
vote
0answers
104 views

Algorithm for merging mesh with cad file

I am writing the pre processing program for a porosity based cfd project we just started. Basically I have a 3 dimensional mesh made of cubes and I need to import a STL file over it, and calculate how ...
1
vote
0answers
101 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 ...
0
votes
0answers
28 views

Largest triangle that contains a point

Given the location of $n$ points on a 2D plane ($P_1, P_2, \ldots, P_n$); and the location of a special point $X$. Find three points $P_i,P_j,P_k$ ($i \neq j \neq k$) such that point $X$ is inside the ...
0
votes
0answers
39 views

Storing and retrieving two-dimensional and three-dimensional data

I work on computational geometry. A huge number of two-dimensional and three-dimensional data are found in my project. Coordinates of polygon and polyhedrons vertices consisted of two-dimensional and ...
0
votes
2answers
71 views

Problem of half-planes intersection

Consider the half-planes $\{x \leqslant 2\}$ and $\{x+y \leqslant 3\}$. These two half-planes are coded with the R package 'rcdd' as follows: ...
0
votes
0answers
17 views

Minimal covering of rectangle with fixed, overlapping rectangles

A finite set $R$ of fixed, axis aligned 2-D rectangles $r_i=\left\{x_{0i},y_{0i},W_i,H_i \right\}$ is given. These rectangles are potentially overlapping. Given a new axis aligned rectangle $t$, I ...
0
votes
0answers
28 views

Hi I am trying to model a 2D Lug angle using Gmsh 4.6. How can I combine transfinite quad and regular full quad meshes in the following geo file?

I need transfinite mesh a small section of the bolt hole to insert a crack. However, The transfinite mesh and regular full quad mesh seem being incompatible and throwing errors. How can I combine ...