Problem and questions about LineArrangement

[apirogov]

I am currently trying to port some code I played with from Python that used CGAL bindings to Haskell and it looks like HGeometry has the algorithms I need, which are computing Line Arrangements and Convex Hulls.

import Linear.V2
import qualified Data.Geometry as HG 
import qualified Data.Geometry.Arrangement as HG
import Data.Proxy
import Data.Ext

segToHGLine (V2 x1 y1, V2 x2 y2) = HG.lineThrough (HG.Point2 x1 y1) (HG.Point2 x2 y2)

box = [((V2 0 0),(V2 0 1))
      ,((V2 0 1),(V2 1 1))
      ,((V2 1 1),(V2 1 0))
      ,((V2 1 0),(V2 0 0))
      ,((V2 0 0),(V2 1 1))
      ,((V2 1 0),(V2 0 1))
      ]
arr = HG.constructArrangement (Proxy :: Proxy ()) $ map ((:+ ()) . segToHGLine) box

Now this ends with an error "link: fromJust" when evaluating _unboundedIntersections in GHCI.

1. Am I doing something wrong or is this a bug? I would have expected to get an arrangement that in some way contains the 4 triangles inside the box.

2. What would be the easiest way to extract the polygons (as sequence of points) of the arrangement?

3. With the CGAL bindings I could use line segments for arrangements. It does not look to me that this is possible with HGeometry yet, is this correct? Should I just use constructArrangementInBox with a sufficiently tight box that excludes intersections outside of the regions that I care for, as a workaround for the lacking support for segments?

Thanks in advance!

[noinia]

Thanks for your interest in hgeometry, and sorry for the late reply.

1. I would have to look into this in a bit more detail, but that indeed sounds like a bug. My first guess would be that the current code is not correctly handling degenerate intersections (i.e. three lines intersecting in a single point). (But again I would have to look into this in more detail to be sure).

2. get the PlanarSubdivision from the Arrangement, and then use rawFacePolygons to get the polygons representing the faces. For each polygon you can ask for its vertices and/or outerBoundary depending on what you want exactly.

3. Currently the Arrangement implementation indeed supports only lines, not linesegments. You could try to use the constructArrangementInBox function, but the assumption there is that outside the box there are no intersections/vertices in the arrangement. So that may give you some undesired behaviour. Some alternatives are:

a) build the arrangement of the supportinlines of the segments, and mark the edges that are part of the original input segments (note that this may blow up the space requirement, i.e. it produces an arrangement of O(n^2) size, whereas maybe the segments did not intersect at all, so could have been stored in O(n) space)

b) To build the arrangement of segments you essentially need 2 things; to find the intersections and to build the planar subdivision (after "splitting" segments at intersections). Both these indiviual parts have been implemented. But they still need to be combined.