Skip to content

Instantly share code, notes, and snippets.

@bmershon

bmershon/README.md

Last active September 18, 2016 03:27
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bmershon/9ba5a6fc213717515fba to your computer and use it in GitHub Desktop.
Save bmershon/9ba5a6fc213717515fba to your computer and use it in GitHub Desktop.
Download ZIP
Point Cloud Triangulation
Raw
README.md

One problem we encounter when we attempt to form the Rips-Complex of a point-cloud is over-triangulation.

If we naively form triangles for all unordered triples of points, we create a simplicial complex that is no-longer 2-dimensional. If, for example, we wish to count the number of 1-cycles in a rips-complex formed from a 2-dimensional point cloud, we need to be careful when we add triangles.

Rips-Complex shows this particular application.

Triangles appear when all of the edges for that triangle, the three 1-simplex faces, are present. These edges appear when the balls of radius r that expand around each point first touch. How do we know which edges we should form in the first place?

We can use the Delaunay triangulation in the plane as your limiter; so you only ever draw edges and triangles that form part of the Delaunay triangulation.

Then, the rule for adding triangles becomes:

(x,y) is an edge at radius R if d(x,y) < R/2 AND (x,y) forms an edge in the Delaunay triangulation

Raw
index.html
<!DOCTYPE html><meta charset=utf-8><style>.triangle{fill:#87cefa;stroke-width:1.5px;stroke:#000;fill-opacity:.2}</style><body><script src=http://d3js.org/d3.v3.min.js></script><script>var margin={top:20,right:20,bottom:20,left:20},padding={top:60,right:60,bottom:60,left:60},outerWidth=960,outerHeight=500,innerWidth=outerWidth-margin.left-margin.right,innerHeight=outerHeight-margin.top-margin.bottom,width=innerWidth-padding.left-padding.right,height=innerHeight-padding.top-padding.bottom,svg=d3.select("body").append("svg").attr("width",outerWidth).attr("height",outerHeight).append("g").attr("transform","translate("+margin.left+","+margin.top+")"),data=[[200,200],[200,420],[600,250],[100,210],[150,40],[370,300]],delaunay=d3.geom.delaunay(data),color=d3.scale.category10(),triangle=svg.selectAll("polygon").data(delaunay).enter().append("polygon").attr("class","triangle").attr("points",function(t){var a=t[0][0]+","+t[0][1]+", "+t[1][0]+","+t[1][1]+", "+t[2][0]+","+t[2][1];return a}),dot=svg.selectAll("dot").data(data).enter().append("circle");dot.attr("class","dot").attr("cx",function(t){return t[0]}).attr("cy",function(t){return t[1]}).attr("fill",function(t,a){return color(a)}).attr("r",6)</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment