geri-borbas/unity.library.eppz.geometry

2D Geometry for Unity. Suited for everyday polygon hassle. Polygon clipping, polygon winding direction, polygon area, polygon centroid, centroid of multiple polygons, line intersection, point-line distance, segment intersection, polygon-point containment, polygon triangulation, polygon Voronoi diagram, polygon offset, polygon outline, polygon buffer, polygon union, polygon substraction, polygon boolean operations, and more. It is a polygon fest.

eppz! Geometry

part of Unity.Library.eppz

📐 2D geometry for Unity. Suited for everyday polygon hassle.

Polygon clipping, polygon winding direction, polygon area, polygon centroid, centroid of multiple polygons, line intersection, point-line distance, segment intersection, polygon-point containment, polygon triangulation, polygon Voronoi diagram, polygon offset, polygon outline, polygon buffer, polygon union, polygon substraction, polygon boolean operations, and more.

The library is being used in production. However, it comes with the disclaimed liability and warranty of MIT License.

Examples

If you prefer to read example code immediately, you can find example scenes in Scenes folder.

• Polygon-Point containment
• Polygon-Segment intersection test
• Polygon permiter-Point containment (Precise)
• Polygon permiter-Point containment (Default)
• Polygon-Segment containment
• Polygon-Polygon containment
• Vertex facing
• Polygon area, Polygon winding
• Segment-Segment intersection point
• Polygon offset
• Multiple polygon centroid
• Polygon triangulation

Model classes

• Vertex.cs
  • Basically a Vector2 point, but is aware of the polygon context it resides (neighbours, segments, edges, polygon, bisector, normal).
• Segment.cs
  • Segment of two Vector2 point. Carries out basic geometry features (point distance, point containment, segment intersection).
• Edge.cs
  • Edge of two Vertex in a polygon (a special Segment subclass). Likewise vertices, this model is also aware of the polygon context it resides (neighbours, segments, edges, polygon, perpendicular, normal).
• Polygon.cs
  • The role player, it really embodies mostly every feature of this library. Basically a polygon made of vertices.
  • Can be created with point array, transforms, Source.Polygon components. Further polygons can be embedded into recursively. Vertices, edges, polygons can be enumerated (recursively).
  • Area, winding direction, centroid are being calculated. Also carries the basic geometry features (point containment, line-, segment-, polygon intersection and more).
  • Using library modules, it implements polygon offset (outline), union polygon (polygon clipping), basic mesh triangulation. It implements conversion to both Clipper and Triangle.NET, so you can implement further integration with those (awesome) libraries.

Geometry.cs

Most of the basic 2D geometry algorithm collection is implemented in this static base class. You can (mostly) use them with Unity Vector2 types directly, so (almost entirely) without the model classes introduced above.

• Point
  • ArePointsEqualWithAccuracy()
    • Determine if points are equal with a given accuracy.
  • ArePointsCCW()
    • Determine winding direction of three points.
• Rect / Bounds
  • IsRectContainsRectSizeWithAccuracy()
    • Determine if rect2.size fits into rect1 (compare sizes only).
  • IsRectContainsRectWithAccuracy()
    • Determine if rect2 is contained by rect1 (even if permiters are touching) with a given accuracy.
• Line
  • IntersectionPointOfLines()
    • Returns intersection point of two lines (defined by segment endpoints). Returns zero, when segments have common points, or when a segment point lies on other.
  • PointDistanceFromLine()
    • Determine point distance from line (defined by segment endpoints).
• Segment
  • PointIsLeftOfSegment()
    • Determine if a given point lies on the left side of a segment (line beneath).
  • AreSegmentsEqualWithAccuracy()
    • Determine if segments (defined by endpoints) are equal with a given accuracy.
  • HaveSegmentsCommonPointsWithAccuracy()
    • Determine if segments (defined by endpoints) have common points with a given accuracy.
  • AreSegmentsIntersecting()
    • Determine if two segments defined by endpoints are intersecting (defined by points). True when the two segments are intersecting. Not true when endpoints are equal, nor when a point is contained by other segment. Credits to Bryce Boe (@bboe) for his writeup Line Segment Intersection Algorithm.
• Polygon (using EPPZ.Geometry.Polygon)
  • IsPolygonContainsPoint()
    • Test if a polygon contains the given point (checks for sub-polygons recursive). Uses the same Bryce boe algorithm above, so considerations are the same. See Point in polygon for more.
  • CentroidOfPolygons()
    • Returns the compound centroid of multiple polygon using Geometric decomposition.

Modules

For clipping, offsetting, triangulating the library use these brilliant third party C# libraries below.

