[Webinar] Streamline your web hosting managementRegister Today

x
Solved

# Manually insert a point into a line

Posted on 2010-04-08
Medium Priority
438 Views
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)
}
};
``````
0
Question by:kloeber
• 7
• 4

LVL 1

Author Comment

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

LVL 92

Expert Comment

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

LVL 1

Author Comment

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

LVL 92

Expert Comment

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

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

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

LVL 92

Expert Comment

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

LVL 1

Author Comment

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

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

ID: 30198551
ok, I will look into that.

Thanx for thoughts...
0

LVL 1

Assisted Solution

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

LVL 1

Author Comment

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

## Featured Post

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…
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