Determining the 'outer' subpath in a compound SVG path

Question

The following four SVG paths render the same (using the default fill-rule="nonzero"):

<path id="cwOccwI" d="M0,0 10,0 10,10zM5,2 8,5 8,2z" transform="translate( 0,0)"/>
<path id="ccwOcwI" d="M0,0 10,10 10,0zM5,2 8,2 8,5z" transform="translate(15,0)"/>
<path id="ccwIcwO" d="M5,2 8,5 8,2zM0,0 10,0 10,10z" transform="translate(30,0)"/>
<path id="cwIccwO" d="M5,2 8,2 8,5zM0,0 10,10 10,0z" transform="translate(45,0)"/>

As hinted at by the IDs, these are combinations of clockwise (cw) and counter-clockwise (ccw) orientations for the outer (O) and inner (I) subpaths, varying the order the subpaths are added.

I'm converting SVG paths to GeoJSON. It requires a single 'positive' subpath that is oriented counter-clockwise, and any/all 'hole' subpaths to be oriented clockwise.

Given an SVG path with subpaths (which I can assume/guarantee will not overlap), how can I determine which subpath(s) are 'positive' paths, and which are 'holes'? As shown above, I cannot rely on the orientation of the points within the path, and I cannot rely on the ordering of sub-paths.

Answer 1

If you can assume the subpaths are non-intersecting (and non-self-intersecting), and that the fill rule is always the nonzero rule, the easiest way is probably to pick the first point on the first subpath, and do a standard point-in-polygon test with the polygons defined by each other subpath. If the point is not inside any other subpath, then this subpath is the outermost one. If the point is inside one other subpath, that one must be the outermost one. If the point is inside more than one other subpath, take the set of subpaths it is inside and repeat the test.

Obviously doing it this way requires that there is only one outermost subpath. It's entirely possible in SVG to have multiple disjoint subpaths in one path, and you didn't say whether this is possible in your source data. If it is possible, then you'll have to test every subpath to find out which other subpath(s) it is inside. Each time you run the point-in-polygon test, you find the subpath you're considering is either an outermost one, or you'll find out which subpath it is inside. If it's inside another path, you don't need to consider it in any further tests. At the end, you have a list of outermost subpaths, each of which has a list of all the subpaths it encloses. You can turn each outermost subpath into a separate GeoJSON polygon.