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

200 questions
Filter by
Sorted by
Tagged with
35 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 ...
534 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 ...
40 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?
757 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#...
245 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 ...
362 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 ...
140 views

### Rank constrained SDP

I would like to optimize a function of the following form: $$\sum_{i,j=1}^N c_{i,j} \mathbf{x}_i \cdot \mathbf{x}_j,$$ where $\mathbf{x}_i \in \mathbf{R}^d$. Is it possible ...
85 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 ...
205 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 ...
1k 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, ...
353 views

131 views

### Riemann surfaces: computing $f(z) = \int_0^z \frac{dx}{\sqrt{P(x)}}$

I am trying to validate that the Schwartz-Christoffel mapping does indeed take the upper-half plane $\mathbb{H} = \{ z: \mathrm{Re}(z) > 0\}$ to a polygon. This involves integrals of functions ...
170 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 ...
326 views

### Computing the (non-convex) boundary of a set of paths between two points

I have a set of paths between two fixed points (marked in red below). Each of these paths consists of an ordered series of $\{x, y\}$ points (marked in blue). I am trying to find the ordered set of ...
994 views

### A method to determine whether a point can be contained within a circle with no neighbouring points

I have been working on a particularly challenging problem and was hoping for some guidance. Here is my problem. I have a point cloud containing millions of points. For each point in the set, I need to ...