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
4
votes
1answer
253 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
1k 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
71 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
254 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 ...
25
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
181 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
54 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 ...
4
votes
2answers
308 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
133 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
156 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
140 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
158 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
483 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 ...
6
votes
4answers
2k 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
154 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
69 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
76 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
36 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
1answer
68 views

Optimally “morph” one set of points into another

Given two sets of (two-dimensional) points, say, $A=\{a_1,a_2,\ldots,a_{n_a}\}$ and (you guessed it) $B=\{b_1,b_2,\ldots,b_{n_b}\}$, and $d^2_{i,j}=\mid a_i-b_j\mid^{\ 2}$ the "matrix" (not ...
4
votes
3answers
215 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
280 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
53 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
70 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
1k 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
26 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 ...
4
votes
2answers
276 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
117 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 ...
3
votes
3answers
580 views

Mathematical programming formulation of triangle intersection

Given variables $a_1$, $b_1$, $c_1$ and $a_2$, $b_2$, $c_2$ representing the vertices of two plane triangles, how might one specify the requirement for the two triangles to intersect as an objective ...
1
vote
1answer
101 views

Efficiently determine whether a curve intersects a given rectangle?

Suppose we have a straight line in Cartesian space such that $$ x_k = x_0 + k \delta x, \quad \quad y_k = y_0 + k \delta y, \quad \quad z_k = z_0 + k \delta z $$ where $k$ can take any real value. If ...
1
vote
1answer
82 views

Why rational numbers in the Lenstra–Lenstra–Lovász algorithm?

The Lenstra–Lenstra–Lovász (LLL) algorithm is a famous one for lattice reduction. But concerning its application, I am always baffled by one point. The algorithm applies equally well to irrational ...
3
votes
4answers
394 views

How to “smoothen” (not just refine) a 2D/3D polygonal mesh

Suppose I have a complicated structure given in 2 or 3 dimensions as a polygon mesh. For example, this could represent a "cave" or an assembly of irreguar shaped particles or a tree, whatever. Now I'd ...
2
votes
0answers
60 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
3answers
1k views

Fit best polygon to a discrete contour

I have a discrete contour represented by a set of points. The contour looks like a polygon but if you zoom you see that the edges are rugged (that's because it was obtained while working on a finite ...
1
vote
0answers
53 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 ...
3
votes
0answers
1k 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 ...
2
votes
2answers
484 views

Fitting orthogonal planes to a point set

I have a set of 3d points to which I want to fit two planes. I know the assignment of points to the planes so I don't need any RANSAC or similar. Currently, I'm using a PCA-based approach to fit two ...
0
votes
1answer
70 views

Loooking for name of this geometrical optimization technique

From my knowledge if you fit geometrical objects into point clouds you want in general minimize the squared distances of the point cloud to your fitted objects. I do so with the downhill simplex ...
1
vote
1answer
105 views

What is a good algorithm, and framework, to calculate centres of gravity or mass (cog)?

I'd like to take an photograph, subdivide it into a tesselation, either of squares, or (ideally), hexagons, and then find the centre of gravity (or, if you prefer, centre of mass) of each cell of the ...
1
vote
0answers
32 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 ...
0
votes
1answer
34 views

Parametrization of distorted and dented ellipsoids

My program uses a lot of ellipsoid shaped polygons in 2 and 3 D. So far, I create them by the simple, well-known parametrization about two angles. Now I'd like to have my ellipses a bit dented and ...
1
vote
0answers
75 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 ...
3
votes
1answer
550 views

Library for polygon processing in 3D

I need to process some polygons in 3D. They are typically loaded from an OFF or STL file. Then I need to do some transformations (rotation, move, resize), I'd like to check whether points are inside ...
0
votes
1answer
202 views

Heat Equation in 3D mass Matrix set-up

I am solving a 3D heat transfer equation with variable boundaries (insulated, convective, radiative or free) using a F.D.M. technique. My geometry of choice is a cube. The purpose of my work is to get ...
0
votes
1answer
407 views

Fortran round-off error with floating point operations

I have simple code, which flags nodes with in region enclosed by cylinder. On implementing the code, the result is mild tilt of the cylinder observed case with $\theta=90^{\circ}$. The algorithm for ...
4
votes
1answer
2k views

Unwrap cylinder to plane in Paraview

I want to extract the data from the boundary surface of a cylinder (in a .vtu file) and plot it onto a plane, where the coordinates are theta (rotation angle) and Z(...
1
vote
1answer
82 views

computational complexity for computing perimeter of a polygon

What is computational complexity for computing perimeter of a polygon of $n$ vertices? The polygon is not necessarily regular and can be convex or non-convex.
3
votes
0answers
114 views

Pure math questions arising in computer vision, and the need for mathematicians to solve them [closed]

I've read in several articles/answer written by CS (grad) students or other people that the advanced knowledge of pure math that's required for certain areas of computer vision is sometimes too high ...
2
votes
5answers
250 views

Fast comparison of line segments lengths

I have two line segments given by their endpoints $(a_1,a_2)$, $(b_1,b_2)$ in $R^3$ and want to know if they have the same length (up to some error), so that the naive test looks like $$|\, \Vert a_1-...
3
votes
1answer
48 views

Find a consistent cyclic orientation on a conic section

I have a conic section in the real projective plane. This is represented by its real symmetric 3×3 matrix. I verify that the conic section is real and non-degenerate by computing the eigenvalues of ...
2
votes
1answer
1k views

Fitting a rectangle to a point set

I have an ordered list of (2d-)points that are forming a (not axis aligned) rectangle and I'd like to recover that rectangle. Approximations like a minimal enclosing rectangle can't be used so that I'...