# Questions tagged [computational-geometry]

Questions on constructing graphical objects using relatively complex computations relating to the mathematical structures defining those objects. Examples include convex hulls, Voronoi diagrams, Delaunay triangulations, mathematical constructions, symmetries, genuses of curves and graphs and programmatic constructions of polyhedra.

724 questions
Filter by
Sorted by
Tagged with
26k views

### How to create word clouds?

Word clouds are rather useless fancy and visually appealing plots, where words are plotted with different sizes according to their frequency in a corpus. Many applications exist out there (Wordle, ...
• 46.6k
12k views

### How to peel the labels from marmalade jars using Mathematica?

How can I detect and peel the label from the jar below (POV, cylinder radius, jar contents are all unknown) to get something like this, which is the original label before it was stuck on the jar?
• 115k
20k views

### How to check if a 2D point is in a polygon?

Background: I use code from An Efficient Test For A Point To Be In A Convex Polygon Wolfram Demonstration to check if a point ( mouse pointer ) is in a ( convex ) polygon. Clearly this code fails for ...
• 9,637
5k views

### Can Mathematica solve Plateau's problem (finding a minimal surface with specified boundary)?

Given a closed curve $\mathcal C$ in three dimensions, is it possible to use Mathematica's built-in functionality to compute a minimal surface whose boundary is $\mathcal C$? For simplicity, let us ...
20k views

### How can I calculate a jigsaw puzzle cut path?

I want to generate a path to cut an arbitrary shape into a set of jigsaw puzzle pieces. All pieces must be unique to preclude placing a piece in the wrong spot. Pieces must be interlocking such that ...
• 270k
4k views

### Numerically solving Helmholtz equation in 3D for arbitrary shapes

Context While studying manifold Learning I got interested in finding the eigenvectors of the Laplacian. (also in connection to this problem of solving the heat equation) Following this and that ...
• 22.6k
10k views

### Intersecting graphics

Does the Mathematica graphics system have any concept of intersecting graphics? I've not found much in the documents so far. For example, if I want to show the intersection of two shapes: ...
• 24.2k
4k views

### Animating a Voronoi Diagram

edit: Excellent answers have been provided and I made an animation which is suitable for my use, however, all the examples rely on bitmap/rasterized data; is there a vector based approach? I would ...
• 9,572
4k views

### How to estimate geodesics on discrete surfaces?

Continuing with my interest on curvature of discrete surfaces here and here, I would like to also calculate and plot geodesics on discretised (triangulated) surfaces. Basically, my long-term idea ...
• 3,923
3k views

### Voronoi diagrams for generators other than points

Any suggestions on how to determine a Voronoi diagram for sites other than points, as e.g. in the picture below? The input is a raster image.
• 787
5k views

### How can I define a 3D version of the built-in VoronoiDiagram (VoronoiMesh in V10) function?

Can anybody point me in a direction that will guide me to extend the VoronoiDiagram function in Mathematica to handle 3D (three dimensional) situations (i.e. points ...
• 32.9k
7k views

### Creating a 2D meshing algorithm in Mathematica

As what is proving to be a difficult, but entertaining task, I am attempting to adapt a 2D meshing algorithm created for MATLAB and port it to Mathematica. I understand meshing functions already exist ...
• 3,366
2k views

### Site - Cell Correspondence in Voronoi Diagram obtained via VoronoiMesh

Consider the following: ...
• 32.9k
2k views

### Finding length of intersection of two surfaces

I would like to know how we find the length of the intersection of two surfaces. For instance, in the following example,a surface intersects with a plane: How do we find the length of intersection ...
• 483
2k views

### How to perform Loop subdivision on a triangle mesh with Mathematica?

(Cross posted on Wolfram Community) Every now and then, the question pops up how a given geometric mesh (e.g. a MeshRegion) can be refined to produce a (i) finer ...
2k views

### Movable text on a curve

Having an arbitrary curve defined as InterpolatingFunction, what is the best way to place a text on this curve? The text generally has two rows, for example: ...
• 61.4k
3k views

### How to speed up estimation of Mean and Gaussian curvatures on triangular meshes?

I am trying to estimate curvatures on a triangulated surface/manifold using the algorithm of : Meyer, M., Desbrun, M., Schröder, P., & Barr, A. H. (2003). Discrete differential-geometry operators ...
• 3,923
2k views

### Find the nearest locations for multiple points

Assume that there are many holes with their locations fixed, and the same number of balls distributed randomly. What is the smallest total distance for the balls fitting into the holes on the ...
• 2,315
9k views

### Efficiently determining if 3D points are within a surface composed of polygons

This is the 2nd part of a previous question which I edited to make into 2 separate questions: Extracting polygons from 3D contour plot surface As an extension of my earlier question involving simple ...
• 9,572
487 views

### Bug in ArcLength?

fixed in 10.1 (windows) With Mathematica 10.0.2: ArcLength[Line[{{0, 0}, {1, 0}, {2, 0}}]] ArcLength[Line[{{0}, {1}, {2}}]] (* 2 *) (* 2 *) However, ...
• 1,199
360 views

### Regression /Bug in DelaunayMesh from 10.3.1 to 10.4

Bug introduced in 10.4 and persists through 11.1 In answering this question, I realized the OP and I were obtaining different results from the alphaShapes2D code. ...
• 32.9k
3k views

### Implementation of Balaban's Line intersection algorithm in Mathematica

I'm trying to implement a Brillouin Zone algorithm within Mathematica, including the generation of Brillouin zones of higher order in 2D and 3D. There is a nice implementation of generating these ...
• 2,861
1k views

### GraphicsMeshFindIntersections[ ] fails to detect intersections

GraphicsMeshFindIntersections[ ] is an undocumented function for, well, detecting intersections very efficiently. Take a look: ...
• 115k
4k views

### Generating convex polyhedron from face planes?

Suppose I have lists of normals and points for planes. There's a convex polyhedron whose faces lie on these planes and are bounded by plane intersections. What would be the easiest way to produce an ...
• 1,123
2k views

### Convert binary voxel image to geometric region

I have a binary voxel image which described a contiguous region in space. Example: ...
• 233k
3k views

### How to speed up the function DelaunayTriangulation?

First define a function meshGrid to generate some points: ...
• 2,461
5k views

### Generate a Random Polygon

Does some package exist with a function that takes a parameter $n$ and generates a random 2D $n$-sided simple polygon (convex or non-convex), possibly within a certain bounding box? It does not ...
• 343
1k views

### Find the volume of Phobos and Deimos

How can we calculate the volume of a 3D object using the new-in-10 computational geometry functions? For simple objects this works: ...
• 233k
2k views

### How to create regular (planar) graphs?

How to programmatically create and plot regular planar graphs with $k = 3, 4$ or $6$ (not hypercubes) and regular nonplanar graphs of $k = 8$ (see figure)? Note that what matters is the average ...
• 46.6k
5k views

### Finding a Concave Hull

I have 3D clustered data: Is there any other way to get the concave hull of 3D data points?
1k views

### How can the {x,y,z} points that fall on the outer boundary of a set of values be selected and smoothly surfaced?

For a given set of x,y,z values, that may, or may not form a uniform shape, how can the center of the data cloud be found, and the surface points be located and a solid smooth surface created from ...
• 4,478
4k views

### Insphere for Irregular Tetrahedron

I am looking for existing Mathematica code to compute the unique sphere inscribed inside an irregular tetrahedron. I can write it myself, but I would love to find that someone already performed this ...
• 4,659
785 views

### How to extract parts from atomic expressions like DelaunayMesh and Graph?

I was looking at this question here and I tried the suggested idea by Anton Antonov to use DelaunayMesh It will look like this: ...
• 19.7k
3k views

### How to obtain the cell-adjacency graph of a mesh?

In addition to the accepted answer, see also the answer by Chip Hurst. This functionality is built in, but not documented. Given an arbitrary mesh region, how can I efficiently obtain the graph ...
• 233k
4k views

### How to calculate the volume of a convex hull?

Given a spatial curve represented by a parametric equation, is it possible in Mathematica 9 to calculate symbolically (or at least numerically) the volume of its convex hull?
• 437
3k views

### Difference (or intersection) of two convex polyhedra

I have two convex polyhedra stored in the following form: a set of vertices vertices = {{x1,y1,z1},...}, a set of faces, where each face is a convex polygon ...
• 1,680
374 views

### RegionMeasure is wrong for simple 1D Path

Bug introduced in 11.1 Take the simple path defined by a line through a set of points ...
• 8,399
1k views

### Cropping a Voronoi diagram

Someone know how can I get the correct crop of this Voronoi image using RegionFunction? As you can see, there is a lot of undesired white regions inside the left ...
• 26.1k
2k views

### DelaunayMesh in a specified closed region - creating a concave hull from a set of points

I have a list of discrete points wich I want to use as nodes for creating a 2D mesh. I used DelaunayMesh and it works fine. The problem that I have is that some elements/polygons are outside of the ...
• 211
2k views

### Build a refined grid based on intersecting line

I honestly have no idea where to begin with this problem. In summary, I have a 2D coarse grid with an intersecting line. For an easy example, let's assume it's a 4x4 grid. I wish to pass through each ...
• 10.9k
4k views

### How to generate higher dimensional convex hull?

I like the function ConvexHullMesh very much, since I often need to take a look at the convex hull of points in 2D and 3D, which as an example can be generated and ...
• 5,423
3k views

### How to find the incircle and circumcircle for an irregular polygon?

I was inspired by blog post where Gonzalo Ciruelos sorted all the countries by roundness, and looked at the Wikipedia page that gives a different definition of roundness to what Ciruelos used: The ...
• 67.3k
851 views

### Object separation from a 2.5D surface

I'm trying to identify the shape and the boundaries of objects. The data was generated with a laser scanner and represent the surface of an area in which many boulders lay on the ground and making up ...
• 441
608 views

### Find duplicates in list of InfiniteLine

MMA 10 introduced a new function, which can be very convenient: InfiniteLine. Of course, two infinite lines can be described by different arguments: for example <...
• 14.2k
2k views

### Determine whether points lie within a cow

I would like to determine whether randomly-generated points ...
• 3,167
1k views

### How to get a specified number of points that are nearly equally spaced in a closed rectangle

TriangulateMesh is almost the right tool for this problem. For example, ...
• 6,984
2k views

### Faster way to compute the distance from a point to a surface in 3D

I am trying to compute the shortest distance between a point and a triangle in 3D ...
• 739
2k views

### Efficient way of finding shortest distance between two sets of points in mathematica

I have two sets of 3D points, say a = RandomReal[1, {10, 3}]; b = RandomReal[1, {10, 3}]; I wanna find the first N pairs that have shortest distance between the ...
• 1,386
1k views

### Equidistant points on a polyline

Set of 2D-points connected by a polyline B-spline function: ...
• 5,809