getting three resultant paths from two intersecting paths

Question

I have two intersecting paths in a xy plane see image.

A path is defined by a set of points in order so that every two consecutive points form an edge of path. Paths are always closed. Points are flagged to indicated that whether they from edges or curve. I am trying to write a function to get three paths as following.

I tried the following.

create temp path Object path_C
go through every edge in path_A
    go through every edge in path_B
        if current edge of path_A intersects edge of path_B
        find the intersection
        store the intersection point in path_C
    inner loop ends here
outer loop ends here
go through every point in path_A
   if a point lies within the path_B 
   add it to the path_C
   and remove it from path_A 
end of loop
go through every point in path_B
   if a point lies within the path_A 
   add it to the path_C
   and remove it from path_B
end the loop

before I could run it one of my friend pointed out that there is no guarantee that path_C has got the points in correct order. Now I can't figure out how can I fix this problem. If you can suggest some optimizations that will be even better.

Side note : I am actually trying to implement the divide feature in adobe illustrator's pathfinder panel.

Do you realize that the result might be more than 3 regions – Niklas B. Oct 14 '15 at 19:30 — Niklas B., Oct 14 '15 at 19:30
Oh! How did I miss that. Btw thanks for pointing out. – Sayam Qazi Oct 15 '15 at 08:01 — Sayam Qazi, Oct 15 '15 at 08:01

score 0 · Accepted Answer · edited May 23 '17 at 12:29

The terminology you looking for is a "graph cycle", look at this stack overflow thread: finding all cycles in graph. Basically you want to construct a graph from the two paths. This is done by joining two paths (bring all their edges and verts), and introducing new vertices on each point of intersection. The point of intersection is where the graphs will merge. During implementation, consider all the edge cases, i.e. intersection can happen between an edge going through a vertex, colinear edges/verts, etc. Also note, that for certain shapes, like say U shape and a rectangle, can produce several cycles.

getting three resultant paths from two intersecting paths

1 Answers1