|
Lines 17-22
import java.io.Serializable;
Link Here
|
| 17 |
import java.util.ArrayList; |
17 |
import java.util.ArrayList; |
| 18 |
import java.util.Arrays; |
18 |
import java.util.Arrays; |
| 19 |
import java.util.Comparator; |
19 |
import java.util.Comparator; |
|
|
20 |
import java.util.List; |
| 20 |
|
21 |
|
| 21 |
import org.eclipse.gef4.geometry.euclidean.Angle; |
22 |
import org.eclipse.gef4.geometry.euclidean.Angle; |
| 22 |
import org.eclipse.gef4.geometry.euclidean.Straight; |
23 |
import org.eclipse.gef4.geometry.euclidean.Straight; |
|
Lines 116-121
public class Point implements Cloneable, Serializable {
Link Here
|
| 116 |
return Point.getCopy(points); |
117 |
return Point.getCopy(points); |
| 117 |
} |
118 |
} |
| 118 |
|
119 |
|
|
|
120 |
// Remove duplicate points from the given point list in orde to be able |
| 121 |
// to apply the Graham scan. |
| 122 |
points = eliminateDuplicates(points); |
| 123 |
|
| 119 |
// do a graham scan to find the convex hull of the given set of points |
124 |
// do a graham scan to find the convex hull of the given set of points |
| 120 |
|
125 |
|
| 121 |
// move point with lowest y coordinate to first position |
126 |
// move point with lowest y coordinate to first position |
|
Lines 164-169
public class Point implements Cloneable, Serializable {
Link Here
|
| 164 |
return convexHull.toArray(new Point[] {}); |
169 |
return convexHull.toArray(new Point[] {}); |
| 165 |
} |
170 |
} |
| 166 |
|
171 |
|
|
|
172 |
private static Point[] eliminateDuplicates(Point... points) { |
| 173 |
// sort points by x and y |
| 174 |
Arrays.sort(points, 0, points.length, new Comparator<Point>() { |
| 175 |
public int compare(Point p1, Point p2) { |
| 176 |
if (p1.x < p2.x) |
| 177 |
return -1; |
| 178 |
if (p1.x == p2.x && p1.y < p2.y) |
| 179 |
return -1; |
| 180 |
return 1; |
| 181 |
} |
| 182 |
}); |
| 183 |
|
| 184 |
// filter points |
| 185 |
List<Point> uniquePoints = new ArrayList<Point>(points.length); |
| 186 |
for (int i = 0; i < points.length - 1; i++) |
| 187 |
if (!points[i].equals(points[i + 1])) |
| 188 |
uniquePoints.add(points[i]); |
| 189 |
uniquePoints.add(points[points.length - 1]); |
| 190 |
return uniquePoints.toArray(new Point[] {}); |
| 191 |
} |
| 192 |
|
| 167 |
/** |
193 |
/** |
| 168 |
* Copies an array of points, by copying each point contained in the array. |
194 |
* Copies an array of points, by copying each point contained in the array. |
| 169 |
* |
195 |
* |
