[Webinar] Streamline your web hosting managementRegister Today

x
?
Solved

Manually insert a point into a line

Posted on 2010-04-08
12
Medium Priority
?
438 Views
Last Modified: 2012-05-09
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

0
Comment
Question by:kloeber
  • 7
  • 4
12 Comments
 
LVL 1

Author Comment

by:kloeber
ID: 30116689
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
 
LVL 92

Expert Comment

by:objects
ID: 30150444
you need to define the algorithm, there is no standard one.
0
 
LVL 1

Author Comment

by:kloeber
ID: 30176603
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
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 
LVL 92

Expert Comment

by:objects
ID: 30177455
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
 
LVL 1

Author Comment

by:kloeber
ID: 30180901
@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
 
LVL 1

Author Comment

by:kloeber
ID: 30181405
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
 
LVL 92

Expert Comment

by:objects
ID: 30187355
I mean how do you define where in the path it should be added
0
 
LVL 1

Author Comment

by:kloeber
ID: 30188915
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
 
LVL 92

Accepted Solution

by:
objects earned 1200 total points
ID: 30189508
theres no standard algorithm for that.
try something like the shortest perpendicular distance from the path between two points
0
 
LVL 1

Author Comment

by:kloeber
ID: 30198551
ok, I will look into that.

Thanx for thoughts...
0
 
LVL 1

Assisted Solution

by:rkursem
rkursem earned 800 total points
ID: 30229654
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
 
LVL 1

Author Comment

by:kloeber
ID: 30497895
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

Featured Post

Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:
Suggested Courses
Course of the Month10 days, 11 hours left to enroll

612 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question