# 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
224 views

66 views

### How to minimize $(x-a)^2+(y-b)^2$ subject to $\sqrt{a}+\sqrt{b}=\sqrt{2}$?

I am not sure if this is on-topic here, but I am trying. Let $x,y$ be positive real numbers. I am trying to find $$\min_{\sqrt{a}+\sqrt{b}=\sqrt{2}}(x-a)^2+(y-b)^2$$ I tried using Mathematica for ...
49 views

### How do I find the portion of a cell/voxel lying within a defined surface?

We have a 3-dimensional grid of voxels (or cells), with individual voxels being of volume $dx\,dy\,dz$ where $dx=dy=dz=1$. A cone-like surface is defined by some function, $z = f(x, y)$, which in ...
36 views

### Systematically outputting sign vectors of restricted hyperplane arrangement

(I previously asked this question on Sage's dedicated Q&A site, but got no response, so I figured it would be worth trying here.) I have a way of constructing hyperplane arrangements in Sage, ...
106 views

### How can one prove the duality of Voronoi and Delaunay?

Hoping I'm not misunderstanding the concept here, but it is my understanding that Voronoi Diagrams and Delaunay Tesselations are 'dual' to one another, owing to the fact that each' solution makes ...
135 views

345 views

### How to create a random 3D domain representing a plant's root structure?

I would like to model laminar flow of water from roots to the stem of a plant. At the very end of the roots, the tubes vary from millimeter to centimeter scale in diameter and length. As we get closer ...
294 views

### Random placement of euclidean points with constrained inter-point distances in a fixed area

I'd like to place as many random points as possible in a 2D square $S=[0,1]x[0,1]$ such that the euclidean distance $d$ between any two points $d$ is greater than a given value $b$ (b is small). I'm ...
1k views

### Uniform dots distribution in a sphere

I'm trying to implement Barnes-Hut algorithm, with a binary tree. My initial conditions are a uniform mass distribution in a sphere with radius $R$. How can I create uniform dots distribution in a ...
326 views

### Smallest circumscribed circle in spherical geometry

I work in Python 3 on astrophysics projects. I need to compute the smallest circumscribed circle of a set of points in the sky (so described by Right Ascension and Declination). I have found a code ...
148 views

### Is it valid to assume the center of a bounding sphere to be also the center of the bounding box?

Computing an axis aligned bounding box of a point set is trivial. Computing a bounding sphere of a point set is also trivial when the center is known. Computing the center of the bounding sphere is ...
253 views

### How can I find a line segment with the most intersections along with the coordinates of the intersection points?

There are $n$ points in a 2-D plane and each is given by its $x$ and $y$ coordinates. They are stored in an array in an ascending order with respect to $x$. All points are connected together by line ...
51 views

### Calculating depth mask from different lighting

I have a object which is static, the camera is static and light source is moving. How can the depth mask be calculated ? Concept is to use - calculate height from shadow length Lets imagine a have ...
47 views

### Cover a polygon with least amount of parallelograms [closed]

I am solving the task that is as follows: Input: a polygon. Can be any kind of polygon without self intersections. Can be a non-convex and with holes inside. Goal: to cover it with 2 (at least) or ...
182 views

### How to calculate the geodesic curvature of a discrete 3D curve?

I have coordinates of a set of points that form a closed loop that lies in a 3D surface. I know the equation of the surface and I can calculate it's surface normal at any point. I found that for a ...
127 views

### Ordering points from X Y coordinates

I have series of points extracted from a regular grid, with their X/Y coordinates. A previous algorithm (that I cannot modified!) output a list of these coordinates, but the ordering of these point is ...
1k views

### Algorithms to extract trajectory lines out of 3D point clouds

I am looking for different approaches to extract 3D polylines out of Point Clouds. We are able to create these point clouds out of different data sources of real world surveys (LIDAR, RADAR, etc...) ...
74 views

### projective reconstruction from orthogonal views

This is a problem from projective geometry. Suppose I have a vector $z \in R^k$ of unit length $\| z \| =1$ inside a $k$-dimensional hypercube. I don't know its value but do know its projection upto ...
70 views

### Smoothness regularisation of a 2D field on a triangular mesh?

I'm working on an inverse problem where the solution is the values of a 2D scalar field at the vertices of a 2D triangular mesh, such that the field can be defined continuously inside the mesh via ...
341 views

### A robust algorithm to sort a non-convex polygon vertices

Let v_{0},...,v_{N-1} be N points in a Cartesian xy plane defining the vertices of closed polygon (i.e. v_{N} = v_{0}). Let P_{0}...
I have a little background in writing toy finite volume CFD codes. In 2D Cartesian scenarios, I typically take $x_{\min}$, $x_{\max}$, $y_{\min}$, $y_{\max}$, and the number of points in $x$ and $y$ ...