Boprs/BooleanOperation.cs

#if ACAD24
using Autodesk.AutoCAD.EditorInput;
using Autodesk.AutoCAD.Geometry;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.Colors;
using AcAp = Autodesk.AutoCAD.ApplicationServices;
#elif BCAD
using Bricscad.EditorInput;
using Teigha.Geometry;
using Teigha.DatabaseServices;
using Teigha.Colors;
#endif
using System;
using System.Collections.Generic;

namespace Boprs
{
	/// <summary>
	/// Type of the boolean operation.
	/// </summary>
	public enum BoprType
	{
		/// <summary>
		/// Union.
		/// </summary>
		UNITE,
		/// <summary>
		/// Intersection.
		/// </summary>
		INTERSECT,
		/// <summary>
		/// Difference.
		/// </summary>
		SUBTRACT,
		/// <summary>
		/// Exclusive or.
		/// </summary>
		EXCLUSIVE,
	}

	/// <summary>
	/// Boolean operation on two regions.
	/// </summary>
	public class BooleanOperation
	{
		/// <summary>
		/// Resulting region from the operation.
		/// </summary>
		public Region Result { get; private set; }

		/// <summary>
		/// Subdivide any intersecting edges such that there are no more edge intersections and tag their Type property.
		/// </summary>
		/// <remarks>
		/// <para>
		/// This method will empty the sortedVertices list.
		/// </para>
		/// </remarks>
		/// <param name="sortedVertices">Lexico-graphically sorted vertices of the edges to subdivide.</param>
		/// <returns>Processed edges.</returns>
		private List<SweepEdge> ProcessEdges(List<SweepVertex> sortedVertices)
		{
			// Sweepline to keep track of edges.
			SweepLine sweepLine = new SweepLine();

			// Processed edges will be moved here.
			List<SweepEdge> processed = new List<SweepEdge>();

			// Go through all the sorted vertices, test for intersections when appropriate and,
			// if needed, subdivide the edges.
			while (sortedVertices.Count != 0)
			{
				SweepVertex acVx = sortedVertices[0];
				sortedVertices.RemoveAt(0);

				if (acVx.IsLeft())
				{
					sweepLine.Add(acVx.Edge, true);

					SweepEdge prevEdge = sweepLine.PrevEdge(acVx.Edge);
					SweepEdge nextEdge = sweepLine.NextEdge(acVx.Edge);

					acVx.Edge.SetInsideOther(prevEdge);
					
					if (prevEdge != null)
					{
						List<SweepVertex> newVertices = acVx.Edge.TrySubdivideBy(prevEdge);

						foreach (SweepVertex vertex in newVertices)
						{
							Utils.InsertVertexSorted(sortedVertices, vertex);
						}
					}
					if (nextEdge != null)
					{
						List<SweepVertex> newVertices = acVx.Edge.TrySubdivideBy(nextEdge);

						foreach (SweepVertex vertex in newVertices)
						{
							Utils.InsertVertexSorted(sortedVertices, vertex);
						}
					}
				}
				else
				{
					SweepEdge prevEdge = sweepLine.PrevEdge(acVx.Edge);
					SweepEdge nextEdge = sweepLine.NextEdge(acVx.Edge);
					
					sweepLine.Remove(acVx.Edge);
					processed.Add(acVx.Edge);

					if (prevEdge != null && nextEdge != null)
					{
						List<SweepVertex> newVertices = prevEdge.TrySubdivideBy(nextEdge);

						foreach (SweepVertex vertex in newVertices)
						{
							Utils.InsertVertexSorted(sortedVertices, vertex);
						}
					}
				}
			}

			return processed;
		}

		/// <summary>
		/// Should a given edge be included in the result polygon?
		/// </summary>
		/// <param name="edge">Edge to evaluate.</param>
		/// <param name="subject">Subject region of this operation.</param>
		/// <param name="boprType">Type of the boolean operation.</param>
		/// <returns><c>true</c> if the edge should be included in the result, <c>false</c> if not.</returns>
		private bool IsInResult(SweepEdge edge, Region subject, BoprType boprType)
		{
			switch (edge.Type)
			{
				case EdgeType.NORMAL:
					switch (boprType)
					{
						case BoprType.UNITE:
							return !edge.InsideOther;
						case BoprType.INTERSECT:
							return edge.InsideOther;
						case BoprType.SUBTRACT:
							return (edge.ParentRegion == subject && !edge.InsideOther) || 
								(edge.ParentRegion != subject && edge.InsideOther);
						case BoprType.EXCLUSIVE:
							return true;
					}
					break;
				case EdgeType.OVERLAP_SAME:
					return boprType == BoprType.INTERSECT || boprType == BoprType.UNITE;
				case EdgeType.OVERLAP_DIFFERENT:
					return boprType == BoprType.SUBTRACT;
				case EdgeType.OVERLAP_SILENT:
					return false;
			}
			return false;  // Just to avoid compiler warning.
		}

		/// <summary>
		/// Build the result polygon from processed edges.
		/// </summary>
		/// <param name="edges">Input edges.</param>
		/// <param name="subject">Subject region of this operation.</param>
		/// <param name="boprType">Type of boolean operation.</param>
		/// <returns>Built result region.</returns>
		private Region BuildResult(List<SweepEdge> edges, Region subject, BoprType boprType)
		{
			List<LineSegment2d> chosenSegments = new List<LineSegment2d>();

			foreach(SweepEdge edge in edges)
			{
				if(IsInResult(edge, subject, boprType))
				{
					chosenSegments.Add(new LineSegment2d(edge.LeftVertex.Point, edge.RightVertex.Point));
				}
			}

			return Region.FromSegments(chosenSegments);
		}

		/// <summary>
		/// Compute a boolean operation on two regions.
		/// </summary>
		/// <param name="subject">Subject region.</param>
		/// <param name="clip">Clip region.</param>
		/// <param name="type">Boolean operation type.</param>
		public BooleanOperation(Region subject, Region clip, BoprType type)
		{
			List<SweepVertex> sortedVerts = new List<SweepVertex>();
			
			foreach (SweepEdge edge in subject.GetEdgeCopies())
			{
				sortedVerts.Add(edge.LeftVertex);
				sortedVerts.Add(edge.RightVertex);
			}
			foreach (SweepEdge edge in clip.GetEdgeCopies())
			{
				sortedVerts.Add(edge.LeftVertex);
				sortedVerts.Add(edge.RightVertex);
			}
			
			sortedVerts.Sort();

			List<SweepEdge> processed = ProcessEdges(sortedVerts);
			
			Result = BuildResult(processed, subject, type);
		}
	}
}