# 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.

219 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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(...
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.
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 ...
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-...
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 ...
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'...
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 ...
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 ...
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?
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#...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
406 views

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 ...