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
17
votes
3
answers
2k
views
Implementing an algorithm for finding the largest circle that contains a single point in a set (and no other point)
This question concerns the implementation of an algorithm proposed by Rahul Narain on a former question of mine that was migrated to math.stackexchange: https://math.stackexchange.com/questions/483845/...
- 171
4
votes
0
answers
270
views
Generating an obstacle-avoiding closed-curve with a fixed perimeter and a target area
I was wondering if there was a neat way to solve the following problem in Mathematica v9 -
Provided a binarized image (where we call black pixels "obstacles" or vice versa, whichever is most ...
- 63
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
6
votes
2
answers
1k
views
How to use a ConvexHull as RegionFunction?
I have a set of data supported over a region in 2D. I want to use RegionPlot and ContourPlot on interpolations of my data, but want to restrict the Plots to the region over which my data is supported.
...
- 655
0
votes
1
answer
420
views
Partitioning a list of 2D points into sublists that fit into non-overlapping equal-sized squares [duplicate]
I have a set of {x, y} coordinates, for example:
...
- 353
10
votes
3
answers
954
views
I can't understand FindShortestTour
I can't understand the function FindShortestTour because of the result:
FindShortestTour[{{0, 1}, {5, 1}, {2, 1}, {10, 1}}]
...
- 3,191
5
votes
1
answer
2k
views
How to split compound polygons into convex polygons?
Is it possible to split non-convex polygons into convex plygons with Mathematica 9?
For example:
...
- 2,570
3
votes
1
answer
103
views
14
votes
1
answer
983
views
rule-based implementation of an algorithm
When I first started learning about rule-based programming with Mathematica, I tried to translate this algorithm for computing the convex hull of a set of 2-D points in $O(n \log(n))$ time, to use ...
- 2,719
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
2
votes
2
answers
315
views
Finding integral points on a surface
Suppose I have a dimension formula (for a Lie algebra representation) that is as follows:
$$
d(a,b) = {(a+1)(b+1)(a+b+2) \over 2}
$$
Now consider the surface $F(a,b,n) = 0 = d(a,b) -n$ where $n \in \...
- 167
1
vote
2
answers
916
views
Translating a "Point-to-Triangle" distance script from MATLAB to Mathematica
Update - Thanks everyone for your responses! After fixing a problem with vector normalization, the code below now works.
I'm a new user, and I was attempting to port some Mathematica code from ...
- 13
17
votes
9
answers
9k
views
How do I draw a hemisphere?
I want to draw a solid or partially transparent hemisphere above a partially transparent cuboid object in Graphics3D. However, I do not know how to do this such ...
- 421
17
votes
3
answers
9k
views
Graphics3D: Finding intersection of 3d objects and lines
I found these two nice links 1) intersecting graphics 2) Implementation of Balaban's Line intersection algorithm in Mathematica which works for 2d.
However, I need to find whether a ray(line) ...
- 4,539
2
votes
1
answer
872
views
Creating hexahedral finite elements in Mathematica
Is it possible to do FEM using hexahedral elements in Mathematica? If it possible, is there any help to do that?
- 79
8
votes
4
answers
2k
views
How to create a planar graph from a set of random points
Question
Given a set of points in the plane, how can you create a planar graph in the standard graph representation of Mathematica (version 9 or higher), from these points?
Background
A planar graph ...
- 7,617
0
votes
3
answers
352
views
Cover a rectangle with size constrained rectangular regions
I have a big grid (indicated on the image in grey) that is divided in several blocks (each with a maximum width of 3 units). Now I would like to divide a region (indicated on the grid in red) by the ...
- 109
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
17
votes
3
answers
11k
views
Create triangular mesh from random list of points
I have a list of points. I would like to take these points and create a mesh of triangles from them, making sure triangles don't overlap. So here's a list of points:
...
- 3,366
20
votes
2
answers
1k
views
Equidistant points on a polyline
Set of 2D-points connected by a polyline B-spline function:
...
- 5,809
10
votes
3
answers
4k
views
Convex hull of a 3D object?
I am trying to find a convex hull command for a Graphics3D object. Does it exist in Mathematica?
...
- 2,593
3
votes
0
answers
670
views
How to make 3D object smooth?
This thread considers mathematical methods here to make the 3D object smooth but this question consider how to achieve the goal of smoothing a 3D object in Mathematica.
I want to get smoother ...
- 2,593
7
votes
0
answers
582
views
Computing Ehrhart's polynomial for a convex polytope
Is there a Mathematica implementation for computing the Ehrhart polynomial of a convex polytope which is specified either by its vertices or by a set of inequalities?
I am interested in knowing this ...
- 971
1
vote
2
answers
546
views
Integrating polynomial functions over polytopes with an add-on package
There is a Mathematica package to evaluate integrals over polytopes:
http://library.wolfram.com/infocenter/Books/3652/
In the documentation (Functions.nb file) I ...
- 971
7
votes
3
answers
5k
views
Calculating a minimum bounding box for a set of 3-space coordinates / spheres
I have a set of 3-space coordinates for the atoms of a molecule (I could also transform them into spheres with radii corresponding to the atoms they represent). I would like to place this molecule ...
- 1,477
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
16
votes
3
answers
3k
views
Finding the perimeter, area and number of sides of a Voronoi cell
Does anyone have any suggestions how to determine the perimeter, area and number of sides of each Voronoi cell in Voronoi diagram?
- 787
4
votes
1
answer
468
views
A Graphics`Mesh`ConvexHull[] peculiarity
I have been unable to explain the behavior of Graphics`Mesh`ConvexHull[] on the following (highly simplified) example:
...
- 371
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
6
votes
2
answers
2k
views
Extracting polygons from 3D contour plot surface
Edit: This question turned out to be two parts so I am going to make this question about only the first part a kguler provided an excellent answer.
Here is a better representation. My actual data ...
- 9,572
13
votes
1
answer
835
views
Has anyone implemented cohomology for complex manifolds?
I'm investigating the cohomology of complex manifolds, and need to construct chain complexes, Mayer-Vietoris sequences etc. I use Mathematica for numerically tracing manifolds with geodesics, but ...
- 131
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
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.5k
18
votes
3
answers
5k
views
Checking if a point is in a convex 3D polyhedron
Extending from these questions How to check if a 3D point is in a planar polygon? and How to check if a 2D point is in a polygon?.
I'm trying to do this to render specific shapes made up of spheres.
...
- 9,572
3
votes
1
answer
536
views
How can Mathematica be used to detect an area surrounded by the most lines?
I have an array of lines that produce random shapes. These lines define edge boundaries from an array that I would like to use to reconstruct the main feature of the array. Can Mathematica find the ...
- 4,478
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
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
24
votes
6
answers
3k
views
How to speed up the function DelaunayTriangulation?
First define a function meshGrid to generate some points:
...
- 2,461
4
votes
2
answers
370
views
Vectors in a spherical shell
I have written code that randomly generates a 3D vector of random magnitude. I now want to create a histogram of how many vectors lie in the concentric spherical shells (n*delta r, (n+1)delta r) ...
- 161
12
votes
4
answers
8k
views
Randomly packing spheres of fixed radius within a cube
How can I have Mathematica randomly place spheres in a cube so they won't overlap? The cube is $20 \times 20 \times 20$, and the spheres have a radius of $0.7$.
- 161
8
votes
2
answers
5k
views
Delaunay Triangulation for 3D Surface Data
I want to do a Delaunay triangulation on scattered 3D surface data. Mathematica itself does it only for 2D through the command DelaunayTriangulation[], which gives ...
- 141
-2
votes
1
answer
429
views
Perimeter and area are positive integers
In Geometry 3D, How can I find the vertices with integer coordinates of a triangle whose perimeter and area are positive integers with Mathematica? Suppose its vertices $(x,y,z)$ has coordinates ...
- 4,473
9
votes
3
answers
6k
views
How to check if a 3D point is in a planar polygon?
Following up on ndroock1's question, I naively tried to apply the solutions to a 3D point and polygon and they didn't work. For example, functions involving ArcTan ...
- 7,439
15
votes
6
answers
1k
views
How to ensure that Polygon[list] plots a simple polygon?
Consider the following code which plots a triangle.
p = {{0, 0}, {.2, 0}, {0, .2}};
{Cyan, Polygon[Dynamic[p]]} // Graphics
Then adding (for example) ...
- 9,647
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,647
1
vote
1
answer
313
views
Code to draw geometry doesn't run
I'm new to Mathematica and have no background whatsoever in programming, although I will teach myself soon. I was wondering if one of you programming pros could help me out. I received a code from ...
- 21
8
votes
2
answers
1k
views
Finding concave hull for separated small clusters
Data :
data3D = Import[file, "VertexData"];
Graphics3D[Point[data3D]]
How to find concave polygon for separated small clusters.
user1362
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
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
6
votes
3
answers
5k
views
Mathematica function intersection points with 3D grid
I need to produce a 3-dimensional equispaced grid over a given function in a way, that I can calculate intersection points of the function with the grids edges.
So my first question is how to produce ...
- 141