The revolutionary project management tool is here! Plan visually with a single glance and make sure your projects get done.
private ArrayList<Point> points = new ArrayList<Point>() {
@Override
public void add(int index, Point newPoint) {
index = 0;
int minIndex = 0;
double minDistance = Double.MAX_VALUE;
for (Point p : this) {
double distance = p.distanceSq(newPoint);
if (distance < minDistance) {
minDistance = distance;
minIndex = index;
}
index++;
}
if (direction.compare(newPoint, get(minIndex)) < 0)
super.add(minIndex, newPoint);
else super.add(minIndex + 1, newPoint);
}
};
public enum Direction {
leftToRight(new Comparator<Point>() {
@Override public int compare(Point p1, Point p2) { return p2.x - p1.x; }}),
rightToLeft(new Comparator<Point>() {
@Override public int compare(Point p1, Point p2) { return p1.x - p2.x; }}),
topToBottom(new Comparator<Point>() {
@Override public int compare(Point p1, Point p2) { return p2.y - p1.y; }}),
bottomToTop(new Comparator<Point>() {
@Override public int compare(Point p1, Point p2) { return p1.y - p2.y; }}),
leftToLeft(new Comparator<Point>() {
@Override public int compare(Point p1, Point p2) { return 0; }}), // dunno wot to do here
rightToRight(new Comparator<Point>() {
@Override public int compare(Point p1, Point p2) { return 0; }}), // dunno wot to do here
topToTop(new Comparator<Point>() {
@Override public int compare(Point p1, Point p2) { return 0; }}); // dunno wot to do here
private Comparator comparator;
Direction(Comparator c) { comparator = c; }
public Comparator comparator() { return comparator; }
public int compare(Point p1, Point p2) { return comparator.compare(p1, p2); }
};
:
Path2D.Float path = new Path2D.Float();
path.moveTo(start.x, start.y);
for (int index = 1; index < points.size(); index++)
path.lineTo(points.get(index).x, points.get(index).y);
:
g.draw(path);
:
/** Distance between a point and a polygon.
@param x0 x of single point.
@param y0 y of single point.
@param beginidx Index of first point (xvals,yvals) to include in the search (to only search a subsection of the polygon). Pass 0 to start from first point.
@param endidx Index of last point+1 (xvals,yvals) to include in the search (to only search a subsection of the polygon). Pass xvals.size() to include last point.
@param polyx Pointer to double to store x-position of nearest point projected on polygon (pass NULL to not store).
@param polyy Pointer to double to store y-position of nearest point projected on polygon (pass NULL to not store).
@param polyidx Pointer to index to store the index of the nearest point passed to method (pass NULL to not store).
@return The smallest Eucledian distance between p0 and the polygon defined by (xvals, yvals).
*/double DistancePointToPolygon(double x0, double y0, std::vector<double> &xvals, std::vector<double> &yvals, int beginidx, int endidx, double* polyx, double* polyy, int* polyidx) {
double a ,b, c;
double x1, x2, y1, y2;
int i;
double curdist, bestdist, dist, distp1, distp2, maxdist, baselinelength;
double scalefactor;
if (xvals.size()==0)
return 1E100;
else if (xvals.size()==1)
return DistancePointToPoint(x0,y0, xvals[0], yvals[0]);
x2 = xvals[beginidx];
y2 = yvals[beginidx];
bestdist = 1E100;
for (i=beginidx+1; i<endidx; i++)
{
x1 = x2;
y1 = y2;
x2 = xvals[i];
y2 = yvals[i];
// Line in the plane defined by p1 and p2
a = -(y2 - y1);
b = (x2 - x1);
c = -a*x1 - b*y1;
dist = fabs(a*x0 + b*y0 + c) / sqrt(a*a + b*b);
// To the line segment
distp1 = DistancePointToPoint(x0,y0, x1,y1);
distp2 = DistancePointToPoint(x0,y0, x2,y2);
maxdist = max(distp1, distp2);
// Calculate length of baseline in triangle defined by
// p0, p0 projected on line, and the most distant point on edge
baselinelength = sqrt(maxdist*maxdist - dist*dist);
if (baselinelength < DistancePointToPoint(x1,y1, x2,y2))
curdist = dist;
else
curdist = min(distp1, distp2);
if (curdist < bestdist)
{
bestdist = curdist;
if (polyx != NULL)
{
if (curdist == distp1)
{
*polyx = x1;
*polyy = y1;
}
else if (curdist == distp2)
{
*polyx = x2;
*polyy = y2;
}
else
{
scalefactor = baselinelength / DistancePointToPoint(x1,y1, x2,y2);
if (distp1>distp2)
{
// Use triangle p1, p0, projection p0
*polyx = x1 + scalefactor * (x2-x1);
*polyy = y1 + scalefactor * (y2-y1);
}
else
{
// Use triangle p2, p0, projection p0
*polyx = x2 + scalefactor * (x1-x2);
*polyy = y2 + scalefactor * (y1-y2);
}
}
}
// Store index of nearest point
if (polyidx != NULL)
{
if (distp2 <= distp1)
*polyidx = i-1;
else
*polyidx = i;
}
}
}
return bestdist;
};
import java.util.ArrayList;
import java.awt.Point;
import java.awt.geom.Line2D;
public class SortedPoints extends ArrayList<Point> {
public void insert(Point newPoint) { add(shortestDistance(newPoint), newPoint); }
private int shortestDistance(Point p0) {
int minIndex = 1;
if (size() > 2) {
double minDistance = Double.MAX_VALUE;
for (int i = 0; i < size() - 1; i++) {
Point p1 = get(i);
Point p2 = get(i + 1);
double d = Line2D.ptSegDist(p1.x, p1.y, p2.x, p2.y, p0.x, p0.y);
if (d < minDistance) {
minIndex = i + 1;
minDistance = d;
}
}
}
return minIndex;
}
}
If you are experiencing a similar issue, please ask a related question
Join the community of 500,000 technology professionals and ask your questions.