### HEM functions

*Offset, Distance, and Walk over Half-Edge Mesh*

Presented here are three functions for working with Half-Edge Meshes in Grasshopper.

The first uses the lists of vertex’ incident edges (vIE) to calculate the bisecting angles at intersections in-between branches and create an offset of the graph which can be uniquely defined at every vertex (in black and grey in the image above). The output creates two sets of polylines: one which defines the faces and one which defines a polygon around the intersection (in the case of two-segment intersections, this is a straight, bisecting line segment). This is useful for giving a graph material thickness or for offsetting faces inward to suggest circulation capacity along the edges.

The second function analyses the distance of every edge to a point at one of the nodes over the graph (red-yellow-blue gradient in the image above). That is, the distance it would take to walk from one of the origin points to the midpoint of that edge taking shortest path from node to node along edges only. This can be used to take into account the embedded graph distance two points are from one another rather than straight-line Cartesian distance. It could also be used to compute the Space Syntax component of Depth Distance.

The third function traces a random walk over the graph from one or more starting points (the grey circles in the image above show the current position of the walk, the path is hidden from the preview). This allows one to animate HEM analyses from multiple points linked in a smooth progression as in the animation below. A Boolean toggle allows one to eliminate direct backtracking (except at dead-ends, of course) or to permit a limited amount.

*This example, using the street network of Lausanne has over 12600 half-edges. Each frame calculated in just under 1 minute*

*Grasshopper Definition*

(.gh download, and Rhino5 base .3dm)

##### Comments

**4 Responses to “HEM functions”**

Hi Trevor

Very excited about these new functions for grasshopper – thank you very much!

Now that a half-edge mesh has been implemented in grasshopper, I was wondering whether this offset function could be inverted so that the straight skeleton of a polygon could be computed (a la the CGAL definitions?, though they are in C++…)

Great work anyhow, thanks

Daniel

It’s an interesting idea to combine this with a straight skeleton and might help address one of the problems the offset is currently faced with: self-intersection on tight corners when the offset distance is to large.

I took a pass at a basic implementation of the Straight Skeleton on the HEM, and while it’s not as robust as CGAL’s, it is a start. On the backend, I think the code could be better integrated with the HEM data structure than it is now (though you could always merge the straight skeleton and the original HEM segments and calculate a second HEM of the results).

To really solve my offset problem, it will need to be able to compute incrementally and have a way of handling split events, but that’s another day.

Hi Trevor.

I really didnt anticipate you’d get this up and running so quickly! Thanks so much!

For those split events, I’m not sure if you have seen this before (and it looks at cases of weighted straight-skeletons rather than uniform), but http://twak.blogspot.com.au/2011/01/degeneracy-in-weighted-straight.html has a quite thorough run-down of split-event types and their resolutions. It does look quite complicated though.

Hope this is informative!

Cheers

Daniel, yeah normally not so quick, but you got your comment in at just the right time.

The interesting thing the definition as written now actually works on most split events like the inverted pentagon/double-triangle polygon I see in the link. I need to look a little closer to isolate exactly what conditions are still triggering an error. In any case the link you sent look like something to pore over. Thanks!