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
3
votes
3answers
736 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
108 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
84 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
475 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
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
3answers
2k 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
62 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
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 ...
2
votes
2answers
580 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
72 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
107 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
34 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
35 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
80 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
601 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
211 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
526 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
83 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
122 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
271 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
49 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'...
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
1answer
690 views

Calculate the area and perimeter of a hand-drawn shape

I need to know whether my idea for my final year project could be achieved or not. If its achievable please guide me with the relevant language and other frameworks. The idea I have a piece of paper ...
1
vote
0answers
41 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?
2
votes
0answers
932 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#...
4
votes
3answers
259 views

Point inside curved finite element

I like to create interpolation functions for second order finite element meshes. For elements with straight edges all is good, but some of my elements may have curved edges as shown in the figure: I ...
7
votes
2answers
512 views

Matrix free finite elements method for visualization in process tomography

I am Computer Scientist and now I am interested in matrix multiplication on GPUs. My research are focused on matrix free finite elements method where I multiply sparse matrix. Sparse matrix could ...
4
votes
1answer
154 views

Rank constrained SDP

I would like to optimize a function of the following form: \begin{equation} \sum_{i,j=1}^N c_{i,j} \mathbf{x}_i \cdot \mathbf{x}_j, \end{equation} where $\mathbf{x}_i \in \mathbf{R}^d$. Is it possible ...
2
votes
0answers
118 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 ...
3
votes
5answers
211 views

Distance between points

I am wondering how can I solve following problem. Arrange randomly $n$ points inside a square of side $a$ under the condition that the distance between any two points may not be smaller than 1. I ...
5
votes
2answers
2k views

How to determine whether two cylinders intersect or not?

Considering any two cylinders, defined as: the center of their bottoms $A_i$, the radius of their bottom $R_i$, the unit vector $W_i$ of their axis direction, and the length $L_i$ of the cylinders, ...
2
votes
1answer
406 views

Comparison of convex hulls [closed]

Consider a set of polytopes $P_i : i=1,2,...,k$ each of which has a structure as $P_i:= \{(x_{i1},x_{i2},..., x_{in})\; |\; x_{ij} \in [a_{ij}, b_{ij}] \subseteq [0,1]\}\;\; \text{for all}\;\; j=1,......
5
votes
1answer
161 views

How do you mesh and re-mesh a surface (2-manifold) in 4D?

For ease of explanation, suppose that you began with a two-dimensional surface in (x1, x2, x3, x4)-space, and the surface begins as a flat planar region in the (x1, x2)-plane. The boundaries of this ...
2
votes
1answer
290 views

Monte Carlo Double Integration Implementation

Am implementing a monte carlo integration routine to compute this double integral in eqn 0.3 of page 2 of this paper 'Mobius energy of knots and unknots', Annals of Mathematics, http://www.math.ucsb....
1
vote
2answers
145 views

Wrapping grid of points around curvature of an infinitely long cylinder [closed]

I have an infinitely long cylinder defined using radius a point in 3d Axis defined using a 3d vector I have a set of points with 3d coordinates placed in a grid. I want to wrap this grid of points ...
1
vote
2answers
760 views

Ideas on how to search nearby geospatial data fast

I am looking at a very simple problem, but can't quite find the best solution. I need to accept a lat/lon coordinate and based on that coordinate find all the points within roughly ~1km (accuracy is ...
7
votes
2answers
444 views

applications of computational geometry in fields such as CFD?

Out of curiosity, I was recently trying to search what skills are required to be successful as developer in scientific computing field (e.g. CFD or similar). And to do so, I was going to through ...
1
vote
1answer
490 views

Find area of a polygon. In C and Obj C.

I've been given an assignment: Create a console application (using C and Obj C) that will calculate area of a random polygon. The application should process input data as a .txt file with a list of ...
4
votes
1answer
67 views

Estimating the local compression/expansion ratio for a transformation on a point cloud

Let's say we have an unorganized point cloud P1 with N points, each with coordinates {x,y,z}. We apply non-rigid transformation to P1 (translation + rotation + warping), to obtain point cloud P2. ...
2
votes
0answers
70 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 ...
1
vote
0answers
515 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 ...
0
votes
2answers
130 views

Minimizing the edge length of a polygon preserving its angles

I am trying to minimize the edge lengths of a polygon while keeping the angles the same. I can achieve this geometrically (iteratively), however, I am looking for some related papers that can solve ...
0
votes
1answer
55 views

Exit point of a ray shot through the earth from another location on the earth?

I have a little computational geometry project I'm struggling with for a non-commercial "art" installation. It is driving me crazy and I'd happily pay for an implementable algorithm/solution (...
2
votes
0answers
88 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 ...
3
votes
1answer
79 views

How to Check a Hyper-Cube for Defects

I would greatly appreciate some help/references on solving the following problem: You are in charge of searching through a n-dimensional hyper-cube $[0,1]^n$ to make sure that it does not contain ...
1
vote
2answers
224 views

How to determine the support/influence domain for irregularly distributed nodes in the Element-Free Galekin Method?

EDIT (26-12-14):In the Belytschko's EFG code, the domain of influence for uniform distributed node can be calculated using the code below; my question is how to calculate xspac and yspac when the ...
3
votes
2answers
430 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 ...
0
votes
3answers
162 views

Meshing of polygons

I need to generate a sequence of increasingly denser high-quality triangular meshes for some pentagons in MATLAB. I want to supply as my input The coordinates of the 5 vertices of the pentagon ...