Manually insert a point into a line

Folk'ses,

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

Open in new window

LVL 1
kloeberAsked:
Who is Participating?
I wear a lot of hats...

"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.

kloeberAuthor Commented:
Following is the compare stuff:
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); }
    };

Open in new window

0
objectsCommented:
you need to define the algorithm, there is no standard one.
0
kloeberAuthor Commented:
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
Introducing Cloud Class® training courses

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.

objectsCommented:
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
0
kloeberAuthor Commented:
@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.
0
kloeberAuthor Commented:
following is how I create and draw the line:
:
        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);
:

Open in new window

0
objectsCommented:
I mean how do you define where in the path it should be added
0
kloeberAuthor Commented:
so that I can draw a consecutive line:

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.
 
0
objectsCommented:
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.

Start your 7-day free trial
kloeberAuthor Commented:
ok, I will look into that.

Thanx for thoughts...
0
rkursemCommented:
Hi Kloeber,

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

Open in new window

0
kloeberAuthor Commented:
thanks objects and rekursem!
Using the distance between the new point and the line segments does the trick:
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;
    }
}

Open in new window

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

From novice to tech pro — start learning today.