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?
    – user174739
    Mar 16, 2016 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, 2016 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, 2016 at 17:51

1 Answer 1


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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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