2
$\begingroup$

I'm developing a CAD drawing generator using C# and netdxf library (https://github.com/haplokuon/netDxf)

The app first performs boolean operations (specifically - union & subtraction) on polygons and draws the resultant path on .dxf file.

I'm using Angus johnson's Clipper library (Clipper - an open source freeware polygon clipping library | angusj.com) for clipping

Everything works fine for polygons, The problem is when I need to clip circles and polygons, the result is a large list of points (representing the path of the figure to be drawn on dxf)

So the curved portion of the path is composed of tiny segments, which is a big problem for the CAM software that'd be used later.

Below is such an image (the result of clipping circle and polygon). The grey portion is full of tiny line segments

enter image description here

Questions -

1) How can I convert those tiny line segments to circles/arcs using the list of points?

2) Can I take a completely different approach to avoid this problem?

Thanks!

Improve this question
$\endgroup$

3 Answers 3

Reset to default
1
$\begingroup$

I don't know how the clipping library you are using returns the clipped objects, but if I understand your question, you want a way to represent your circles that does not use much memory? If you are only using perfect circles (and not ellipses) you could represent each arc segment as simply an origin point, a radius, and a start/stop angle.

This is the part where it would be helpful to know what the clipping library returns. If it returns a chain of points as a separate object for each clipped arc segment, and you already know the radius and center of the circle (from before clipping), you could take the first and last point in the returned chain and compute the angle for each.

atan2(x - origin.x, y - origin.y)

Then when you would like to draw the thing, you can write and algorithm to trace the arc going from the start to stop angle. If you want to do further clipping, you could recreate the arc as a chain of points.

Be careful about whether the returned segment was clockwise or counterclockwise.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The clipping library returns a list of points that make up the above figure. I cant distinguish between points that make up the arc and points that make up the lines. $\endgroup$
    – user3453636
    Dec 18, 2017 at 0:51
  • $\begingroup$ So the dotted purple lines are part of the returned object? Well if the points in the arc are closely packed as you say, you can look at the distance between consecutive points. If that that distance is above some threshold then you can say that you've hit an edge of the arc. $\endgroup$
    – Chuck
    Dec 18, 2017 at 4:17
1
$\begingroup$

If Clipper has the capability of working with tagged edges (i.e. such that you can associate some label to every edge of the input polygons and retrieve these labels after clipping), then you can tag the edges with labels that relate to the individual original primitives (your circular arcs). Then by looking at the labels in the output, you can rebuild the modified arcs and from the endpoints determine the new angular extent. Beware that a single arc could be decomposed in several ones.

If only vertices can be tagged, you can proceed similarly and use the edges having only one vertex with the correct tag, and obtain the arc endpoints from the other side of these edges.

If no tags are possible, you can still perform a geometric matching between the original flattened arcs and the outlines produced by Clipper. In principle, comparison for strict equality should work because Clipper has no reason to alter the coordinates of the original vertices. For efficiency of the matching, a scanline method would be better than exhaustive comparison.

Note that in your example, the discretization of the arc seems too fine. A simple rule is to adjust the discretization so that the distance between the chords and the arc do not exceed a given maximum distance.

Now, after Clipper has computed the approximate intersections between lines and arcs (or between two arcs), if you know the identity of the original primitives, you can recompute the intersections exactly, using analytical formulas, and reconstruct the correct sequence of arcs/lines. As the primitives can intersect at more than one point, use the intersection closest to the Clipper point.

Improve this answer
$\endgroup$
0
$\begingroup$

You cannot use Clipper and expect analytical results. Circle arcs will be composed by line segments. That said, you know your boolean operands so it should be possible and fairly easy to map all line segments back to their origin operand and extract the arcs yourself.

Improve this answer
$\endgroup$
5
  • $\begingroup$ "fairly easy": how so ? $\endgroup$
    – user1703
    Mar 25 at 15:21
  • $\begingroup$ Well, find all intersections between the circle and the polygon's line segments (for the circle parameterized by t), the circle segments will alternate between in and out, one of these you should be able to determine as in or out, and then you're done. Fairly easy. $\endgroup$
    – beyond
    Mar 28 at 7:38
  • $\begingroup$ Well, it seems that you never truly looked at this problem. In the case of just polygons, this is the Weiler-Atherton Polygon Clipping Algorithm. (Clipper implements a variant of that, namely the Vatti algorithm.) Not really a stroll to code due to hard corner cases. And having circles makes it more difficult as two pieces can intersect twice. So that task is harder than re-developing Clipper. $\endgroup$
    – user1703
    Mar 28 at 7:52
  • 1
    $\begingroup$ You're right, I never did. Thanks for correcting me. $\endgroup$
    – beyond
    Mar 28 at 7:54
  • $\begingroup$ For the basic principle, you are quite right. Alternating between sections of both outlines, changing at every intersection. This is clear for segments/arcs in general position, but not otherwise. [Other issue is that of efficiency: for complex shapes, a brute-force search for intersections, taking N.M operations, is not reasonable.] $\endgroup$
    – user1703
    Mar 28 at 7:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.