How would I implement the shoelace theorem to find the areas of multiple convex polygons created from intersecting lines?

Question

I am creating a piece of javascript code where it's necessary to identify every polygon created from a number of randomly generated intersecting lines. The following screenshot will give a better explanation of what I'm talking about:

Now, I need to calculate the area of each polygon and return the largest area. The approach I'm taking is to identify every intersection (denoted with red dots) and treat them as a vertex of whichever polygon(s) they belong to. If I can somehow identify which polygon(s) each vertex/intersection belongs to, then arrange the vertices of each polygon in a clockwise direction then it would be simple to apply the shoelace theorem to find the area of each polygon.

However, I'm afraid that I'm completely lost and have tried various (failed) methods to achieve this. What is the best way to compile a list of clockwise-arranged vertices for each polygon? I'm working on acquiring which segments are associated with every given intersection, and I think this is a step in the right direction but I don't know where to go from there. Does this require some vector work?

Answer 1

I can think of one possibility. Here I've labeled each of the vertices.

_{(source: i.imm.io)}

I'm assuming that if you know the lines involved and their intersections, you can find all the line segments that intersect at a particular point. So lets start with a particular point, say K, and a directed segment, IK. Now we have four directed segments that lead from the end of that, KI, KJ, KL, and KM. We are interested only in the two that are closest to, but not on, the line KI. Let's focus on KM, although you can do the same thing with KJ.

(Note that if there are more than two lines intersecting at the point, we can still find the two that are closest to the line, generally one forming a positive angle with the initial segment, the other a negative one.)

We notice that IKM is a positive angle, and then examine the segments containing M, choosing the one with the smallest positive angle with KM, in this case MF, do this again at F (although there are only two choices here) to get FG, and then GH, and then HI, which completes one polygon, the hexagon IKMFGH.

Going back to our original segment of IK, we look at our other smallest angle, IKJ, and do a similar process to find the triangle IKJ. We have now found all the polygons containing IK.

Then of course you do this again, each other segment. You will need to remove duplicates, or be smarter about not continuing to analyze a path when you can see it will be a duplicate. (Each angle will be in at most one polygon, so if you see an angle already recorded, you can skip it.)

This would not work if your polygons weren't convex, but if they are made from lines cut through a rectangle, I'm pretty sure they will always be convex.

I haven't actually tried to code this, but I'm pretty sure it will work.