Offset failure

[timoria21]

Hello,

I have the following offset sample with an open polyline, and I cannot get a proper result; it seems that if I somehow ignore the result of the intersection with the circles of radius equals to the offset performed in dualSliceAtIntersectsForOffset() method (file: polylineoffset.hpp), I can get the wanted result.

Is there a reason that can explain the initial error? What is the main logic behind this circles intersections?

Pseudocode:

List<PlineVertex> pts = new List<PlineVertex>()
{
    new PlineVertex(-18.2193583535761, 0, 0),
    new PlineVertex(-18.2193583535761, -0.1875, 0),
    new PlineVertex(-3.8125, -0.1875, 0),
    new PlineVertex(-2.8125, -0.1875, 0),
    new PlineVertex(-2.8125, -0.174999997019768, 0),
    new PlineVertex(-1.3125, -0.174999997019768, 0),
    new PlineVertex(-1.3125, -0.1875, 0),
    new PlineVertex(-6.12372410773971E-05, -0.187499990000001, 0.414309224131129),
    new PlineVertex(0.1875, 0, 0)
}

Polyline currIsland = new Polyline(false, pts)

OffsetLoopSet loopSet = new cavc.OffsetLoopSet()
Polyline.invertDirection(currIsland)
loopSet.cwLoops.Add(new OffsetLoop(0, currIsland, Polyline.createApproxSpatialIndex(currIsland)))
double offsetDelta = 2e-5

ParallelOffsetIslands alg = new cavc.ParallelOffsetIslands()
OffsetLoopSet offsetResult = alg.compute(loopSet, offsetDelta)

Thanks,

Dave

[jbuckmccready]

The circle intersections at the end points is required to form slices and discard them in cases where the end point of the open polyline wraps back on itself. The reason it chooses this approach is for the following reasons:

1. It ensures the resulting offset is never closer to the original polyline than the offset value given.
2. The resulting offset polyline is not self intersecting if the input polyline was not self intersecting.
3. The "gap" generated is consistent in the case of a self intersecting polyline (e.g., imagine if you offset both directions at the same time by the same amount then it will form a proper "tube" around the input polyline even if the end point wraps back on itself).

See the following example:

Forming a "tube" by offsetting both directions the same amount, one direction is colored blue, the other is colored red. Note the point at which the slices join between the red and blue offset where the arrow points would not exist if the circle intersects were not applied.

This could definitely be an optional thing and the algorithm should still work (there isn't a "right" answer about what it should do at the end points), so if you have a different use case you could change it.

[timoria21]

Thanks,

So in my situation (please, refer to the attached picture) it is safe to assume that, if this circle intersects the raw offset in its exact start/end point, this specific intersection itself could be ignored; is it correct?

[jbuckmccready]

Yes... The algorithm in cavalier contours should probably check for that case and disregard the intersect point as an optimization (the algorithm should still work correctly even with the intersect at the end point).

Based on your example you may have problems due to the offset distance (2e-5) being too close to the default epsilon values (pos_equal-eps = 1e-5 and slice_join_eps = 1e-4).

[timoria21]

Hello again,

for the sake of completeness of this discussion, I managed these cases as follows: do you agree with the proposed change?

template <typename Real>
std::vector<OpenPolylineSlice<Real>>
dualSliceAtIntersectsForOffset(Polyline<Real> const& originalPline,
    Polyline<Real> const& rawOffsetPline,
    Polyline<Real> const& dualRawOffsetPline, Real offset) {
    std::vector<OpenPolylineSlice<Real>> result;
    if (rawOffsetPline.size() < 2) {
        return result;
    }

    StaticSpatialIndex<Real> origPlineSpatialIndex = createApproxSpatialIndex(originalPline);
    StaticSpatialIndex<Real> rawOffsetPlineSpatialIndex = createApproxSpatialIndex(rawOffsetPline);

    std::vector<PlineIntersect<Real>> selfIntersects;
    allSelfIntersects(rawOffsetPline, selfIntersects, rawOffsetPlineSpatialIndex);

    PlineIntersectsResult<Real> dualIntersects;
    findIntersects(rawOffsetPline, dualRawOffsetPline, rawOffsetPlineSpatialIndex, dualIntersects);

    // using map rather than unordered map since we want to construct the slices in vertex index order
    // and we do so by looping through all intersects (required later when slices are stitched
    // together, because slices may not all form closed loops/polylines so must go in order of
    // indexes to ensure longest sitched results are formed)
    std::map<std::size_t, std::vector<Vector2<Real>>> intersectsLookup;

    if (!originalPline.isClosed()) {
        // find intersects between circles generated at original open polyline end points and raw offset
        // polyline
        std::vector<std::pair<std::size_t, Vector2<Real>>> intersects;
        internal::offsetCircleIntersectsWithPline(rawOffsetPline, offset, originalPline[0].pos(),
            rawOffsetPlineSpatialIndex, intersects);
        internal::offsetCircleIntersectsWithPline(rawOffsetPline, offset,
            originalPline.lastVertex().pos(),
            rawOffsetPlineSpatialIndex, intersects);

        for (auto const& pair : intersects) {
            // Keep intersection only if its not a tangent intersection with the raw offset // <---
            if (!Vector2.fuzzyEqual(pair.second, rawOffsetPline[0].pos()) && !Vector2.fuzzyEqual(pair.second, rawOffsetPline.lastVertex().pos())) {
                intersectsLookup[pair.first].push_back(pair.second);
            }
        }
    }

    // ...
}

[jbuckmccready]

Yep, looks right to me, thanks for finding this.