# 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
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 (...
4k 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 ...
134 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, ...
824 views

317 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 ...
66 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 ...
679 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 ...
100 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 ...
79 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 ...
357 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?
2k 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 ...
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 ...
81 views

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$-...
203 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 ...
165 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 ...
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 ...
319 views

### Finding closed equipotential surfaces on a 3D grid

In short, I'm looking for either: (1) Publications or other sources dealing with contour/isosurface finding algorithms, so that I can write my own implementation (and parallelize as best I can), or (...
111 views

292 views

### Closest interior point on integer grid to a vertex of a convex polyhedron

I have a 3 dimensional convex polyhedron whose vertex coordinates are rational. For one of these vertices, I would like to find the nearest integer grid point (under the Euclidean metric) that is ...
296 views

### Library for closest point on a polyhedron

I need to compute a closest point on a nonconvex polyhedron to a given point in 3D space. I need a simple algorithm or library. I search in CGAL but did not find a suitable function and the package is ...
98 views

### Dissipation and symplectic manifolds

I'm working on an API for simulation of port-Hamiltonian systems. As far as I understand it, a Hamiltonian system is symplectic if it is power conserving, and so including resistive elements would ...
1k views

### How to calculate the area of intersection between a 3D volume and a 2D plane

Hello if anyone can offer insight on how to solve my problem that would be great! I am looking to calculate the area of intersection between a 3D volume and a 2D plane. 3D volume: defined by 6 points ...
138 views

### How to treat hexahedral element with shifted hanging node?

When using the Hexpress grid generator one gets hexahedral cells, possibly with hanging nodes. Because of a smoothing step, the hanging nodes can be shifted: they are not necessarily on the straight ...
200 views

### Restrict Voronoï diagram to a polygon

I managed to build the Voronoï diagram of n points using Fortune's algorithm. This gives me a set of half-edges, some of which being infinite (no starting point and/or no end point). I'd like to ...
533 views

### Backward stable projection and normalization of a vector

Given a machine precision unit vector $n$, and an arbitrary vector $v$, I want an unconditionally backward stable method to compute $$f(v) = \frac{v-nn'v}{\left|v-nn'v\right|}$$ In other words, ...
44 views

### Error in Maple's CellDecomposition Command

I have a simple system that I want to process with the CellDecomposition command of Maple. I don't know why Maple is giving an error here! The code is ...
109 views

### exact area resampling [closed]

I do image processing, and right now I need to resample some images taken from slightly different perspectives so I can match up features. The pixel intensities have scientific significance, so I want ...
2k views

### Shape regularity in higher dimensions

In Finite Element theory, and other methods in scientific computing for PDEs, one uses meshes which fulfill several regularity criteria, many of them being equivalent. It is of interest to have ...