Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
0answers
47 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 ...
4
votes
1answer
654 views

Finding Shape Functions for a Triangle in 3D coordinate space

I have a Triangular Plane T given by three points in 3D space $$P_1 = (x_1,y_1,z_1)\\ P_2 = (x_2,y_2,z_2) \\ P_3 = (x_3,y_3,z_3)$$ I want to find the Shape Functions on this plane as $N_1(x,y,z),N_2(...
0
votes
1answer
248 views

Min supporting line for a set of points

I'm trying to solve exercises of the book "Computational Geometry in C" by O'Rourke. Could you please help me with this one? Design an algorithm to find a line $L$ that: has all the points ...
2
votes
3answers
763 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 ...
0
votes
1answer
65 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 ...
1
vote
1answer
98 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 ...
1
vote
0answers
30 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 ...
0
votes
1answer
32 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 ...
1
vote
0answers
67 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 ...
3
votes
1answer
476 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 ...
0
votes
1answer
186 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 ...
0
votes
1answer
334 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 ...
4
votes
4answers
328 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 ...
1
vote
1answer
78 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.
3
votes
0answers
104 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 ...
6
votes
3answers
157 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 ...
8
votes
1answer
225 views

Does some form of documentation of GMSH exist?

I am looking to implement GMSh into a simualtor that I am going to create. I am looking to integrate the geo, mesh, and post processor modules. However, looking online, it appears the documentation ...
3
votes
5answers
233 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-...
4
votes
1answer
47 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 ...
3
votes
1answer
905 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'...
2
votes
2answers
410 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 ...
1
vote
0answers
34 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
0answers
36 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?
1
vote
0answers
618 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#...
1
vote
1answer
451 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 ...
3
votes
0answers
838 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 ...
6
votes
2answers
295 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 ...
2
votes
0answers
70 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 ...
4
votes
1answer
118 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 ...
3
votes
3answers
480 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 ...
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
290 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,......
4
votes
3answers
224 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 ...
3
votes
5answers
199 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 ...
2
votes
1answer
212 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....
14
votes
4answers
2k views

Selecting most scattered points from a set of points

Is there any (efficient) algorithm to select subset of $M$ points from a set of $N$ points ($M < N$) such that they "cover" most area (over all possible subsets of size $M$)? I assume the points ...
1
vote
2answers
124 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
665 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
347 views

How to sample points in hyperbolic space?

Hyperbolic space in the Poincaré upper half space model looks like ordinary $\Bbb R^n$ but with the notion of angle and distance distorted in a relatively simple way. In Euclidean space I can sample a ...
3
votes
0answers
155 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)...
1
vote
1answer
416 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
65 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. ...
6
votes
2answers
403 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 ...
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
423 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
118 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
79 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 ...
0
votes
3answers
132 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 ...