If I have a series of edges that branch and curve, such as in a road network, is there an algorithm that will identify the areas (defined by sequence of geographic points) defined between those lines?



road network


partitioned road network areas

Keeping in mind that the areas can be irregular shapes.

  • 1
    There are several ways to approach this problem. I think you should provide more detail to assist people looking to answer the question. In particular: 1. What format are the lines/edges stored in? (e.g. is it x, y coordinates for start and end points). 2. Is the algorithm run on-the-fly or is it pre-computing values that are looked up at a later date? 3. Do the polygons ever overlap? Are there other complications such as margins of error for the line/edge vertices? – Marvin Mar 16 '16 at 2:19
  • If input is bitmap, use connected component labeling. If input is geometry (vertices), see combinatorial map. If already using a GIS system, see map algebra or the documentation of the system. – rwong Mar 16 '16 at 4:04
  • It is likely that your question has already been asked before and answered on the GIS site (gis.stackexchange.com). If you are using a GIS software, you should be able to get the information easily without implementing your own algorithms. If you are not using a GIS software, it could be difficult, and your question currently did not provide enough detail (see Peter Tòmas Scott's comment) for anyone to write an answer. If you are a software consultant (i.e. you do not plan to implement it yourself), the answer would be "use a GIS software". – rwong Mar 16 '16 at 17:51

What you are looking for is called a "Polygonizer". Unfortunately, the Wikipedia article is currently just a stub, but you can google for this term, which leads you to some free and some commercial implementations.

| improve this answer | |

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.