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
21 views

Why is bounding a surface with a capsule is better than with a cylinder to detect intersections?

In this article: https://www.geometrictools.com/Documentation/IntersectionOfCylinders.pdf the writer says: "If you plan on using cylinders for bounding volumes in a real-time graphics engine—...
1
vote
1answer
72 views

Calculate the arc length of a Steinmetz curve numerically

I'd like to know the length made by the intersection curve of two orthogonal cylinders of different radii a and b where a > b >0. I came across this post that provides a solution with an ...
2
votes
1answer
228 views

Efficient root finding algorithm for monotonic function

This is my first time asking a question here, so I may not be asking this in the right place. I am trying to find the roots of a monotonic function with as few function evaluations as possible. I ...
3
votes
1answer
65 views

Good rectangular covering of an SDF

I have a 2D SDF describing my shape, but it's fine to think of it as a black/white image (black="inside" white="outside"). I want to generate a small set of rectangles (say, 8 of ...
4
votes
1answer
52 views

Algorithm to merge two polygons (using connectivities)?

I am struggling with implementing an algorithm that does one simple thing: Consider two polygons (one can just draw any two polygons and number their vertices), whose connectivities in a node list are:...
0
votes
0answers
28 views

Largest triangle that contains a point

Given the location of $n$ points on a 2D plane ($P_1, P_2, \ldots, P_n$); and the location of a special point $X$. Find three points $P_i,P_j,P_k$ ($i \neq j \neq k$) such that point $X$ is inside the ...
0
votes
2answers
71 views

Problem of half-planes intersection

Consider the half-planes $\{x \leqslant 2\}$ and $\{x+y \leqslant 3\}$. These two half-planes are coded with the R package 'rcdd' as follows: ...
0
votes
0answers
39 views

Storing and retrieving two-dimensional and three-dimensional data

I work on computational geometry. A huge number of two-dimensional and three-dimensional data are found in my project. Coordinates of polygon and polyhedrons vertices consisted of two-dimensional and ...
1
vote
1answer
85 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 ...
2
votes
1answer
77 views

Project to nearest point on convex polyhedron

