Hi Gerd
Here is a unit test for polygon splitting. To go in
{trunk}/test/uk/me/parabola/util/ShapeSplitterTest.java
Regards
Ticker
On Sun, 2017-01-08 at 10:30 +0000, Gerd Petermann wrote:
> Hi Ticker,
>
> I think you can take the tests in uk.me.parabola.util in mkgmap/test
> as an example.
> And sorry, I should already have coded one for
> clipSinglePathWithSutherlandHodgman().
>
> Gerd
>
>
> ________________________________________
> Von: mkgmap-dev <[email protected]> im Auftrag
> von Ticker Berkin <[email protected]>
> Gesendet: Sonntag, 8. Januar 2017 11:20:19
> An: [email protected]
> Betreff: Re: [mkgmap-dev] New code for splitting polygon
>
> Hi Gerd
>
> Will do. Can you point me to an example of the preferred style for a
> unit test.
>
> Thanks
> Ticker
>
> On Sat, 2017-01-07 at 18:14 +0000, Gerd Petermann wrote:
> > Hi Ticker,
> >
> > sounds great. Please can you add some unit tests to show what it
> > does
> > with holes, points on the split line
> > and one or more line segments on the split line?
> >
> > Gerd
> > ________________________________________
> > Von: mkgmap-dev <[email protected]> im Auftrag
> > von Ticker Berkin <[email protected]>
> > Gesendet: Samstag, 7. Januar 2017 18:36:31
> > An: mkgmap development
> > Betreff: [mkgmap-dev] New code for splitting polygon
> >
> > Hi Gerd
> >
> > I've written some new code for splitting polygons in an efficient
> > manner. The main interface takes a shape and line of latitude or
> > longitude and returns 2 lists of shapes on either side of the line.
> > There is also a function to clip to rectangle.
> >
> > I've put the code in util/ShapeSplitter but it could go elsewhere
> > if
> > you prefer.
> >
> > So far I've only converted build/MapArea to use it, but I think it
> > can
> > be used throughout eventually. For the moment I've commented out
> > the
> > old code in MapArea, but this can be deleted in a while.
> >
> > Regards
> > Ticker
> > _______________________________________________
> > mkgmap-dev mailing list
> > [email protected]
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> [email protected]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> [email protected]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
/*
* Copyright (C) 2017.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 3 or
* version 2 as published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*/
package uk.me.parabola.util;
import java.util.ArrayList;
//import java.util.Arrays;
import java.util.List;
import java.util.Collections;
import uk.me.parabola.util.Java2DConverter;
import uk.me.parabola.imgfmt.app.Area;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.mkgmap.filters.ShapeMergeFilter;
import uk.me.parabola.mkgmap.general.MapShape;
import org.junit.Test;
import static org.junit.Assert.*;
/**
* Test polygon splitting
* @author Ticker Berkin
*
*/
public class ShapeSplitterTest {
@Test
public void test1_SimpleSplit() {
// simple diamond shape
int[][] os = { {1,1}, {5,3}, {7,7}, {3,5} };
splitTester st = new splitTester(os);
st.cutPosn(3, false);
int[][] f1 = { {1,1}, {3,2}, {3,5} };
st.addExpected(f1);
int[][] f2 = { {3,2}, {5,3}, {7,7}, {3,5} };
st.addExpected(f2);
st.cutWithSplitShape();
st.cutWithClipToBounds();
st.cutWithJava2D();
st.cutPosn(5, true);
int[][] t1 = { {1,1}, {5,3}, {6,5}, {3,5} };
st.addExpected(t1);
int[][] t2 = { {6,5}, {7,7}, {3,5} };
st.addExpected(t2);
st.cutWithSplitShape();
st.cutWithClipToBounds();
st.cutWithJava2D();
}
@Test
public void test2_cutToHole() {
// shape has hole with cut to get to it
int[][] os = { {1,1}, {3,1}, {3,3}, {2,3}, {2,4}, {4,4}, {4,3}, {3,3}, {3,1}, {5,1}, {5,5}, {1,5} };
splitTester st = new splitTester(os);
// cut across existing cut
st.cutPosn(2, true);
int[][] t1 = { {1,1}, {3,1}, {3,2}, {1,2} };
st.addExpected(t1);
int[][] t2 = { {3,1}, {5,1}, {5,2}, {3,2} };
st.addExpected(t2);
int[][] t3 = { {1,2}, {3,2}, {3,3}, {2,3}, {2,4}, {4,4}, {4,3}, {3,3}, {3,2}, {5,2}, {5,5}, {1,5} };
st.addExpected(t3);
st.cutWithSplitShape();
st.cutWithClipToBounds();
//!!! st.cutWithJava2D(); !!! java2D can't handle this
// cut along cut and through other side of hole
st.cutPosn(3, false);
int[][] f1 = { {1,1}, {3,1}, {3,3}, {2,3}, {2,4}, {3,4}, {3,5}, {1,5} };
st.addExpected(f1);
int[][] f2 = { {3,1}, {5,1}, {5,5}, {3,5}, {3,4}, {4,4}, {4,3}, {3,3} };
st.addExpected(f2);
st.cutWithSplitShape();
st.cutWithClipToBounds();
st.cutWithJava2D();
}
@Test
public void test3_cutSpiral() {
// Imagine shape is rope, folded and the two loose ends on inside of a spiral
int[][] os = {
// start: lower clockwise out
{7,10}, {6,10}, {6,6}, {10,6}, {10,14}, {2,14}, {2,2}, {14,2},
// fold
{14,14}, {13,14}, {13,3},
// lower anti-clockwise in
{3,3}, {3,13}, {9,13}, {9,7}, {7,7},
// lower clockwise out
{7,8}, {8,8}, {8,12}, {4,12}, {4,4}, {12,4}, {12,15},
// fold
{15,15}, {15,1},
// lower anti-clockwise in :end
{1,1}, {1,15}, {11,15}, {11,5}, {5,5}, {5,11}, {7,11}
};
splitTester st = new splitTester(os);
st.cutPosn(9, true);
// left hand going up
int[][] l1 = { {1,9}, {1,1}, {15,1}, {15,9}, {14,9}, {14,2}, {2,2}, {2,9} };
st.addExpected(l1);
int[][] l2 = { {3,9}, {3,3}, {13,3}, {13,9}, {12,9}, {12,4}, {4,4}, {4,9} };
st.addExpected(l2);
int[][] l3 = { {5,9}, {5,5}, {11,5}, {11,9}, {10,9}, {10,6}, {6,6}, {6,9} };
st.addExpected(l3);
int[][] l4 = { {8,9}, {8,8}, {7,8}, {7,7}, {9,7}, {9,9} };
st.addExpected(l4);
// right hand going up
int[][] r1 = { {1,9}, {1,15}, {11,15}, {11,9}, {10,9}, {10,14}, {2,14}, {2,9} };
st.addExpected(r1);
int[][] r2 = { {3,9}, {3,13}, {9,13}, {9,9}, {8,9}, {8,12}, {4,12}, {4,9} };
st.addExpected(r2);
int[][] r3 = { {5,9}, {5,11}, {7,11}, {7,10}, {6,10}, {6,9} };
st.addExpected(r3);
int[][] r4 = { {12,9}, {12,15}, {15,15}, {15,9}, {14,9}, {14,14}, {13,14}, {13,9} };
st.addExpected(r4);
st.cutWithSplitShape();
st.cutWithClipToBounds();
st.cutWithJava2D();
}
@Test
public void test4_cutFlash() {
// a complicated shape that needs to be drawn on graph paper to understand
int[][] os = {
{20,18}, {15,18}, {6,9}, {6,10}, {4,8}, {4,18},
{1,18}, {1,1}, {20,1}, {20,10},
{12,2}, {12,10}, {11,9}, {11,10}, {9,8}, {9,10}, {2,3},
{2,10}, {3,11}, {3,5}, {13,15}, {13,7}, {16,10}, {16,8}, {18,10}, {18,9}, {20,11}
};
splitTester st = new splitTester(os);
st.cutPosn(9, true);
// left hand going up
int[][] l1 = { {1,9}, {1,1}, {20,1}, {20,9}, {19,9}, {12,2}, {12,9}, {10,9}, {9,8}, {9,9}, {8,9}, {2,3}, {2,9} };
st.addExpected(l1);
int[][] l2 = { {3,9}, {3,5}, {7,9}, {5,9}, {4,8}, {4,9} };
st.addExpected(l2);
int[][] l3 = { {13,9}, {13,7}, {15,9} };
st.addExpected(l3);
int[][] l4 = { {16,9}, {16,8}, {17,9} };
st.addExpected(l4);
// right hand going up
int[][] r1 = { {1,9}, {1,18}, {4,18}, {4,9}, {3,9}, {3,11}, {2,10}, {2,9} };
st.addExpected(r1);
int[][] r2 = { {5,9}, {6,10}, {6,9} };
st.addExpected(r2);
int[][] r3 = { {6,9}, {15,18}, {20,18}, {20,11}, {18,9}, {18,10}, {17,9}, {16,9}, {16,10}, {15,9}, {13,9}, {13,15}, {7,9} };
st.addExpected(r3);
int[][] r4 = { {8,9}, {9,10}, {9,9} };
st.addExpected(r4);
int[][] r5 = { {10,9}, {11,10}, {11,9} };
st.addExpected(r5);
int[][] r6 = { {11,9}, {12,10}, {12,9} };
st.addExpected(r6);
int[][] r7 = { {19,9}, {20,10}, {20,9} };
st.addExpected(r7);
st.cutWithSplitShape();
st.cutWithClipToBounds();
st.cutWithJava2D();
}
private class splitTester {
List<Coord> origShape;
long origArea;
List<List<Coord>> expectedShapes, resultShapes;
long totalArea;
int dividingLine;
boolean isLongitude;
Area lessBounds, moreBounds;
String algorithm;
List<Coord> makeShape(int[][] lowPrecPoints) {
List<Coord> points = new ArrayList<>();
for (int [] intPair : lowPrecPoints)
points.add(new Coord(intPair[0], intPair[1]));
points.add(points.get(0));
return points;
}
splitTester(int[][] lowPrecPoints) {
origShape = makeShape(lowPrecPoints);
origArea = ShapeMergeFilter.calcAreaSizeTestVal(origShape);
}
void cutPosn(int dividingLine, boolean isLongitude) {
this.dividingLine = dividingLine;
this.isLongitude = isLongitude;
expectedShapes = new ArrayList<>();
totalArea = 0;
// make Area bounding boxes for some of the algorithms
MapShape tempShape = new MapShape();
tempShape.setPoints(origShape);
Area bounds = tempShape.getBounds();
if (isLongitude) {
lessBounds = new Area(bounds.getMinLat(),
bounds.getMinLong(),
bounds.getMaxLat(),
dividingLine);
moreBounds = new Area(bounds.getMinLat(),
dividingLine,
bounds.getMaxLat(),
bounds.getMaxLong());
} else {
lessBounds = new Area(bounds.getMinLat(),
bounds.getMinLong(),
dividingLine,
bounds.getMaxLong());
moreBounds = new Area(dividingLine,
bounds.getMinLong(),
bounds.getMaxLat(),
bounds.getMaxLong());
}
}
void addExpected(int[][] lowPrecPoints) {
List<Coord> another = makeShape(lowPrecPoints);
totalArea += Math.abs(ShapeMergeFilter.calcAreaSizeTestVal(another));
expectedShapes.add(another);
}
void preSplit(String algorithm) {
this.algorithm = algorithm;
assertEquals(algorithm + " bits area", Math.abs(origArea), totalArea);
resultShapes = null;
}
void checkResults() {
assertEquals(algorithm + " number of areas", expectedShapes.size(), resultShapes.size());
long resTotalArea = 0;
for (List<Coord> resShape : resultShapes) {
long resArea = ShapeMergeFilter.calcAreaSizeTestVal(resShape);
resTotalArea += Math.abs(resArea);
MapShape resTemp = new MapShape();
resTemp.setPoints(resShape);
Area resBounds = resTemp.getBounds();
// try and find in expected shapes
boolean foundIt = false;
for (List<Coord> expShape : expectedShapes) {
long expArea = ShapeMergeFilter.calcAreaSizeTestVal(expShape);
MapShape expTemp = new MapShape();
expTemp.setPoints(expShape);
Area expBounds = expTemp.getBounds();
if (Math.abs(expArea) == Math.abs(resArea) && expBounds.equals(resBounds)) {
foundIt = true;
// attempt to check points
// make unclosed copy for manipulation
List<Coord> resPoints = new ArrayList<>(resShape);
resPoints.remove(resPoints.size()-1);
if (expArea != resArea) // if sign of areas different
Collections.reverse(resPoints);
// rotate the list so have same first elem
Coord expFst = expShape.get(0);
int inx;
for (inx = 0; inx < resPoints.size(); ++inx)
if (resPoints.get(inx).equals(expFst))
break;
assertNotEquals("find first point failed", resPoints.size(), inx);
if (inx > 0)
Collections.rotate(resPoints, -inx);
// now step through. Maybe need to allow duplicate/extra in result set
// if java2D... might keeps some on the cut line
inx = 0;
for (Coord resPoint : resPoints) {
assertTrue(algorithm + " point " + inx, resPoint.equals(expShape.get(inx)));
++inx;
}
break;
} // if shape has correct area and bounds
} // for each expectedShape
assertTrue(algorithm + " result shape not matched", foundIt);
} // for each resultShape
assertEquals(algorithm + " result total area", Math.abs(origArea), resTotalArea);
} // checkResults
void cutWithSplitShape() {
preSplit("splitShape");
resultShapes = new ArrayList<>();
ShapeSplitter.splitShape(origShape, dividingLine << Coord.DELTA_SHIFT, isLongitude, resultShapes, resultShapes, null);
checkResults();
}
void cutWithClipToBounds() {
preSplit("clipToBounds");
resultShapes = ShapeSplitter.clipToBounds(origShape, lessBounds, null);
List<List<Coord>> moreShapes = ShapeSplitter.clipToBounds(origShape, moreBounds, null);
resultShapes.addAll(moreShapes);
checkResults();
}
void cutWithJava2D() {
preSplit("java2D");
java.awt.geom.Area area = Java2DConverter.createArea(origShape);
java.awt.geom.Area clipper = Java2DConverter.createBoundsArea(lessBounds);
clipper.intersect(area);
resultShapes = Java2DConverter.areaToShapes(clipper);
clipper = Java2DConverter.createBoundsArea(moreBounds);
clipper.intersect(area);
List<List<Coord>> moreShapes = Java2DConverter.areaToShapes(clipper);
resultShapes.addAll(moreShapes);
checkResults();
}
/*
void cutWithSuthHodg() {
preSplit("suthHodg");
started to look at this to see if could fit in to testing like above but gave up.
Path2D.Double ShapeSplitter.clipSinglePathWithSutherlandHodgman (double[] points, int num, Rectangle2D clippingRect, Rectangle2D.Double bbox) {
checkResults();
}
*/
}
}
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
