I have a problem with sorting coordinates, which I can't seem to find a solution/algorithm for. Here is my problem:
+ I have a drawing in which icons are connected by (arbitrary long/complex) directed lines.
+ the user can edit the connecting lines by
- dragging the points around,
- remove points,
- add points to the line.
The points of a line are stored in an ArrayList of Points and to draw the connection I create a Path2D out of the list.

Here is my problem/question:
when the user inserts a new point how can I find out where in my array list the new point has to go?
Are there any algorithms how to sort a set of coordinates along a path or something like that?
(the number of points per line are typically very small, so performance is not an issue here.)

Thomas

Attached is my code I came up with, but which does not work reliably...

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); } };

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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); } };

oookaaayyy...
but is that such a rare function that nobody has come up with some ideas how to solve this?

How can I follow a path which is defined by a set of points to find out where to insert a new point?

0

Tech changes fast. You can learn faster. That’s why we’re bringing professional training courses to Experts Exchange. With a subscription, you can access all the Cloud Class® courses to expand your education, prep for certifications, and get top-notch instructions.

first you need to *define* where it should be inserted
from what you're posted it sounds like you don't actually have a definition of where it should be inserted. there are many ways to decide where

@objects:
I don't quite understand what you mean by "first you need to *define*..."
+ I have a line/path
+ the user clicks on it
+ at the click-location I want to have a new point

in order to draw a consecutive line I need to find the place in my list of points to add the new point.

: 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);:

existing line stored in arraylist p1, p2, p3
X--------------X---------------X
p1 p2 p3

the user clicks somewhere between p2 and p3 at +:
X--------------X---------+-----X
p1 p2 np p3

now I want to insert the new point in my arraylist so that I have p1, p2, np, p3

My algorithm works as long as the lines are fairly straight (horizontal or vertical). But as soon as I have a more complex line, the calculation of the minimum distance between the new point and the existing points can yield wrong results because my algorithm does not move along the path of the line.

The 2nd problem my current alogrithm has, is that I don't know if I need to insert the new point before or after the point to which it is closest. That is why I added the 'directon.compare' stuff.

theres no standard algorithm for that.
try something like the shortest perpendicular distance from the path between two points

0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

I had the same challenge a while back. The solution is not that straight-forward as it involves both projection and checking against end-points. Anyway, the attached c++ code should give you:

The shortest distance from point to a polygon - useful for determining if the user actually hit near the polygon. You could set 5-10 pixels as the limit.

The projection of the point onto the polygon.

The index of the nearby point.

Hope it answers your request even though you might need some adjustment as I've used STL-classes. Also, DistancePointToPoint is the Eucledian distance.

Best regards,
Rasmus

/** 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;};

It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for freeEdge Out The Competitionfor your dream job with proven skills and certifications.Get started todayStand Outas the employee with proven skills.Start learning today for freeMove Your Career Forwardwith certification training in the latest technologies.Start your trial today

Open in new window