I have a point $y \in \mathbb{R}^d$ and a convex polyhedron $\mathcal{P}$ given as the intersection of half-spaces: $$\mathcal{P} = \{x \in \mathbb{R}^d \mid a_1 \cdot x \le b_1, \dots, a_n \cdot x \...
0
votes
1answer
50 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, ...
3
votes
3answers
150 views

How to determine if 2 rays intersect?

We are given the 2D coordinates of 2 points: the first point is where the ray starts and it goes through the second point. We are given another ray in the same way. How do we determine if they have a ...
0
votes
0answers
17 views

Minimal covering of rectangle with fixed, overlapping rectangles

A finite set $R$ of fixed, axis aligned 2-D rectangles $r_i=\left\{x_{0i},y_{0i},W_i,H_i \right\}$ is given. These rectangles are potentially overlapping. Given a new axis aligned rectangle $t$, I ...
2
votes
4answers
2k 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 ...
15
votes
3answers
812 views

Fitting Implicit Surfaces to Oriented Point Sets

I have a question regarding quadric fit to a set of points and corresponding normals (or equivalently, tangents). Fitting quadric surfaces to point data is well explored. Some works are as follows: ...
0
votes
0answers
27 views

Hi I am trying to model a 2D Lug angle using Gmsh 4.6. How can I combine transfinite quad and regular full quad meshes in the following geo file?

I need transfinite mesh a small section of the bolt hole to insert a crack. However, The transfinite mesh and regular full quad mesh seem being incompatible and throwing errors. How can I combine ...
36
votes
18answers
9k views

Good examples of “two is easy, three is hard” in computational sciences

I recently encountered a formulation of the meta-phenomenon: "two is easy, three is hard" (phrased this way by Federico Poloni), which can be described, as follows: When a certain problem is ...
3
votes
3answers
142 views

What are some algorithms to calculate the width of an arbitrary polygon when a bounding box approximation is inaccurate

What are some alternative algorithms to creating a bounding box for finding the max width of a concave, simple winding polygon, like the one in the below image? I prefer solutions that are more ...
0
votes
0answers
35 views

Producing Voronoi diagram in three dimensional

A Voronoi diagram is a kind of tesselation that divided the medium into polygons in 2D and polyhedrons in 3D. Although there are many algorithms to construct a Voronoi diagram, some of them are faster ...
1
vote
0answers
81 views

Fortune algorithm for voronoi diagram

Although there are many algorithms to construct Voronoi diagram, some of them are faster than others. Based on my knowledge Fortune algorithm is fastest for construct Voronoi diagram either in two ...
2
votes
3answers
183 views

For traditional FEM and FVM, why can't we use mesh to represent geometry and use the mesh which represent the geometry to do the computation directly?

Isogeometric analysis [1] has the advantage of integrating geometric and mesh models using NURBS or Spline. At the same time, I would like to ask a question to my friends: for traditional FEM and FVM, ...
4
votes
4answers
170 views

Can the mesh generation methods in FVM and FEM be totally based on the knowledge of the mesh generation theory in computer graphics?

The main references of mesh generation methods in computer graphics (CG) I found are discrete Differential Geometry [1] and a famous book "Polygon Mesh Processing" [2], while the "...
0
votes
0answers
47 views

Surface mesh from labeled 3D points

I'm trying to figure out how to create a surface mesh from a set of labeled 3D points. The 3D object could be something like part of a cave system or asteroid where there would be parts of the surface ...
3
votes
1answer
128 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 ...
4
votes
1answer
131 views

Optimally “morph” one set of points into another

Given two sets of (two-dimensional) points, say, $A=\{a_1,a_2,\ldots,a_{n_a}\}$ and (you guessed it) $B=\{b_1,b_2,\ldots,b_{n_b}\}$, and $d^2_{i,j}=\mid a_i-b_j\mid^{\ 2}$ the "matrix" (not ...
7
votes
0answers
262 views

Finding points inside cells of power (generalized Voronoi) diagram

Suppose we have a set of points $p_1,\ldots,p_n\in\mathbb R^d$ as well as a set of weights $w_1,\ldots,w_n\in\mathbb R$. Recall that the power cell associated to the pair $(p_k,w_k)$ is given by: $$\...
5
votes
0answers
59 views

Why does the naive barycentric hodgestar fail?

The discrete exterior calculus is defined first using circumcentric dual cells, because the primal and dual edges are orthogonal and thus the dual cells are convex. This leads to a diagonal hodge star ...
0
votes
1answer
93 views

Applying weak form

I have two dimensional equation and I want to solve it using Finite Element Methods. $$ \nabla . (\alpha(x,y)\nabla u(x,y)) + \dfrac{\partial u(x,y)}{\partial x}+\dfrac{\partial u(x,y)}{\partial y}+u(...
0
votes
2answers
94 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 ...
4
votes
1answer
119 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 ...
2
votes
2answers
718 views

How to determine the Jacobian Ratio for triangle element?

I am trying to implement an algorithm to find the Jacobian ratio for each triangle in mesh as a part of mesh quality check. Let's say that I have vertices of the triangle: $P_1(x_1, y_1, z_1)$, $P_2(...
0
votes
1answer
428 views

Desmos saying there are too many variables [closed]

I wasn't sure if this is a Computational Science SE question or a Stack Overflow question but I think it's more of this one. I wanted to make a graph where I can rotate a hyperbola (not parabola or ...
-1
votes
1answer
73 views

Detecting degenerate triangles with very thin structures

Between the two ears in the following bunny images, there are some degenerate triangles I want to detect. It looks like a volume-less thin slits. If the question is not clear, please let me know.
8
votes
2answers
4k views

How to get all intersections between two simple polygons in O(n+k)

Basically the formulation of the problem I'd like to solve is very simple. Given 2 simple polygons (without self-intersections) report all intersecting edge pairs in O(n+k) time, where n - is a total ...
10
votes
3answers
869 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 ...
1
vote
0answers
27 views

Simplification of vertices and dihedral angle relations of a polygonal chain

I am trying to understand the generation of Cartesian coordinates of polygonal system or poly line with fixed bond angles and fixed link lengths. I assumed the bond angle to be the same and link ...
3
votes
2answers
86 views

Packing spheres inside a geometry

I am looking for packing spheres (can be monodisperse or polydisperse with known radii distribtuions) inside a geometry. I am sure this is a well explored scientific problem with applications in ...
2
votes
2answers
102 views

Is the similar subdivision of a delaunay mesh still delaunay?

I have a delaunay triangulation for a 2d box with say an airfoil inside. If I uniformly refine this mesh by subdividing each triangle in the mesh into 4 triangles by halving each edge, is the ...
5
votes
2answers
2k views

Minimal surface solution in Python

Note: this question was also posted in StackOverflow and math.stackexchange. I have a set of 3D points defining a 3D contour, as shown below. The points in this contour lie in their best-fit plane ...
2
votes
1answer
84 views

How to divide points on a 3D complex surface into two regions based on a closed curve defined on this surface?

My problem seems simple but I can't find an algorithm that will do that for me for any 3D complex surface. I have a really complex shape 3D surface and a closed curve on it defined by some points (...
0
votes
1answer
39 views

Produce vertex displacements from volumetric shrinkage data on unstructured meshes

I was wondering what would be an efficient way to produce compatible displacements for mesh nodes/vertices if the computed data is volume shrinkage of each element/cell in the unstructured mesh? ...
1
vote
0answers
71 views

How to approach geographic data interpolation by distance?

let's say I have a set of geographic locations (lat, lng) resulting from a query. Those locations have some kind of internal ranking, my set is sorted by this number in a descending order. Now I'm ...
0
votes
1answer
43 views

How to find the nearest point inside a list in a given direction

Being $\bar{\mathbf{x}} \in \mathbb{R}^3$ a point and $S =\{\mathbf{x}\}_{i=1}^N \in \mathbb{R}^3$ a sample of N points. I am looking for a simple algorithm to determine the nearest point in $S$ in ...
3
votes
2answers
123 views

Find shortest path around a cylinder represented by 3d triangular mesh

Suppose I have a 3d triangular mesh with the topology of a finite cylinder. Let $C$ be a vertex on that mesh. How can I find the shortest path from $C$ to itself that goes around the cylinder? By ...
5
votes
1answer
140 views

Maximum and Minimum distance from query point within bounding box

I'm reading an article regarding approximating sums using KD-trees (similar to FMM). As part of the effort I'm trying to make sense of this article , which is cited. I'm having trouble understanding ...
1
vote
0answers
73 views

Derivatives over a Finite Element mesh

I have a data extracted from Comsol on some node points and I know the coordinates of each node. Does anyone know how Comsol calculate the partial derivative from the values at each node and also ...
5
votes
1answer
318 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)...
11
votes
3answers
2k views

Volume of 3D convex hull of small point sets all on the hull

I have a question that is similar to this one asked before except in 3D, and I only need the volume, not the actual shape of the hull. More precisely, I'm given a small set of points (say, 10-15) in ...
0
votes
0answers
66 views

Dividing Point Cloud into voxels

I am reading a paper on implementing convolution neural network for a 3D point cloud. In this paper, they are dividing the point cloud into voxels. Is there any easy way to do it using point cloud ...
2
votes
0answers
30 views

Check if two points are symmetrics/asymmetrics

I am working on an Android app which lets a group of children draw whatever they want in a specific area. I need to check if the lines and figure that they draw are symmetric. The problem is that ...

1
2 3 4 5