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
149
votes
4
answers
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
101
votes
4
answers
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
89
votes
11
answers
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
73
votes
4
answers
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 ...
user484
58
votes
2
answers
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
54
votes
2
answers
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
49
votes
7
answers
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
44
votes
2
answers
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
43
votes
5
answers
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
41
votes
7
answers
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
41
votes
8
answers
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
41
votes
4
answers
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
40
votes
5
answers
2k
views
Site - Cell Correspondence in Voronoi Diagram obtained via VoronoiMesh
Consider the following:
...
- 32.9k
38
votes
6
answers
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
36
votes
1
answer
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 ...
- 104k
33
votes
4
answers
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
30
votes
4
answers
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
28
votes
6
answers
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
28
votes
4
answers
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
27
votes
2
answers
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
27
votes
1
answer
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
26
votes
2
answers
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
26
votes
2
answers
1k
views
Graphics`Mesh`FindIntersections[ ] fails to detect intersections
Graphics`Mesh`FindIntersections[ ] is an undocumented function for, well, detecting intersections very efficiently. Take a look:
...
- 115k
25
votes
2
answers
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
25
votes
3
answers
2k
views
Convert binary voxel image to geometric region
I have a binary voxel image which described a contiguous region in space.
Example:
...
- 233k
24
votes
6
answers
3k
views
How to speed up the function DelaunayTriangulation?
First define a function meshGrid to generate some points:
...
- 2,461
24
votes
4
answers
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
24
votes
4
answers
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
24
votes
1
answer
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
23
votes
3
answers
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?
user1362
23
votes
2
answers
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
22
votes
5
answers
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
22
votes
3
answers
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
22
votes
6
answers
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
22
votes
4
answers
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
22
votes
2
answers
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
22
votes
1
answer
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
22
votes
1
answer
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
21
votes
2
answers
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
21
votes
3
answers
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
21
votes
3
answers
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
21
votes
4
answers
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
21
votes
2
answers
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
20
votes
6
answers
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
20
votes
2
answers
2k
views
Determine whether points lie within a cow
I would like to determine whether randomly-generated points
...
- 3,167
20
votes
3
answers
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
20
votes
1
answer
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
20
votes
2
answers
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
20
votes
2
answers
1k
views
Equidistant points on a polyline
Set of 2D-points connected by a polyline B-spline function:
...
- 5,809
19
votes
3
answers
1k
views
Crop a Voronoi diagram and get a proper MeshRegion
How can I crop a VoronoiMesh (or any similar MeshRegion) to a non-rectangular region and receive the output as a ...
- 233k