Given a general polyline and an orthogonal grid, I would like to compute a simpler polyline whose vertices lie on the grid edges/vertices. This can look like this:
(Sorry about the link to the image, but stack overflow apparently doesn't allow me to embed pictures before getting 10 credit points).
The grid is always orthogonal but its vertices do not necessarily have integer coordinates as some x or y lines might have coordinates defined by a previous geometric intersection computation. The initial curve can be represented as a polyline (though it would be nice to have also bezier curve support), not necessarily x-monotone, and it might intersect the grid also along whole edges.
My first thought was to call CGAL::compute_subcurves(..) with the grid lines and the curve I'm adding. I was hoping to get back a list of polylines, each composed of maximal multiple segments inside a face of the original grid. In practice even if the input is composed of polylines and the output of monotone polylines, I get back a list of separated segments. These include also the grid segments and also the polyline segments, and these are not ordered by "walking on the curve segments" as needed to compute the ordered interesection points. If they would have been ordered, a solution would be to iteratively go over them and check which one intersects the original grid, and then save the points.
Another option I thought of is to start with an arrangement of the grid lines, incrementally add polyline segements and have a notification mechanism notifying me on new edges that are pairwise disjoint in their interior, but in the case an edge of the intersected polylines is an original edge of the grid I won't get a notification and I'll miss it. Incrementally adding segments and checking for collisions also doesn't seem to be straightforward as the arrangement API do_intersect(..) seems to return at most a single point, while a given segment of the input polyline might easily intersect two grid lines next to a corner or even lie entirely on a grid segment.
I'm probably missing some simple solution. Can someone give me a pointer, or some api call that might help here?
Edit: There might have been a confusion. The grid is orthogonal but not necessarily regular and might have coordinates that could not globally scale to integers such as here.
Use Arrangement_with_history_2 (instead of Arrangement_2); see https://doc.cgal.org/latest/Arrangement_on_surface_2/classCGAL_1_1Arrangement__with__history__2.html. After you compute the arrangement, you can use point location to locate the end points of your polylines in the arrangement. Then, for each one, you can easily follow the original curve. If you are concerned with performance, you can try inserting (at least) the grid lines incrementally. Another option is to extend the halfedge records and insert the grid lines and each polyline separately. With the appropriate observer, you can mark the generated halfedges that correspond to a given polyline uniquely. I think you can even save the extra point location, by locating one of the two end points of a polyline before inserting it, and then provide the resulting location to the (incremental) insertion function.