• Clipper

  • Polygon and line clipping and offsetting library (C++, C#, Delphi) by Angus Johnson. See standalone project repository Clipper for details.

• Triangle.NET

  • Triangle.NET generates 2D (constrained) Delaunay triangulations and high-quality meshes of point sets or planar straight line graphs. It is a C# port by Christian Woltering of Jonathan Shewchuk's Triangle software. See standalone project repository Triangle.NET for details.

Naming

The library uses namespaces heavily. I like to name things as they are. An edge in this library called Edge, a polygon is called Polygon. If it is a polygon model, it resides the Model namespace (EPPZ.Geometry.Model actually). Whether it is a source component for polygon, it resides in the Source namespace. It becomes nicely readable, as you declare polygons like Model.Polygon, or reference polygon sources as Source.Polygon.

In addition, every class is namespaced in the folder it resides. If you look at a folder name, you can tell that classes are namespaced to the same as the folder name.

Add-ons

• ClipperAddOns

  • Mainly Polygon extensions for easy conversion between eppz! Geometry and Clipper. It has a method to convert from generic Vector2[] array. Clipper works with integers. So conversion involves a scale up (and a scale down), thus you'll need to pass a scale value to Clipper. (for example eppz! Geometry internals use 10e+5f by default).
    • Polygon PolygonFromClipperPaths(Paths paths, float scale)
    • Polygon PolygonFromClipperPath(Path path, float scale)
    • Paths ClipperPaths(this Polygon this_, float scale)
    • Path ClipperPath(this Polygon this_, float scale)
    • Vector2[] PointsFromClipperPath(Path path, float scale)

• TriangleNetAddOns

  • Bridges the gap between library Model.Polygon objects and Triangle.NET models (meshes, voronoi diagrams).
    • TriangleNet.Geometry.Polygon TriangleNetPolygon(this Polygon this_)
    • Rect Bounds(this TriangleNet.Voronoi.Legacy.SimpleVoronoi this_)
    • Paths ClipperPathsFromVoronoiRegions(List<TriangleNet.Voronoi.Legacy.VoronoiRegion> voronoiRegions, float scale = 1.0f)
    • Vector2 VectorFromPoint(TriangleNet.Geometry.Point point)
    • Vector2[] PointsFromVertices(ICollection<TriangleNet.Geometry.Point> vertices)

• UnityEngineAddOns

  • Contains a single Model.Polygon (yet enormously useful) extension that triangulates the corresponding polygon, and hooks up the result into a UnityEngine.MeshFilter component. This is the core functionality embedded into Source.Mesh component (see example scene Polygon triangulation for more).
    • UnityEngine.Mesh Mesh(this EPPZ.Geometry.Model.Polygon this_, string name = "")
    • UnityEngine.Mesh Mesh(this EPPZ.Geometry.Model.Polygon this_, TriangulatorType triangulator, string name = "")
    • UnityEngine.Mesh Mesh(this EPPZ.Geometry.Model.Polygon this_, Color color, TriangulatorType triangulator, string name = "")

License

Licensed under the MIT License.

unity.library.eppz.geometry's Issues

Erro when add package from git URL

Hi Borbas,

Thanks for the amazing polygon operations! I am a green hand on unity. I would love to try this great library EPPZ. But it seems that directly download the [Unity.Library.eppz-master.zip] or add the depository by URL at unity package manager is not working. I keep getting this erro(picture). Is that because I do not have the MIT licence?

Thanks agian and looking forward to your reply!

Kind regards,
Qim

Singleton LineRendererCamera Not Initialised — Unity 2019.3

Trying this library out as it looks very helpful! But I'm hitting an error when running all the example scenes.

NullReferenceException: Object reference not set to an instance of an object EPPZ.Lines.LineRendererCamera.AddDirectRenderer (EPPZ.Lines.DirectLineRenderer renderer) (at Assets/22. Assets — 3rd Party/Unity.Library.eppz/Unity.Library.eppz.Lines/LineRendererCamera.cs:51) EPPZ.Lines.DirectLineRenderer.Awake () (at Assets/22. Assets — 3rd Party/Unity.Library.eppz/Unity.Library.eppz.Lines/DirectLineRenderer.cs:32)

This seems to be some failure to initialise the singleton?

To get the library working I also added Unity.Library.eppz.Lines and the required define symbol. And I thought the singleton issue might be related to the missing execution order utility, so I also added Unity.Library.eppz.Utils, but this did not correct the above error.

Unity 2019.3.7f1
macOS 10.15.5

Polygon subtraction

Great stuff you got here! Just one question, you mention in the description that you can perform subtraction. Is it possible to subtract one polygon from another as shown in the picture below? So far i have only managed to do an XOR.

Thanks!

Sort vertices clockwise

I have irregular vertices and i want to sort them CW or CCW. What is the generalized method to do it. Any suggestions please?

Missing dependencies

Error I am getting after importing your library.

Assets/Plugins/eppz!/Geometry/Scenes/Controllers/Controller_1.cs(33,10): error CS0246: The type or namespace name `SegmentLineRenderer' could not be found. Are you missing an assembly reference?