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
1
vote
0answers
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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?
2
votes
0answers
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#...
4
votes
3answers
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 ...
6
votes
2answers
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 ...
4
votes
1answer
140 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
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 ...
3
votes
5answers
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 ...
5
votes
2answers
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, ...
2
votes
1answer
353 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
160 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
222 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
128 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
697 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 ...
3
votes
0answers
178 views

Shape measure for C-shaped objects

There are many well defined measures for many basic geometrical objects such as rectangularity (area coverage of minimum bounding rectangle), triangularity (area coverage of minimum enclosing triangle)...
6
votes
2answers
418 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
447 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
66 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
474 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
123 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
52 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
83 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 ...
3
votes
1answer
91 views

Mesh with constraints

Is it possible to construct a constrained tetrahedral mesh of a domain using Tetgen or similar software? What I mean by constrained is that there are some nodes or edges that are not free but are ...
1
vote
2answers
216 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
419 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
152 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 ...
1
vote
1answer
1k views

Convex Polygon Intersection

Determining the intersection of two convex polygons is one of the fundamental problems in computational geometry . I'm asking for an algorithm having: INPUT: Given two convex polygons P and Q in 2D (...
2
votes
2answers
3k views

Determine unit outward normal vector for a curve

It is necessary for me to find the unit outward normal vector for the curve: $$\gamma=(x(t),y(t)) $$ where $$x(t)=\cos(t)−0.5\cos(3t)$$ and $$y(t)=\sin(t)+\sin(7t)+\sin(3t)$$ I know how to find ...
1
vote
0answers
120 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, ...
2
votes
2answers
659 views

Finding nearest neighbors using Jaccard distance for positive, real-valued vectors

Say we have $x_i, \ldots, x_n \in R ^ D$ with positive, real components and use Jaccard distance $d(x_i, x_j) = 1 - \frac{\sum_{d = 1}^D\min(x_i^d, x_j^d)}{\sum_{d = 1}^D\max(x_i^d, x_j^d)}$ to find $...
3
votes
1answer
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 ...
2
votes
0answers
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 ...
3
votes
1answer
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 ...
6
votes
2answers
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 ...
2
votes
1answer
678 views

What is the exact formulation of compressible Euler equation of gas dynamics in polar coordinates with artificial diffusion in 2D?

The interested equation is advection-diffusion equation. One of the canonical example is Navier-Stokes equations. However, I would like to let the coefficient of diffusion constant goes to zero, $\...
2
votes
1answer
298 views

Speedier alternative to “skimage.morphology._pnpoly import points_inside_poly”?

I am using scikit-image's points_inside_poly function, and in my code I am calling it enough times that it takes up about 50% of ...
1
vote
1answer
63 views

Integer simplification of irrational inequality

I'm doing work in computational geometry where the robustness of the algorithm is important. On two separate occasions now have I come across a scenario where I compare the numerical size of two ...
3
votes
3answers
642 views

Surface integration over a portion of an ellipsoid

I would like to perform a surface integration over a portion $D$ of an ellipsoid. A plane arbitrarily intersects the ellipsoid forming two sections, of which one is $D$. I do not know how I can ...
1
vote
0answers
99 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 ...
0
votes
1answer
76 views

difference of polytopes in $\mathbb{R}^n$

Is checking the equivalence of two convex polytopes $p^{s}$ and $p^{t}$ NP-hard? $p^{s}= CH\{ \cup <p^{s,a_1},...., p^{s,a_m}> \} $ // CH is convex hull computed on union of a polynomial ...
1
vote
1answer
312 views

Number of faces in a 3D multi-type unstructured grid

Given a 3D unstructured grid consisting of mixed types of shapes (hex, tet, ...), is there a method to know how many faces (including boundary faces) are contained in the grid?
3
votes
1answer
1k views

area of voronoi cell

I have a Voronoi diagram that I need to calculate the area of each cell. This Voronoi diagram is produced by Voronoi command in MATLAB. To find the vertices of the Voronoi cell I use ...
4
votes
2answers
70 views

Fitting a surface to scalar functions given on the edges of a triangulation

Given a triangle mesh $\mathcal{T}$ with vertices $V=\{\mathbf{v}_i\}_{i=1}^n$ in $\mathbb{R}^3$ and triangles $T_{ijk}=[\mathbf{v}_i, \mathbf{v}_j, \mathbf{v}_k]$. For each vertex $\mathbf{v}_i$, I ...
2
votes
0answers
80 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$-...
2
votes
1answer
186 views

Algorithm to equalize the area of random tessellation of various polygons

I am looking for an algorithm that I can apply for a random tessellation of polygons with different areas. The algorithm can relax the geometry of the polygons to a condition that all of them would ...
4
votes
3answers
160 views

Plane constraints in R3

I have multiple plane constraints in $\mathbb{R}^3$ of the form: $$n_i \cdot x \ge \delta_i$$ Where $n_i$ is the $i$th plane normal (in form (x, y, z)), $x$ is a point in space, and $\delta_i$ is ...
0
votes
1answer
65 views

How to model waterflow when only a couple of sample points available

Figure below depicts a cross section of a creek for which I am trying to measure the water flow for that section. What we have as inputs are a bunch of sample points on the river. For each sample ...