Given a collection of lines and a point how can I discover the closest boundary around the point. In the image below A represents a collection of disconnected lines and B is the boundary I want to discover. There may be lines that not connected or it might be that the point is not actually enclosed at all and so the operation should fail. I am looking for some algorithms I might consider. My initial thought was to find all intersections and then create a point cloud but I am not sure where I would go from there or if that would be the best way to go.

Find Boundary from lines and a point

  • What software are you using? – smiller Nov 21 '18 at 20:01

This operation is commonly called Polygonize, which takes one or more vector lines layers and identifies all of the polygons formed by the intersections of the input features. This operation is fairly common in GIS software. For example, QGIS contains a Polygonize tool, if you are looking for an open-source implementation. I have also added a Polygonize tool to the open-source WhiteboxTools geospatial library (source code found here; more information here), which was used in the example below.

As an example, here are two overlapping vector layers, one is a road network (7400 features) and the other is a stream network (3800 features):

enter image description here

The output of the polygonize operation is as follows:

enter image description here

Each of the 4400 polygons formed by the intersection of features in the input vector layers is output. The operation took 3.7 seconds on my Macbook, so polygonization is a fairly efficient GIS operation, depending on the input data.

Once you've polygonized the lines, you can probably use vector intersection to identify which polygons contain points.

  • This is exactly what I was looking for. Thanks so much. – Jonathan Wagner Nov 21 '18 at 21:10
  • @JonathanWagner I'm glad I could help out. – WhiteboxDev Nov 21 '18 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.