How can I form polygons from lines

Question

I have a bunch of 2-dimensional lines, whose start and end points are known. The lines might occasionally cross each other, or one line might end in the middle of another line. I need to form polygons from this mesh of lines. If necessary, I can ensure that the left side of all lines are inside their polygons.

Answer 1

What you're describing is what we called "parcelization" or "spaghetti cutting", and then "polygonization" when I worked for GeoVision. Basically you want to cut the lines where-ever they intersect other lines and themselves, and then you want to assemble them into polygons by traversing line/node/line until you find a closed polygon.