/*
* 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 static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotEquals;
import static org.junit.Assert.assertTrue;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import org.junit.Test;
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;
/**
* Test polygon splitting
*
* @author Ticker Berkin
*
*/
public class ShapeSplitterTest
{
@Test
public void test1SimpleSplit
() {
// 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.
runSplitShape();
st.
runClipToBounds();
st.
runJava2D();
// st.runSuthHodg();
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.
runSplitShape();
st.
runClipToBounds();
st.
runJava2D();
// st.runSuthHodg();
}
@Test
public void test2CutToHole
() {
// 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.
runSplitShape();
st.
runClipToBounds();
// !!! st.runJava2D(); !!! java2D can't handle this
// st.runSuthHodg();
// 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.
runSplitShape();
st.
runClipToBounds();
st.
runJava2D();
// st.runSuthHodg();
}
@Test
public void test3CutSpiral
() {
// 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.
runSplitShape();
st.
runClipToBounds();
st.
runJava2D();
// st.runSuthHodg();
}
@Test
public void test4CutFlash
() {
// 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.
runSplitShape();
st.
runClipToBounds();
st.
runJava2D();
// st.runSuthHodg();
st.
clipBounds(1,
1,
20,
18); // this full area
st.
addExpected(os
); // original shape
st.
runClipToBounds();
st.
runJava2D();
// st.runSuthHodg();
st.
clipBounds(13,
10,
19,
16); // a solid bit
int[][] s1 =
{ { 13,
10 },
{ 13,
16 },
{ 19,
16 },
{ 19,
10 } };
st.
addExpected(s1
);
st.
runClipToBounds();
st.
runJava2D();
// st.runSuthHodg();
st.
clipBounds(9,
10,
13,
11); // a hole
st.
runClipToBounds();
st.
runJava2D();
// st.runSuthHodg();
}
@Test
public void test4ClipTest
() {
// shape to defeat naive sutherland-hodge implementation
int[][] os =
{ { 2,
1 },
{ 10,
1 },
{ 10,
10 },
{ 1,
10 },
{ 1,
2 },
{ 2,
3 },
{ 2,
5 },
{ 4,
5 },
{ 4,
6 },
{ 2,
6 },
{ 2,
9 },
{ 5,
9 },
{ 5,
7 },
{ 6,
7 },
{ 6,
9 },
{ 9,
9 },
{ 9,
6 },
{ 7,
6 },
{ 7,
5 },
{ 9,
5 },
{ 9,
2 },
{ 6,
2 },
{ 6,
4 },
{ 5,
4 },
{ 5,
2 },
{ 3,
2 } };
SplitTester st =
new SplitTester
(os
);
st.
clipBounds(3,
3,
8,
8);
int[][] s1 =
{ { 6,
3 },
{ 6,
4 },
{ 5,
4 },
{ 5,
3 } };
st.
addExpected(s1
);
int[][] s2 =
{ { 7,
5 },
{ 8,
5 },
{ 8,
6 },
{ 7,
6 } };
st.
addExpected(s2
);
int[][] s3 =
{ { 5,
7 },
{ 6,
7 },
{ 6,
8 },
{ 5,
8 } };
st.
addExpected(s3
);
int[][] s4 =
{ { 3,
5 },
{ 4,
5 },
{ 4,
6 },
{ 3,
6 } };
st.
addExpected(s4
);
st.
runClipToBounds();
st.
runJava2D();
// st.runSuthHodg();
}
private class SplitTester
{
List<Coord
> origShape
;
long origArea
;
List<List<Coord
>> expectedShapes, resultShapes
;
long totalArea
;
boolean dividingInTwo
;
int dividingLine
;
boolean isLongitude
;
Area fstBounds, lstBounds
;
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
) {
dividingInTwo =
true;
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
) {
fstBounds =
new Area(bounds.
getMinLat(), bounds.
getMinLong(), bounds.
getMaxLat(), dividingLine
);
lstBounds =
new Area(bounds.
getMinLat(), dividingLine, bounds.
getMaxLat(), bounds.
getMaxLong());
} else {
fstBounds =
new Area(bounds.
getMinLat(), bounds.
getMinLong(), dividingLine, bounds.
getMaxLong());
lstBounds =
new Area(dividingLine, bounds.
getMinLong(), bounds.
getMaxLat(), bounds.
getMaxLong());
}
}
void clipBounds
(int minLat,
int minLong,
int maxLat,
int maxLong
) {
dividingInTwo =
false;
expectedShapes =
new ArrayList<>();
totalArea =
0;
fstBounds =
new Area(minLat, minLong, maxLat, maxLong
);
}
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
;
if (dividingInTwo
) {
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", totalArea, resTotalArea
);
} // checkResults
void runSplitShape
() {
preSplit
("splitShape");
resultShapes =
new ArrayList<>();
assertTrue
(algorithm +
" Not applicable to clip", dividingInTwo
);
ShapeSplitter.
splitShape(origShape, dividingLine
<< Coord.
DELTA_SHIFT, isLongitude, resultShapes,
resultShapes,
null);
checkResults
();
}
void runClipToBounds
() {
preSplit
("clipToBounds");
resultShapes = ShapeSplitter.
clipToBounds(origShape, fstBounds,
null);
if (dividingInTwo
) {
List<List<Coord
>> moreShapes = ShapeSplitter.
clipToBounds(origShape, lstBounds,
null);
resultShapes.
addAll(moreShapes
);
}
checkResults
();
}
void runJava2D
() {
preSplit
("java2D");
java.
awt.
geom.
Area area = Java2DConverter.
createArea(origShape
);
java.
awt.
geom.
Area clipper = Java2DConverter.
createBoundsArea(fstBounds
);
clipper.
intersect(area
);
resultShapes = Java2DConverter.
areaToShapes(clipper
);
if (dividingInTwo
) {
clipper = Java2DConverter.
createBoundsArea(lstBounds
);
clipper.
intersect(area
);
List<List<Coord
>> moreShapes = Java2DConverter.
areaToShapes(clipper
);
resultShapes.
addAll(moreShapes
);
}
checkResults
();
}
/*
* void runSuthHodg() { 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(); }
*/
}
}