Return to Question

I'm trying to implement a Billouin-Zone algorithm within mathematica including the generation of Brillouin zones of higher order in 2D and 3D. There is a nice implementation of generating these zones in the Mathematica GuideBook for Graphics. However this implementation uses the brute force approach in calculating line segment intersections of order O(n²) with n number of lines:

intersectionPoint[{{p1x_, p1y_}, {r1x_, r1y_}},  {{p2x_, p2y_}, {r2x_, r2y_}}, maxDist_] := Module[{aux}, If[PossibleZeroQ[r1y r2x - r2y r1x], Sequence @@ {}, aux = {p1x + (r1x (p1y r2x - p2y r2x - p1x r2y + p2x r2y))/(r1x r2y - r1y r2x), p1y + (r1y (p1y r2x - p2y r2x - p1x r2y + p2x r2y))/(r1x r2y - r1y r2x)} // N; If[Simplify[aux.aux] <= maxDist && IntervalMemberQ[ IntervalIntersection[Interval[{p1x, p1x + r1x}], Interval[{p2x, p2x + r2x}]], aux[[1]]] && IntervalMemberQ[ IntervalIntersection[Interval[{p1y, p1y + r1y}], Interval[{p2y, p2y + r2y}]], aux[[2]]], aux, Sequence @@ {}]]] 

I'm sure there are a lot of improvements to above code, but the fact persists that the order will be of O(n²). Since the line intersection for the Brillouin zone algorithm for high order zones in 3D is the by far most costly step I'm looking into smarter approaches to find intersecting line segments. The very smart algorithm by Balaban entitled An optimal algorithm for finding segments intersections is achieving an order of at least O(n log(n)). However the algorithm involves a rather complex binary search tree implementation. Since mathematica has very efficient search implementations within lists already natively supported, I wonder if someone has implemented the Balaban or equivalent sweep line and sweep plane algorithms within mathematica taking advantage of the built in mathematica search functions? I'm especially interested in a 2D AND an 3D implementation of a line segment intersection within mathematica.

Many thanks in advance for any help!

I'm trying to implement a Brillouin Zone algorithm within Mathematica, including the generation of Brillouin zones of higher order in 2D and 3D. There is a nice implementation of generating these zones in the Mathematica Guidebook for Graphics. However, this implementation uses the brute force approach in calculating line segment intersections of order $\mathcal O(n^2)$ with $n$ number of lines:

intersectionPoint[{{p1x_, p1y_}, {r1x_, r1y_}}, {{p2x_, p2y_}, {r2x_, r2y_}}, maxDist_] := Module[{aux}, If[PossibleZeroQ[r1y r2x - r2y r1x], Sequence @@ {}, aux = {p1x + (r1x (p1y r2x - p2y r2x - p1x r2y + p2x r2y))/(r1x r2y - r1y r2x), p1y + (r1y (p1y r2x - p2y r2x - p1x r2y + p2x r2y))/(r1x r2y - r1y r2x)} // N; If[Simplify[aux.aux] <= maxDist && IntervalMemberQ[ IntervalIntersection[Interval[{p1x, p1x + r1x}], Interval[{p2x, p2x + r2x}]], aux[[1]]] && IntervalMemberQ[ IntervalIntersection[Interval[{p1y, p1y + r1y}], Interval[{p2y, p2y + r2y}]], aux[[2]]], aux, Sequence @@ {}]]] 

I'm sure there are a lot of improvements to above code, but the fact persists that the order will be of $\mathcal O(n^2)$. Since the line intersection for the Brillouin zone algorithm for high order zones in 3D is by far the most costly step, I'm looking into smarter approaches to find intersecting line segments. The very smart algorithm by Balaban entitled An optimal algorithm for finding segments intersections achieves an order of at least $\mathcal O(n\log\,n)$. However, the algorithm involves a rather complex binary search tree implementation. Since Mathematica has very efficient search implementations within lists already natively supported, I wonder if someone has implemented the Balaban or equivalent sweep line and sweep plane algorithms within Mathematica that takes advantage of the built-in Mathematica search functions? I'm especially interested in a 2D and a 3D implementation of a line segment intersection within Mathematica.

Many thanks in advance for any help!