topic Re: Creating Voronoi Diagrams in JMP or JSL in Discussions

Creating Voronoi Diagrams in JMP or JSL

thisismiller — Thu, 19 Apr 2018 15:18:30 GMT

Hi all, I'd like to create a Voronoi diagram within the JMP environment. I have a set of point coordinates (X & Y) that are located within the same plane (Z). I'd like a way to show the density of the points per unit area. A Voronoi diagram would be one way to accomplish this. It shows the boundary around the point which is defined by half-way between the euclidean distance between that point P1 and the next point Pn.

Here is Wikipedia's definition: https://en.wikipedia.org/wiki/Voronoi_diagram

Here are instructions for creating this type of diagram in MATLAB

Re: Creating Voronoi Diagrams in JMP or JSL

gzmorgan0 — Thu, 19 Apr 2018 14:59:14 GMT

I am not an expert in this area, however, I recalled reading that JMP Triangularization is an implementation of the Delaunay triangularization which is the "dual" of Voroni. I do not have the algorithms for computing the "dual" plot.

Attached is a sample data set called voroni.jmp that I created to emulate a set of points that are found in several Voroni training documents ( see http://cgl.uni-jena.de/pub/Workshops/WebHome/cgl12new.pdf ). The attached PNG file shows the "dual" relationship of Voroni plots and Delaunay tesselation (triangularization). This attached jmp file has several data table scripts attached. I tested them in JMP 12,13 and 14.

Run each of the table scripts that create graphs. Since you are intrerested in density per unit area, look at the graph Density of Y By X then use the inverted red triangle menu to select a Mesh Plot for a 3D view of density. These views might meet your need or be more informative regarding density.

If the density plots will not serve your purpose and you are still interested in Voroni plots, you can get them from the deldir R package: see https://flowingdata.com/2016/04/12/voronoi-diagram-and-delaunay-triangulation-in-r/ Since JMP does have nearest neighbor and distance algorithms, maybe someone will provide this blog with the necessary steps ( or JSL), to create Voroni diagrams.

Your question motivated me to test the JMP Triangularization method and verify it produces the "classic" results ... after the X and Y coordinates were standardized. [ thanks! ] The attached JSL has steps for drawing the triangles.

Re: Creating Voronoi Diagrams in JMP or JSL

Craige_Hales — Thu, 19 Apr 2018 11:55:56 GMT

Nice example!

and discussion here: https://stackoverflow.com/questions/85275/how-do-i-derive-a-voronoi-diagram-given-its-point-set-and-its-delaunay-triangula

Re: Creating Voronoi Diagrams in JMP or JSL

thisismiller — Thu, 19 Apr 2018 22:24:37 GMT

Hi gzmorgan0,

This is a great start! Thank you for your help.

I did previously play around with the nonparametric density plots, but I wasn't sure this was providing the results I need. Your post helped me to find the right documentation to explain the nonpar density plots mathematically. I'm sharing that definition below. Now that I've read about it, I am still concerned.

Nonpar Density estimates a smooth nonparametric bivariate surface that describes the density
of data points. The plot adds a set of contour lines showing the density (Figure 5.16). The
contour lines are quantile contours in 5% intervals. This means that about 5% of the points
generated from the estimated nonparametric distribution are below the lowest contour, 10%
are below the next contour, and so on. The highest contour has about 95% of the points below
it.

The contours are nice, but they are only splitting the points into equal quantiles. They don't necessarily show how evenly spread the points are within my area. I've attached an example of a data point array to try to convey my point. Do these contours each represent an equal amount of surface area?

A few follow-up questions:

(1) Is there a way to take the nonpar contour data and manipulate it to show the density per unit area? Maybe this is what the "save density grid" option does from the red triangle menu within quantile density.

(2) Can I use a different color theme? I am strongly opposed to the spectrum color theme. However, the color theme() function doesn't work within nonpar density() on JMP13.

(3) Can you help me to extend the Delaunay triangulation to actually show the Voronoi diagram? I'm not comfortable with the math myself.

Re: Creating Voronoi Diagrams in JMP or JSL

gzmorgan0 — Wed, 25 Apr 2018 00:22:00 GMT

Hi,

First of all sorry for the misspelling of Voronoi, old eyes. I am not sure what question you are trying to answer. I think you might be looking for a density or clustering pattern on a wafer map, given the circular picture with a 150 mm radius. I have experience with semiconductor manufacturing data.

JMP has many clustering methods and since JMP12 provides several spatial pattern methods, including one that can cluster wafers based upon pattern similarities. The script below opens a JMP sample data table representing 125 wafer with different defect density and classifies/clusters the wafers by patterns. It can do it for 1 wafer as well.

Names Default to Here(1);

dt = Open("$sample_data/Wafer Stacked.jmp");

dt << run script( "Spatial Cluster of Defects");

spWin = Window("Wafer Stacked - Hierarchical Cluster of Defects");
spClust = (spWin<< child)<<child;
dendro = spClust << Xpath("//OutlineBox[@helpKey='Clust Dendro']");
dendro << Close(0);
//scroll down grab the diamond and move to the left or right to see the clustering change.

I tackled this task because I have been trying to learn more about generating 3D terrains using opengl which has mesh methods. However, I do not know enough about them yet. I decided to tackle craeteing the dual Voronoi graph because spatial geometry is an interest of mine. As stated in my first reply, JMP Triangularization (can be found in the Help > Scripting Index under objects) creates the Delaunay traingularization and also provides messages to get, triangles, points and edges.

I expanded my script to compute the Voronoi dual graph. I have not tested performance for dense points; many of the websites with alternate algorithms and approximations deal with performance. Using the pseudo code reported at the link Craig Hales provided, I created a script. I have only tested it on the single example data table. By the way that data table was generated by copyiong the picture from the link, using it as a background in an XY graph and using mousetrap to capture the coordinates as i clicked on the vertices. You'll note the left most point is a little more left than the original. [yes JMP provides numerous tools to tackle a task.] The new script seems to do the job. It is not application ready, uses a square frame, not a circular wafer, and it standardizes the points (so centered between +/-3 in X and Y).

The script includes a file LCombine.jsl (one of the scripts from "JSL Companion Applications of the JMP Scripting Language, 2nd Ed."). It is attached. You will need to change the path in the attached script to the directory where you saved it. I attached the picture generated by the script. It was tested in JMP 12, 13 and 14.

If you can narrow down the task, like what you want to do with the Voronoi graph or clusters, it would be helpful.

It is not high on my list, but I do believe opengl mesh methods might be able to create a Voronoi graph. I need to do more learning/exploring before saying anything definitively.

voronoi diagram with JMP