alvpickmans/graphical

Research and exploration about geometry, algorithms, data structures and more.

Graphical

Graphical is a personal research project where I explore different topics I am interested about like algorithm theory, geometry, data structures or computer graphics.

History

Graphical was originally conceived as a purely Dynamo package, where I tried to understand and implement visibility graphs in order to find the shortest path on a given layout.

I soon realized that Dynamo's geometry library was too heavy for this purpose, so I started to create custom geometry primitives (vertices, vectors, lines...) in order to improve the performance.

The result is the detachment of the logic used for the construction and computation of graph and visibilities from the purely Dynamo implementation. This might give more flexibility in the future to be aplied in other platforms.

License

This project is licensed under the MIT License - see the LICENSE.md file for details

Acknowledgments

• Dynamo team for the great platform.
• Christian Reksten-Monsen for the inspiration and guidance from his pyvisgraph project.

graphical's Issues

Improve Polygon vertex containment

Use Ray element to perform polygon's vertex containment method.

Edge-Polygon intersection algorithm

Create method to compute the intersection of a polygon and an edge.

Intersection between edges error when perpendicular and intersecting

When doing edge1.Intersection(edge2) and edge1 is perpendicular to edge2 and intersecting on one of edge1's vertex, returned intersection is that vertex. On this case the dot product is also 0 but they are not parallel.

Graphical/Graphical/src/Geometry/gEdge.cs

Lines 112 to 137 in c51ff69

	// if dot == 0 it means that they are parallels
	if(Threshold(dot, 0))
	{
	//Fully contains the test edge
	if(edge.StartVertex.OnEdge(this) && edge.EndVertex.OnEdge(this))
	{
	return edge;
	}
	else if(this.StartVertex.OnEdge(edge) || this.EndVertex.OnEdge(edge))
	{
	gVertex[] vertices = new gVertex[4]
	{
	this.StartVertex,
	this.EndVertex,
	edge.StartVertex,
	edge.EndVertex
	};
	var sorted = vertices.OrderBy(v => v.Y).ThenBy(v => v.X).ThenBy(v => v.Z).ToList();
	return gEdge.ByStartVertexEndVertex(sorted[1], sorted[2]);
	}
	else
	{
	return null;
	}
	}

Dynamo recreation

Shortest Path issue when origin/destination lies on a polygon edge

Add Tolerance input to Threshold methods

Increasing Performance with Convex Hull Approach

Repository works great with basic polygons, but when vertices reach large numbers it takes forever to build the graph. Using convex hull approach will reduce the number of vertices dramatically and improve the performance. In some of my tests, performance improved by 5000%.

Add More Geometries

• Bounding Box
• Circle

Polygon external/internal property to be relational to other polygons

On certain scenarios, a polygon cannot be only categorize as external/internal. One polygon can be external in relation to others inside itself, but internal to other containing it.

A hierarchical representation of polygon's function within a context could be implemented to avoid the black or white representation.