This is an automated email from the ASF dual-hosted git repository.
jsorel pushed a commit to branch feat/image2polygon
in repository https://gitbox.apache.org/repos/asf/sis.git
commit fe6bca1e57746dbee06ae3501c3781309409ac48
Author: jsorel <johann.so...@geomatys.com>
AuthorDate: Tue Mar 25 11:50:05 2025 +0100
Add image to polygon area algorithm
---
.../main/org/apache/sis/image/ImageProcessor.java | 39 +++
.../apache/sis/image/processing/polygon/Block.java | 42 +++
.../sis/image/processing/polygon/Boundary.java | 349 +++++++++++++++++++
.../sis/image/processing/polygon/Polygonize.java | 384 +++++++++++++++++++++
4 files changed, 814 insertions(+)
diff --git
a/endorsed/src/org.apache.sis.feature/main/org/apache/sis/image/ImageProcessor.java
b/endorsed/src/org.apache.sis.feature/main/org/apache/sis/image/ImageProcessor.java
index 9cdae190a2..1345b4075d 100644
---
a/endorsed/src/org.apache.sis.feature/main/org/apache/sis/image/ImageProcessor.java
+++
b/endorsed/src/org.apache.sis.feature/main/org/apache/sis/image/ImageProcessor.java
@@ -56,8 +56,10 @@ import org.apache.sis.util.collection.WeakHashSet;
import org.apache.sis.system.Modules;
import org.apache.sis.image.processing.isoline.Isolines;
import org.apache.sis.feature.internal.Resources;
+import org.apache.sis.image.processing.polygon.Polygonize;
import org.apache.sis.measure.NumberRange;
import org.apache.sis.measure.Units;
+import org.opengis.referencing.operation.MathTransform2D;
/**
@@ -1540,6 +1542,43 @@ public class ImageProcessor implements Cloneable {
}
}
+ /**
+ * Generates area polygons at the specified ranges computed from data
provided by the given image.
+ * Polygons will be computed for every bands in the given image.
+ * For each band, the result is given as a {@code Map} where keys are the
specified {@code ranges}
+ * and values are the polygons at the associated range.
+ * If there are no polygons for a given level, there will be no
corresponding entry in the map.
+ * The provided {@code ranges} must not overlap each other.
+ *
+ * @param data image providing source values.
+ * @param ranges value ranges for which to compute polygones. An array
should be provided for each band.
+ * If there is more bands than {@code ranges.length},
the last array is reused for
+ * all remaining bands.
+ * @param gridToCRS transform from pixel coordinates to geometry
coordinates, or {@code null} if none.
+ * Integer source coordinates are located at pixel
centers.
+ * @return the polygons for specified ranges in each band. The {@code
List} size is the number of bands.
+ * For each band, the {@code Map} size is equal or less than
{@code ranges[band].length}.
+ * Map keys are the specified ranges, excluding those for which
there are no polygons.
+ * Map values are the polygons as a Java2D {@link Shape}.
+ * @throws ImagingOpException if an error occurred during calculation.
+ */
+ public List<Map<NumberRange,List<Shape>>> areas(final RenderedImage data,
NumberRange[][] ranges, final MathTransform gridToCRS) throws
TransformException {
+ final Polygonize polygonizer = new Polygonize(data, ranges);
+ final List<Map<NumberRange, List<Shape>>> result =
polygonizer.polygones();
+
+ if (gridToCRS != null && !gridToCRS.isIdentity()) {
+ final MathTransform2D trs2d =
MathTransforms.bidimensional(gridToCRS);
+ for (Map<NumberRange, List<Shape>> m : result) {
+ for (List<Shape> lst : m.values()) {
+ for (int i = 0, n = lst.size(); i < n; i++) {
+ lst.set(i, trs2d.createTransformedShape(lst.get(i)));
+ }
+ }
+ }
+ }
+ return result;
+ }
+
/**
* Returns {@code true} if the given object is an image processor
* of the same class with the same configuration.
diff --git
a/endorsed/src/org.apache.sis.feature/main/org/apache/sis/image/processing/polygon/Block.java
b/endorsed/src/org.apache.sis.feature/main/org/apache/sis/image/processing/polygon/Block.java
new file mode 100644
index 0000000000..45cbea909d
--- /dev/null
+++
b/endorsed/src/org.apache.sis.feature/main/org/apache/sis/image/processing/polygon/Block.java
@@ -0,0 +1,42 @@
+/*
+ * 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.image.processing.polygon;
+
+import org.apache.sis.measure.NumberRange;
+
+/**
+ * Define a group of pixels with the same range.
+ *
+ * @author Johann Sorel (Geomatys)
+ */
+final class Block {
+
+ public NumberRange range;
+ public int startX;
+ public int endX;
+ public int y;
+ public Boundary boundary;
+
+ public void reset(){
+ range = null;
+ startX = -1;
+ endX = -1;
+ y = -1;
+ boundary = null;
+ }
+
+}
diff --git
a/endorsed/src/org.apache.sis.feature/main/org/apache/sis/image/processing/polygon/Boundary.java
b/endorsed/src/org.apache.sis.feature/main/org/apache/sis/image/processing/polygon/Boundary.java
new file mode 100644
index 0000000000..5a4ce953e9
--- /dev/null
+++
b/endorsed/src/org.apache.sis.feature/main/org/apache/sis/image/processing/polygon/Boundary.java
@@ -0,0 +1,349 @@
+/*
+ * 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.image.processing.polygon;
+
+import java.awt.Shape;
+import java.awt.geom.Area;
+import java.awt.geom.GeneralPath;
+import java.awt.geom.Point2D;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.LinkedList;
+import java.util.List;
+import org.apache.sis.measure.NumberRange;
+
+/**
+ * Define an "in construction" geometries.
+ * This type of objects contain a list of floeatings coordinates sequences
+ * that are progressivly merged together to obtain a polygon which might
contain holes.
+ *
+ * @author Johann Sorel (Geomatys)
+ */
+final class Boundary {
+
+ //finished geometries
+ private final List<GeneralPath> holes = new ArrayList<>();
+
+ //in construction geometries
+ private final LinkedList<LinkedList<Point2D.Double>> floatings = new
LinkedList<LinkedList<Point2D.Double>>();
+ final NumberRange range;
+
+ public Boundary(final NumberRange range){
+ this.range = range;
+ }
+
+ public void start(final int firstX, final int secondX, final int y){
+ if(firstX == secondX) throw new IllegalArgumentException("bugging
algorithm");
+ final LinkedList<Point2D.Double> exterior = new
LinkedList<Point2D.Double>();
+ exterior.addFirst(new Point2D.Double(firstX, y));
+ exterior.addFirst(new Point2D.Double(firstX, y+1));
+ exterior.addLast(new Point2D.Double(secondX, y));
+ exterior.addLast(new Point2D.Double(secondX, y+1));
+ floatings.add(exterior);
+
+ //checkValidity();
+ }
+
+ public void addFloating(final Point2D.Double from, final Point2D.Double
to){
+ if (from.equals(to)) {
+ throw new IllegalArgumentException("bugging algorithm");
+ }
+ //System.err.println("Add Floating From: " + from + " New : " + to );
+
+ final LinkedList<Point2D.Double> ll = new LinkedList<Point2D.Double>();
+ ll.addFirst(to);
+ ll.addLast(from);
+ floatings.add(ll);
+
+ //checkValidity();
+ }
+
+ public void add(final Point2D.Double from, final Point2D.Double to){
+ if(from.equals(to)){
+ throw new IllegalArgumentException("bugging algorithm");
+ }
+
+ //System.err.println("Add From: " + from + " New : " + to );
+
+
+ for(final LinkedList<Point2D.Double> ll : floatings){
+ final Point2D.Double first = ll.getFirst();
+ if(first.equals(from)){
+
+ if(from.x == to.x && ll.size() > 1){
+ final Point2D.Double second = ll.get(1);
+ if(second.x == from.x){
+ //points are aligned, just move the first point
+ first.y = to.y;
+ }else{
+ //points are not aligned, must create a new point
+ ll.addFirst(to);
+ }
+ }else if(from.y == to.y && ll.size() > 1){
+ final Point2D.Double second = ll.get(1);
+ if(second.y == from.y){
+ //points are aligned, just move the first point
+ first.x = to.x;
+ }else{
+ //points are not aligned, must create a new point
+ ll.addFirst(to);
+ }
+ }else{
+ ll.addFirst(to);
+ }
+
+ //checkValidity();
+ return;
+ }
+
+ final Point2D.Double last = ll.getLast();
+ if(last.equals(from)){
+ if(from.x == to.x && ll.size() > 1){
+ final Point2D.Double second = ll.get(ll.size()-2);
+ if(second.x == from.x){
+ //points are aligned, just move the first point
+ last.y = to.y;
+ }else{
+ //points are not aligned, must create a new point
+ ll.addLast(to);
+ }
+ }else if(from.y == to.y && ll.size() > 1){
+ final Point2D.Double second = ll.get(ll.size()-2);
+ if(second.y == from.y){
+ //points are aligned, just move the first point
+ last.x = to.x;
+ }else{
+ //points are not aligned, must create a new point
+ ll.addLast(to);
+ }
+ }else{
+ ll.addLast(to);
+ }
+
+ //checkValidity();
+ return;
+ }
+ }
+
+ //checkValidity();
+ throw new IllegalArgumentException("bugging algorithm");
+ }
+
+ public Shape link(final Point2D.Double from, final Point2D.Double to){
+ if(from.equals(to)){
+ throw new IllegalArgumentException("bugging algorithm : " + to);
+ }
+
+ //System.err.println("Link From: " + from + " to : " + to );
+
+
+ LinkedList<Point2D.Double> fromList = null;
+ boolean fromStart = false;
+ LinkedList<Point2D.Double> toList = null;
+ boolean toStart = false;
+
+ for(final LinkedList<Point2D.Double> ll : floatings){
+
+ if(fromList == null){
+ final Point2D.Double first = ll.getFirst();
+ final Point2D.Double last = ll.getLast();
+ if(first.equals(from)){
+ fromStart = true;
+ fromList = ll;
+ }else if(last.equals(from)){
+ fromStart = false;
+ fromList = ll;
+ }
+ }
+
+ if(toList == null){
+ final Point2D.Double first = ll.getFirst();
+ final Point2D.Double last = ll.getLast();
+ if(first.equals(to)){
+ toStart = true;
+ toList = ll;
+ }else if(last.equals(to)){
+ toStart = false;
+ toList = ll;
+ }
+ }
+
+ if(fromList != null && toList != null) break;
+ }
+
+
+ if(fromList != null && toList != null){
+ if(fromList == toList){
+ //same list finish it
+ //checkValidity();
+ return finish(fromList);
+ }else{
+ combine(fromList, fromStart, toList, toStart);
+ //checkValidity();
+ return null;
+ }
+
+ }else if(fromList != null ){
+ add(from, to);
+ //checkValidity();
+ return null;
+ }else if(toList != null){
+ add(to, from);
+ //checkValidity();
+ return null;
+ }
+
+ //checkValidity();
+ throw new IllegalArgumentException("bugging algorithm");
+ }
+
+ private void combine(final LinkedList<Point2D.Double> fromList, final
boolean fromStart,
+ final LinkedList<Point2D.Double> toList, final
boolean toStart){
+
+ if(fromStart){
+ if(toStart){
+ while(!toList.isEmpty()){
+ fromList.addFirst(toList.pollFirst());
+ }
+ }else{
+ while(!toList.isEmpty()){
+ fromList.addFirst(toList.pollLast());
+ }
+ }
+
+ }else{
+ if(toStart){
+ while(!toList.isEmpty()){
+ fromList.addLast(toList.pollFirst());
+ }
+ }else{
+ while(!toList.isEmpty()){
+ fromList.addLast(toList.pollLast());
+ }
+ }
+ }
+
+ floatings.remove(toList);
+ //checkValidity();
+ }
+
+
+ public void checkValidity(){
+
+ //check for list with less than 2 elements
+ for(LinkedList<Point2D.Double> ll : floatings){
+ if(ll.size() < 2){
+ //System.err.println(">>>> ERROR : " + this.toString());
+ throw new IllegalArgumentException("What ? a list with less
than 2 elements, not valid !");
+ }
+ }
+
+ //check for diagonal cases
+ for(LinkedList<Point2D.Double> ll : floatings){
+ Point2D.Double last = ll.get(0);
+ for(int i=1;i<ll.size();i++){
+ Point2D.Double current = ll.get(i);
+ if(last.x != current.x && last.y != current.y){
+ //System.err.println(">>>> ERROR : " + this.toString());
+ throw new IllegalArgumentException("What ? a diagonal, not
valid !");
+ }
+ last = current;
+ }
+ }
+
+ }
+
+
+
+ private Shape finish(final LinkedList<Point2D.Double> coords){
+
+ if(floatings.size() == 1){
+ //closing the polygon enveloppe
+ Shape geom = toClosedShape(coords);
+ //ring.setUserData(range);
+ floatings.remove(coords);
+
+ if (!holes.isEmpty()) {
+ Area area = new Area(geom);
+ for (Shape hole : holes) {
+ area.subtract(new Area(hole));
+ }
+ geom = area;
+ }
+
+ return geom;
+ }else{
+ //closing a hole in the geometry
+ GeneralPath ring = toClosedShape(coords);
+ holes.add(ring);
+ floatings.remove(coords);
+ return null;
+ }
+
+ }
+
+ private static void reverse(final Point2D.Double[] array){
+ for(int l=0, r=array.length-1; l<r; l++, r--) {
+ Point2D.Double temp = array[l];
+ array[l] = array[r];
+ array[r] = temp;
+ }
+ }
+
+ private GeneralPath toClosedShape(List<Point2D.Double> points) {
+ final GeneralPath path = new GeneralPath();
+ Point2D.Double start = points.get(0);
+ path.moveTo(start.x, start.y);
+ for (int i = 1, n = points.size(); i < n; i++) {
+ Point2D.Double pt = points.get(i);
+ path.lineTo(pt.x, pt.y);
+ }
+ path.closePath();
+
+ return path;
+ }
+
+ public void merge(final Boundary candidate){
+ //merge the floating sequences
+ this.floatings.addAll(candidate.floatings);
+ //merge the holes
+ this.holes.addAll(candidate.holes);
+ candidate.floatings.clear();
+ candidate.holes.clear();
+ }
+
+ @Override
+ public String toString() {
+ final StringBuilder sb = new StringBuilder("Boundary : ");
+ sb.append(range.toString());
+
+ for(LinkedList<Point2D.Double> coords : floatings){
+ sb.append(" \t{");
+ for(Point2D.Double c : coords){
+
sb.append('[').append((int)c.x).append(';').append((int)c.y).append(']');
+ }
+ sb.append('}');
+ }
+
+ return sb.toString();
+ }
+
+ public boolean isEmpty(){
+ return floatings.isEmpty();
+ }
+
+}
diff --git
a/endorsed/src/org.apache.sis.feature/main/org/apache/sis/image/processing/polygon/Polygonize.java
b/endorsed/src/org.apache.sis.feature/main/org/apache/sis/image/processing/polygon/Polygonize.java
new file mode 100644
index 0000000000..1782f30357
--- /dev/null
+++
b/endorsed/src/org.apache.sis.feature/main/org/apache/sis/image/processing/polygon/Polygonize.java
@@ -0,0 +1,384 @@
+/*
+ * 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.image.processing.polygon;
+
+import java.awt.Point;
+import java.awt.Shape;
+import java.awt.geom.Point2D;
+import java.awt.image.RenderedImage;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import org.apache.sis.measure.NumberRange;
+import org.apache.sis.image.PixelIterator;
+import org.opengis.coverage.grid.SequenceType;
+
+
+/**
+ * Process to extract Polygon from an image.
+ *
+ * @author Johann Sorel (Geomatys)
+ */
+public final class Polygonize {
+
+ private static final int LAST_LINE = 0;
+ private static final int CURRENT_LINE = 1;
+
+ //last line cache boundary
+ private final List<Map<NumberRange, List<Shape>>> polygons = new
ArrayList<>();
+
+ //buffer[band][LAST_LINE] holds last line buffer
+ //buffer[band][CURRENT_LINE] holds current line buffer
+ private Boundary[][][] buffers;
+
+ //current pixel block
+ private Block[] blocks;
+
+ private final RenderedImage image;
+ private final NumberRange[][] ranges;
+
+ /**
+ *
+ * @param coverage coverage to process
+ * @param ranges data value ranges
+ * @param band coverage band to process
+ */
+ public Polygonize(RenderedImage image, NumberRange[][] ranges){
+ this.image = image;
+ this.ranges = ranges;
+ }
+
+ public List<Map<NumberRange, List<Shape>>> polygones() {
+
+ final PixelIterator iter = new
PixelIterator.Builder().setIteratorOrder(SequenceType.LINEAR).create(image);
+ final int nbBand = iter.getNumBands();
+ blocks = new Block[nbBand];
+
+ final NumberRange NaNRange = new NaNRange();
+ for (int band = 0; band < nbBand; band++) {
+ final Map<NumberRange, List<Shape>> bandState = new HashMap<>();
+ //add a range for Nan values.
+ bandState.put(NaNRange, new ArrayList<>());
+ polygons.add(bandState);
+
+ for (final NumberRange range : ranges[Math.min(band,
ranges.length-1)]) {
+ bandState.put(range, new ArrayList<>());
+ }
+
+ blocks[band] = new Block();
+ }
+
+
+ /*
+ This algorithm create polygons which follow the contour of each pixel.
+ The 0,0 coordinate will match the pixel corner.
+ */
+ final Point gridPosition = new Point(0, 0);
+ double[] pixel = null;
+
+ final int width = image.getWidth();
+ final int height = image.getHeight();
+ buffers = new Boundary[nbBand][2][width];
+
+ for (int y = 0; y < height; y++) {
+ iter.moveTo(0, y);
+ gridPosition.y = y;
+ for (int x = 0; x < width; x++) {
+ gridPosition.x = x;
+ pixel = iter.getPixel(pixel);
+ for (int band = 0; band < nbBand; band++) {
+ append(polygons.get(band), buffers[band], blocks[band],
gridPosition, pixel[band]);
+ }
+ iter.next();
+ }
+
+ //insert last geometry
+ for (int band = 0; band < nbBand; band++) {
+ constructBlock(polygons.get(band), blocks[band],
buffers[band]);
+
+ //flip buffers, reuse old buffer line.
+ Boundary[] oldLine = buffers[band][LAST_LINE];
+ buffers[band][LAST_LINE] = buffers[band][CURRENT_LINE];
+ buffers[band][CURRENT_LINE] = oldLine;
+
+ blocks[band].reset();
+ }
+
+ }
+
+ //we have finish, close all geometries
+ gridPosition.y += 1;
+ for (int band = 0; band < nbBand; band++) {
+ for(int i = 0; i < buffers[band][LAST_LINE].length;i++) {
+ Shape poly = buffers[band][LAST_LINE][i].link(
+ new Point2D.Double(i, gridPosition.y),
+ new Point2D.Double(i+1, gridPosition.y)
+ );
+ if (poly != null) {
+
polygons.get(band).get(buffers[band][LAST_LINE][i].range).add(poly);
+ }
+ }
+ }
+
+ //avoid memory use
+ buffers = null;
+ final List<Map<NumberRange, List<Shape>>> copy = new
ArrayList<>(polygons);
+ //remove the NaNRange
+ for (Map m : copy) {
+ m.remove(NaNRange);
+ }
+ polygons.clear();
+ return copy;
+ }
+
+ private static void append(Map<NumberRange, List<Shape>> results, final
Boundary[][] buffers, final Block block, final Point point, Number value) {
+
+ //special case for NaN or null
+ final NumberRange valueRange;
+ if (value == null || Double.isNaN(value.doubleValue())) {
+ valueRange = new NaNRange();
+ } else {
+ valueRange = results.keySet().stream()
+ .filter(range -> range.containsAny(value))
+ .findAny()
+ .orElseThrow(() -> new IllegalArgumentException("Value not
in any range :" + value));
+ }
+
+ if (valueRange.equals(block.range)) {
+ //last pixel was in the same range
+ block.endX = point.x;
+ return;
+ } else if (block.range != null) {
+ //last pixel was in a different range, save it's geometry
+ constructBlock(results, block, buffers);
+ }
+
+ //start a pixel serie
+ block.range = valueRange;
+ block.startX = point.x;
+ block.endX = point.x;
+ block.y = point.y;
+ }
+
+ private static void constructBlock(Map<NumberRange, List<Shape>> results,
final Block block, final Boundary[][] buffers) {
+
+ //System.err.println("BLOCK ["+block.startX+","+block.endX+"]");
+
+ if(block.y == 0) {
+ //first line, the buffer is empty, must fill it
+ final Boundary boundary = new Boundary(block.range);
+ boundary.start(block.startX, block.endX+1, block.y);
+
+ for(int i=block.startX; i<=block.endX; i++) {
+ buffers[CURRENT_LINE][i] = boundary;
+ }
+ }else{
+ Boundary currentBoundary = null;
+
+ //first pass to close unfriendly blocks
----------------------------
+ for (int i=block.startX; i<=block.endX;) {
+ final Boundary candidate = buffers[LAST_LINE][i];
+ final int[] candidateExtent = findExtent(buffers, i);
+
+ //do not treat same blockes here
+ if (candidate.range != block.range) {
+ //System.err.println("A different block extent : "+
candidateExtent[0] + " " + candidateExtent[1]);
+ //System.err.println("before :" + candidate.toString());
+
+ if (candidateExtent[0] >= block.startX &&
candidateExtent[1] <= block.endX) {
+ //block overlaps completly candidate
+ final Shape poly = candidate.link(
+ new Point2D.Double(candidateExtent[0],
block.y),
+ new Point2D.Double(candidateExtent[1]+1,
block.y)
+ );
+ if(poly != null)
results.get(candidate.range).add(poly);
+ } else {
+ final Shape poly = candidate.link(
+ new Point2D.Double(
(block.startX<candidateExtent[0]) ? candidateExtent[0]: block.startX, block.y),
+ new Point2D.Double(
(block.endX>candidateExtent[1]) ? candidateExtent[1]+1: block.endX+1, block.y)
+ );
+ if (poly != null)
results.get(candidate.range).add(poly);
+ }
+
+ //System.err.println("after :" + candidate.toString());
+ }
+
+ i = candidateExtent[1]+1;
+ }
+
+ //second pass to fuse with friendly blocks
-------------------------
+
+ //we first merge the last line boundary if needed
+ int firstAnchor = Integer.MAX_VALUE;
+ int lastAnchor = Integer.MIN_VALUE;
+
+ for (int i = block.startX; i <= block.endX; ) {
+ final Boundary candidate = buffers[LAST_LINE][i];
+ final int[] candidateExtent = findExtent(buffers, i);
+
+ //do not treat different blocks here
+ if (candidate.range == block.range) {
+ //System.err.println("A firnet block extent : "+
candidateExtent[0] + " " + candidateExtent[1]);
+// //System.err.println("before :" + candidate.toString());
+
+ if (currentBoundary == null) {
+ //set the current boundary, will expend this one
+ currentBoundary = candidate;
+ } else if(currentBoundary != null) {
+ if(currentBoundary != candidate) {
+ //those two blocks doesnt belong to the same
boundaries, we must merge them
+ currentBoundary.merge(candidate);
+ }
+ currentBoundary.link(
+ new Point2D.Double(lastAnchor, block.y),
+ new Point2D.Double(candidateExtent[0], block.y)
+ );
+
+ replaceInLastLigne(buffers, candidate,
currentBoundary);
+ //System.out.println("Merging : " +
currentBoundary.toString());
+ }
+
+ if (candidateExtent[0] < firstAnchor) {
+ firstAnchor = candidateExtent[0];
+ }
+ lastAnchor = candidateExtent[1]+1;
+ }
+
+ i = candidateExtent[1]+1;
+ }
+
+ if (currentBoundary != null) {
+ //System.err.println("before :" + currentBoundary.toString());
+ }
+
+ if (currentBoundary == null) {
+ //no previous friendly boundary to link with
+ //make a new one
+ currentBoundary = new Boundary(block.range);
+ currentBoundary.start(block.startX, block.endX+1, block.y);
+ } else {
+ if (firstAnchor < block.startX) {
+ //the previous block has created a floating sequence to
this end
+ firstAnchor = block.startX;
+ }
+
+ //add the coordinates
+ //System.err.println("> first anchor : " +firstAnchor + "
lastAnchor : " +lastAnchor);
+ if (firstAnchor == block.startX) {
+ currentBoundary.add(
+ new Point2D.Double(firstAnchor, block.y),
+ new Point2D.Double(block.startX, block.y+1)
+ );
+ } else {
+ currentBoundary.add(
+ new Point2D.Double(firstAnchor, block.y),
+ new Point2D.Double(block.startX, block.y)
+ );
+ currentBoundary.add(
+ new Point2D.Double(block.startX, block.y),
+ new Point2D.Double(block.startX, block.y+1)
+ );
+ }
+
+ if (block.endX+1 >= lastAnchor) {
+ if (lastAnchor == block.endX+1) {
+ currentBoundary.add(
+ new Point2D.Double(lastAnchor, block.y),
+ new Point2D.Double(block.endX+1, block.y+1)
+ );
+ } else {
+ //System.err.println("0 add :" +
currentBoundary.toString());
+ currentBoundary.add(
+ new Point2D.Double(lastAnchor, block.y),
+ new Point2D.Double(block.endX+1, block.y)
+ );
+ //System.err.println("1 add:" +
currentBoundary.toString());
+ currentBoundary.add(
+ new Point2D.Double(block.endX+1, block.y),
+ new Point2D.Double(block.endX+1, block.y+1)
+ );
+ //System.err.println("after add:" +
currentBoundary.toString());
+ }
+ } else {
+ currentBoundary.addFloating(
+ new Point2D.Double(block.endX+1, block.y),
+ new Point2D.Double(block.endX+1, block.y+1)
+ );
+ }
+
+ //System.err.println(currentBoundary.toString());
+
+ }
+
+ //System.err.println("after :" + currentBoundary.toString());
+
+ //fill in the current line
-----------------------------------------
+
+ for (int i = block.startX; i <= block.endX; i++) {
+ if (currentBoundary.isEmpty()) {
+ throw new IllegalArgumentException("An empty boundary
inserted ? not possible.");
+ }
+
+ buffers[CURRENT_LINE][i] = currentBoundary;
+ }
+
+ }
+
+ }
+
+ private static void replaceInLastLigne(final Boundary[][] buffers, final
Boundary old, final Boundary newone) {
+ for (int i = 0, n = buffers[LAST_LINE].length; i < n; i++) {
+ if (buffers[LAST_LINE][i] == old) {
+ buffers[LAST_LINE][i] = newone;
+ }
+
+ if (buffers[CURRENT_LINE][i] == old) {
+ buffers[CURRENT_LINE][i] = newone;
+ }
+ }
+ }
+
+
+ private static int[] findExtent(final Boundary[][] buffers, final int
index) {
+ final int[] extent = new int[]{index,index};
+ final Boundary bnd = buffers[LAST_LINE][index];
+
+ while (extent[0] > 0 && buffers[LAST_LINE][ extent[0]-1 ] == bnd) {
+ extent[0]--;
+ }
+
+ while (extent[1] < buffers[LAST_LINE].length-1 && buffers[LAST_LINE][
extent[1]+1 ] == bnd) {
+ extent[1]++;
+ }
+
+ return extent;
+ }
+
+ private static class NaNRange extends NumberRange{
+
+ public NaNRange() {
+ super(Double.class, 0d, true, 0d, true);
+ }
+
+ @Override
+ public boolean contains(final Comparable number) throws
IllegalArgumentException {
+ return Double.isNaN(((Number) number).doubleValue());
+ }
+ }
+
+}
