Change Details

Currently, the program is able to find all the intersection points. After this, for the boolean operations, there are three possible alternatives, namely: # Greiner-Hormann Algorithm # flattening the curve and later substituting it back using a trick # Using the line-curve intersection algorithm within Qt's implementation All of the above approaches have their pros and cons. # **Greiner-Hormann**: As per the [[ https://en.wikipedia.org/wiki/Greiner%E2%80%93Hormann_clipping_algorithm | wikipedia page ]] it supports parametric curves, making it the only to explicitly do so. This algorithm is pretty simple to implement in it's original form. However it has several disadvantages. It fails to work properly if there are common edges, or an intersection point coinciding with another vertex. Most of these problems can be solved by some preprocessing methods where we flag the degenerate cases and handle them separately. This method is covered in [[ http://www.cad-journal.net/files/vol_3/CAD_3(1-4)_2006_447-456.pdf | this paper ]], however still has a problem where it can't evaluate the result if the intersection point of two separate paths coincides with a point of self intersection of a curve. This is a potential regression, which can only be resolved by breaking down the self intersecting path into smaller, non-intersecting paths. This can be done, however will require additional code (modified to accept curves).

Currently, the program is able to find all the intersection points. After this, for the boolean operations, there are three possible alternatives, namely: # Greiner-Hormann Algorithm # flattening the curve and later substituting it back using a trick # Using the line-curve intersection algorithm within Qt's implementation All of the above approaches have their pros and cons. # **Greiner-Hormann**: As per the [[ https://en.wikipedia.org/wiki/Greiner%E2%80%93Hormann_clipping_algorithm | wikipedia page ]] it supports parametric curves, making it the only to explicitly do so. This algorithm is pretty simple to implement in it's original form. However it has several disadvantages. It fails to work properly if there are common edges, or an intersection point coinciding with another vertex. Most of these problems can be solved by some preprocessing methods where we flag the degenerate cases and handle them separately. This method is covered in [[ http://www.cad-journal.net/files/vol_3/CAD_3(1-4)_2006_447-456.pdf | this paper ]], however still has a problem where it can't evaluate the result if the intersection point of two separate paths coincides with a point of self intersection of a curve. This is a potential regression, which can only be resolved by breaking down the self intersecting path into smaller, non-intersecting paths. This can be done, however will require additional code (modified to accept curves). Still, there is no assurance this method will work properly, as there are several components in the default Qt classes which aren't considered here, which could lead to potential issues. # **flattening**: The basic idea is to flatten the curves and then find the overlapping areas and let Qt do it's thing. However, this will lead to inaccuracy. For this, I thought of a small trick. First, we find all the points of intersection. Then, we split the curve or line about the point of intersection. We split the elements about every intersection point. Thus, we end up with a shape which has no more intersection points left, but only common vertices. Now, if we were to flatten the curves, we would be getting the fill areas. As there are no more intersection points left, it will be absolutely accurate. Then, we iterate through the new shape, replacing the flattening polygon by the actual curve. The only possible issue is if a polygon lies extremely close on the interior of a curve, where although the curve does not truly intersect the polygon, it might seem like so. However, this is not a regression, and it can be easily tackled by setting tolerance values. There will be an overhead, but it shouldn't be that much. (//curve-curve intersections are pretty expensive one takes 250 microsecs on an average. Qt requires 300 microsecs to perform the entire routine for a rounded rectangle- ellipse boolean operation.//) # **using curve-line intersection**: Qt's algorithm doesn't work with curves by default. However the original idea can be extended for curves. It is pretty similar to Vatti's algorithm and essentially relies on horizontal scanlines. Since we can find intersection points, we can get it to work with even-odd rule and find the areas. I had a few concerns regarding its efficiency, however the algorithm ( for horizontal line-curve intersections ) requires 10 microsecs at most. This seems to be a good approach as opposed the previous one, as we still maintain the curve as a curve. However, there will be some extra overhead. If the overhead isn't too much, this could be preferred. If it too much, I believe the second option to be better.

Currently, the program is able to find all the intersection points. After this, for the boolean operations, there are three possible alternatives, namely: # Greiner-Hormann Algorithm # flattening the curve and later substituting it back using a trick # Using the line-curve intersection algorithm within Qt's implementation All of the above approaches have their pros and cons. # **Greiner-Hormann**: As per the [[ https://en.wikipedia.org/wiki/Greiner%E2%80%93Hormann_clipping_algorithm | wikipedia page ]] it supports parametric curves, making it the only to explicitly do so. This algorithm is pretty simple to implement in it's original form. However it has several disadvantages. It fails to work properly if there are common edges, or an intersection point coinciding with another vertex. Most of these problems can be solved by some preprocessing methods where we flag the degenerate cases and handle them separately. This method is covered in [[ http://www.cad-journal.net/files/vol_3/CAD_3(1-4)_2006_447-456.pdf | this paper ]], however still has a problem where it can't evaluate the result if the intersection point of two separate paths coincides with a point of self intersection of a curve. This is a potential regression, which can only be resolved by breaking down the self intersecting path into smaller, non-intersecting paths. This can be done, however will require additional code (modified to accept curves). Still, there is no assurance this method will work properly, as there are several components in the default Qt classes which aren't considered here, which could lead to potential issues. # **flattening**: The basic idea is to flatten the curves and then find the overlapping areas and let Qt do it's thing. However, this will lead to inaccuracy. For this, I thought of a small trick. First, we find all the points of intersection. Then, we split the curve or line about the point of intersection. We split the elements about every intersection point. Thus, we end up with a shape which has no more intersection points left, but only common vertices. Now, if we were to flatten the curves, we would be getting the fill areas. As there are no more intersection points left, it will be absolutely accurate. Then, we iterate through the new shape, replacing the flattening polygon by the actual curve. The only possible issue is if a polygon lies extremely close on the interior of a curve, where although the curve does not truly intersect the polygon, it might seem like so. However, this is not a regression, and it can be easily tackled by setting tolerance values. There will be an overhead, but it shouldn't be that much. (//curve-curve intersections are pretty expensive one takes 250 microsecs on an average. Qt requires 300 microsecs to perform the entire routine for a rounded rectangle- ellipse boolean operation.//) # **using curve-line intersection**: Qt's algorithm doesn't work with curves by default. However the original idea can be extended for curves. It is pretty similar to Vatti's algorithm and essentially relies on horizontal scanlines. Since we can find intersection points, we can get it to work with even-odd rule and find the areas. I had a few concerns regarding its efficiency, however the algorithm ( for horizontal line-curve intersections ) requires 10 microsecs at most. This seems to be a good approach as opposed the previous one, as we still maintain the curve as a curve. However, there will be some extra overhead. If the overhead isn't too much, this could be preferred. If it too much, I believe the second option to be better.