| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.sis.internal.processing.isoline; |
| |
| import java.awt.Point; |
| import java.util.Map; |
| import java.util.Arrays; |
| import java.util.ArrayList; |
| import java.util.Collections; |
| import org.apache.sis.internal.util.Numerics; |
| |
| |
| /** |
| * List of {@code PolylineBuffer} coordinates that have not yet been closed. |
| * Each {@code double[]} in this list is a copy of a {@link PolylineBuffer} used by {@link Tracer.Level}. |
| * Those copies are performed for saving data before they are overwritten by next iterated cell. |
| * |
| * <h2>List indices and ordering of points</h2> |
| * For a given {@code Fragments} list, all {@code double[]} arrays at even indices shall have their points read |
| * in reverse order and all {@code double[]} arrays at odd indices shall have their points read in forward order. |
| * The list size must be even and the list may contain null elements when there is no data in the corresponding |
| * iteration order. This convention makes easy to reverse the order of all points, simply by reversing the order |
| * of {@code double[]} arrays: because even indices become odd and odd indices become even, points order are |
| * implicitly reverted without the need to rewrite all {@code double[]} array contents. |
| * |
| * @author Martin Desruisseaux (Geomatys) |
| * @version 1.3 |
| * |
| * @see Tracer.Level#partialPaths |
| * |
| * @since 1.1 |
| * @module |
| */ |
| @SuppressWarnings({"CloneableImplementsClone", "serial"}) // Not intended to be cloned or serialized. |
| final class Fragments extends ArrayList<double[]> { |
| /** |
| * The first points and last point in this list of polylines. By convention the coordinate having fraction |
| * digits has all its bits inverted by the {@code ~} operator. May be {@code null} if a coordinate is NaN. |
| * Do not modify {@link Point} field values, because those instances are keys in {@link Tracer.Level#partialPaths}. |
| */ |
| private Point firstPoint, lastPoint; |
| |
| /** |
| * Creates a list of polylines initialized to the given items. |
| * The given polylines and their opposite directions are cleared by this method. |
| * |
| * @param polylineOnLeft first polyline with points in forward order. Shall not be null. |
| * @param polylineOnTop next polyline with points in reverse order, or {@code null} if none. |
| */ |
| Fragments(final PolylineBuffer polylineOnLeft, final PolylineBuffer polylineOnTop) { |
| /* |
| * Search for first and last point by inspecting `PolylineBuffer` instances in the order shown below. |
| * The first 4 rows and the last 4 rows search for first point and last point respectively. |
| * The empty rows in the middle are an intentional gap for creating a regular pattern that |
| * we can exploit for 3 decisions that need to be done during the loop: |
| * |
| * ✓ (index & 2) = 0 if using `polylineOnLeft` (otherwise `polylineOnTop`). |
| * ✓ (index % 3) = 0 if using `opposite` value of polyline (may be null). |
| * ✓ (index & 1) = 0 if fetching last point (otherwise fetch first point). |
| * |
| * Index PolylineBuffer (order) !(i & 2) !(i % 3) !(i & 1) Comment |
| * ──────────────────────────────────────────────────────────────────────────── |
| * [0] polylineOnLeft.opposite (←) ✓ ✓ ✓ (1) |
| * [1] polylineOnLeft (→) ✓ (2) |
| * [2] polylineOnTop (←) ✓ (1) |
| * [3] polylineOnTop.opposite (→) ✓ (2) |
| * [4] ✓ ✓ |
| * |5] ✓ |
| * [6] polylineOnTop.opposite (→) ✓ ✓ (3) |
| * [7] polylineOnTop (←) (4) |
| * [8] polylineOnLeft (→) ✓ ✓ (3) |
| * [9] polylineOnLeft.opposite (←) ✓ ✓ (4) |
| * |
| * Comments: |
| * (1) Last `PolylineBuffer` point is first `Fragments` point because of reverse iteration order. |
| * (2) First `PolylineBuffer` point is first `Fragments` point because of forward iteration order. |
| * (3) Last `PolylineBuffer` point is last `Fragments` point because of forward iteration order. |
| * (4) First `PolylineBuffer` point is last `Fragments` point because of reverse iteration order. |
| */ |
| int index = 0; |
| do { |
| PolylineBuffer polyline = ((index & 2) == 0) ? polylineOnLeft : polylineOnTop; // See above table (column 4). |
| if (index % 3 == 0 && polyline != null) polyline = polyline.opposite; // See above table (column 5). |
| if (polyline != null) { |
| int n = polyline.size; |
| if (n != 0) { |
| final double[] coordinates = polyline.coordinates; |
| final double x, y; |
| if (((index & 1) == 0)) { // See above table in comment (column 6). |
| y = coordinates[--n]; |
| x = coordinates[--n]; |
| } else { |
| x = coordinates[0]; |
| y = coordinates[1]; |
| } |
| final boolean isLastPoint = (index >= 6); // See row [6] in above table. |
| if (Double.isFinite(x) && Double.isFinite(y)) { |
| final Point p = new Point((int) x, (int) y); |
| if (!Numerics.isInteger(x)) p.x = ~p.x; |
| if (!Numerics.isInteger(y)) p.y = ~p.y; |
| if (isLastPoint) { |
| lastPoint = p; |
| break; // Done searching both points. |
| } |
| firstPoint = p; |
| } else if (isLastPoint) { |
| /* |
| * If the last point was NaN, check if it was also the case of first point. |
| * If yes, we will not be able to store this `Fragments` in `partialPaths` |
| * because we have no point that we can use as key (it would be pointless |
| * to search for another point further in the `coordinates` array because |
| * that point could never be matched with another `Fragments`). Leave this |
| * list empty for avoiding the copies done by `take(…)` calls. Instead, |
| * callers should write polylines in `Tracer.Level.path` immediately. |
| */ |
| if (firstPoint == null) return; |
| break; |
| } |
| /* |
| * Done searching the first point (may still be null if that point is NaN). |
| * Row [6] in above table is the first row for the search of last point. |
| */ |
| index = 6; |
| continue; |
| } |
| } |
| if (++index == 4) { |
| // Found no non-empty polylines during search for first point. No need to continue searching. |
| return; |
| } |
| } while (index <= 9); |
| /* |
| * Copies coordinates only if at least one of `firstPoint` or `lastPoint` is a valid point. |
| */ |
| take(polylineOnLeft.opposite); // Point will be iterated in reverse order. |
| take(polylineOnLeft); // Point will be iterated in forward order. |
| if (polylineOnTop != null) { |
| PolylineBuffer suffix = polylineOnTop.opposite; |
| take(polylineOnTop); // Inverse order. Set `polylineOnTop.opposite` to null. |
| take(suffix); // Forward order. |
| } |
| } |
| |
| /** |
| * Takes a copy of coordinate values of given polyline, then clears that polyline. |
| */ |
| private void take(final PolylineBuffer polyline) { |
| if (polyline != null && polyline.size != 0) { |
| add(Arrays.copyOf(polyline.coordinates, polyline.size)); |
| polyline.clear(); |
| } else { |
| add(null); // No data for iteration order at this position. |
| } |
| } |
| |
| /** |
| * Returns {@code true} if the given point is equal to the start point or end point. |
| * This is used in assertions for checking key validity in {@link Tracer.Level#partialPaths}. |
| */ |
| final boolean isExtremity(final Point key) { |
| return key.equals(firstPoint) || key.equals(lastPoint); |
| } |
| |
| /** |
| * Associates this polyline to its two extremities in the given map. If other polylines already exist |
| * for one or both extremities, then this polyline will be merged with previously existing polylines. |
| * This method returns {@code true} if the polyline has been closed, in which case caller should store |
| * the coordinates in {@link Tracer.Level#path} immediately. |
| * |
| * @param partialPaths where to add or merge polylines. |
| * @return {@code true} if this polyline became a closed polygon as a result of merge operation. |
| */ |
| final boolean addOrMerge(final Map<Point,Fragments> partialPaths) { |
| final Fragments before = partialPaths.remove(firstPoint); |
| final Fragments after = partialPaths.remove(lastPoint); |
| if (before != null) partialPaths.remove(addAll(before, true)); |
| if (after != null) partialPaths.remove(addAll(after, false)); |
| if (firstPoint != null && firstPoint.equals(lastPoint)) { // First/last points may have changed. |
| partialPaths.remove(firstPoint); |
| partialPaths.remove(lastPoint); |
| return true; |
| } else { |
| // Intentionally replace previous values. |
| if (firstPoint != null) partialPaths.put(firstPoint, this); |
| if (lastPoint != null) partialPaths.put(lastPoint, this); |
| return false; |
| } |
| } |
| |
| /** |
| * Prepends or appends the given polylines to this list of polylines. |
| * Points order will be changed as needed in order to match extremities. |
| * The {@code other} instance should be forgotten after this method call. |
| * |
| * @param other the other polyline to append or prepend to this polyline. |
| * @param prepend {@code true} for prepend operation, {@code false} for append. |
| * @return extremity of {@code other} which has not been assigned to {@code this}. |
| */ |
| private Point addAll(final Fragments other, final boolean prepend) { |
| assert ((size() | other.size()) & 1) == 0; // Must have even number of elements in both lists. |
| /* |
| * In figures below, ● are the extremities to attach together. |
| * `r` is a bitmask telling which polylines to reverse: |
| * 1=this, 2=other, together with combinations 0=none and 3=other. |
| */ |
| int r; if ( lastPoint != null && lastPoint.equals(other.firstPoint)) r = 0; // ○──────● ●──────○ |
| else if (firstPoint != null && firstPoint.equals(other.firstPoint)) r = 1; // ●──────○ ●──────○ |
| else if ( lastPoint != null && lastPoint.equals(other. lastPoint)) r = 2; // ○──────● ○──────● |
| else if (firstPoint != null && firstPoint.equals(other. lastPoint)) r = 3; // ●──────○ ○──────● |
| else { |
| // Should never happen because `other` has been obtained using a point of `this`. |
| throw new AssertionError(); |
| } |
| if (prepend) r ^= 3; // Swap order in above ○──○ ○──○ figures. |
| if ((r & 1) != 0) this.reverse(); |
| if ((r & 2) != 0) other.reverse(); |
| if (prepend) { |
| addAll(0, other); |
| firstPoint = other.firstPoint; |
| return other.lastPoint; |
| } else { |
| addAll(other); |
| lastPoint = other.lastPoint; |
| return other.firstPoint; |
| } |
| } |
| |
| /** |
| * Reverse the order of all points. The last polyline will become the first polyline and vice-versa. |
| * For each polyline, points will be iterated in opposite order. The trick on point order is done by |
| * moving polylines at even indices to odd indices, and conversely (see class javadoc for convention |
| * about even/odd indices). |
| */ |
| private void reverse() { |
| Collections.reverse(this); |
| final Point swap = firstPoint; |
| firstPoint = lastPoint; |
| lastPoint = swap; |
| } |
| |
| /** |
| * Returns the content of this list as an array of {@link PolylineBuffer} instances. |
| * {@code PolylineBuffer} instances at even index should be written with their points in reverse order. |
| * |
| * @see #writeTo(Joiner, PolylineBuffer[], boolean) |
| */ |
| final PolylineBuffer[] toPolylines() { |
| final PolylineBuffer[] polylines = new PolylineBuffer[size()]; |
| for (int i=0; i<polylines.length; i++) { |
| final double[] coordinates = get(i); |
| if (coordinates != null) { |
| polylines[i] = new PolylineBuffer(coordinates); |
| } |
| } |
| return polylines; |
| } |
| } |
