gorhill / Javascript-Voronoi

A Javascript implementation of Fortune's algorithm to compute Voronoi cells
http://www.raymondhill.net/voronoi/
Other
1.03k stars 166 forks source link

No edge or halfedges are created #29

Closed rpadovani closed 8 years ago

rpadovani commented 8 years ago

Thanks for your work on this :)

I'm sure I'm missing something very simple here, but I'm not able to have an useful result.

This is the input:

{ xl: 11.5658569335938,
  xr: 11.6853332519531,
  yt: 44.8761789907703,
  yb: 44.7924263989408 }

[ { x: 11.604309082031248, y: 44.86852295681338 },
  { x: 11.634521484374998, y: 44.85294822403813 },
  { x: 11.604309082031248, y: 44.83736927811443 },
  { x: 11.638641357421875, y: 44.83736927811443 },
  { x: 11.63177490234375, y: 44.820812031724444 },
  { x: 11.5960693359375, y: 44.820812031724444 },
  { x: 11.619415283203125, y: 44.810095984897416 },
  { x: 11.6619873046875, y: 44.83347388333049 },
  { x: 11.649627685546875, y: 44.822760189927365 } ]

And this is the output:

{ site: undefined,
  cells: 
   [ { site: [Object], halfedges: [], closeMe: true },
     { site: [Object], halfedges: [], closeMe: true },
     { site: [Object], halfedges: [], closeMe: false },
     { site: [Object], halfedges: [], closeMe: true },
     { site: [Object], halfedges: [], closeMe: true },
     { site: [Object], halfedges: [], closeMe: false },
     { site: [Object], halfedges: [], closeMe: false },
     { site: [Object], halfedges: [], closeMe: true },
     { site: [Object], halfedges: [], closeMe: true } ],
  edges: [],
  vertices: 
   [ { x: 11.643666783643415, y: 44.794610574161624 },
     { x: 11.64012678846446, y: 44.827050838189045 },
     { x: 11.611433233521034, y: 44.823495044087075 },
     { x: 11.616290671377905, y: 44.826185494149776 },
     { x: 11.650178960146114, y: 44.834610273456285 },
     { x: 11.621475219726562, y: 44.83478582961569 },
     { x: 11.621475219726562, y: 44.84116389601012 },
     { x: 11.652647967468768, y: 44.84940757076509 },
     { x: 11.615399748176795, y: 44.8529461174639 },
     { x: 11.552253172290776, y: 44.8529461174639 },
     { x: 11.627376478435822, y: 44.8761789907703 },
     { x: 11.584201353792057, y: 44.7924263989408 },
     { x: 11.671629951202616, y: 44.8761789907703 },
     { x: 11.61224608828216, y: 44.7924263989408 },
     { x: 11.686745224281982, y: 44.7924263989408 },
     { x: 11.61414593296328, y: 44.8761789907703 },
     { x: 11.644582329600441, y: 44.7924263989408 },
     { x: 11.609475555148991, y: 44.8761789907703 },
     { x: 11.597172383342123, y: 44.7924263989408 },
     { x: 11.635615745083602, y: 44.8761789907703 } ],
  execTime: 6 }

There are no edges and no halfedges - what's wrong?

Thanks in advance!

dmgctrlr commented 8 years ago

Did you ever figure this out?

gorhill commented 8 years ago

Did you try calling Voronoi.quantizeSites() on your sites before computing the diagram?

dmgctrlr commented 8 years ago

I tried that just now, with the same result. I think I'm running into a problem with clipEdges where the c.vb Vertex is null. Not sure why yet.

gorhill commented 8 years ago

This is the input:

{ xl: 11.5658569335938,
  xr: 11.6853332519531,
  yt: 44.8761789907703,
  yb: 44.7924263989408 }

bbox.yt is greater than bbox.yb, meaning an empty bbox, meaning no edge can be found intersecting with it. Reversing the values of bbox.yt and bbox.yb works fine.