Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: Algorithym to remove unnecessary points

1. ## Algorithym to remove unnecessary points

Hi all,

I have a class in which I convert a list of points to a polygon (and do some other things). Before adding the points to the polygon I would like to check if it is really necessary to add it. For instance, I know point B is precisely in the middle of point A and C. Therefore, if I draw a line from point A to point C, I do not have to add point B to the polygon. So, my question is how I can check for UNnecessary points. I have thought of some dirty algorithms but I need at least 50 lines of code. I guess that can be done smarter. If anybody knows a nice, quick to process way of doing, would you tell me, please?

In the method I have an iterating loop, already. Please note that I cannot use 'for(Point p : zone)' for this loop because of other calculations in the method. I can use (the other) two ways of iterating over it, as you can see in the demo. As I am looking for the nicest and easiest way to process, I would like to use my current iterating loop.

I created a workable demo.

```import java.awt.Point;
import java.awt.Polygon;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class PolyCheck {

PolyCheck() {
List<Point> zone = new ArrayList<Point>();
zone.add(new Point(0, 0)); // Point A
zone.add(new Point(1, 0)); // Point B -> UNnecessary
zone.add(new Point(2, 0)); // Point C
zone.add(new Point(2, 2)); // Point D
zone.add(new Point(0, 2)); // Point E

Polygon poly = new Polygon();

int x = 0;
for (Iterator<Point> i = zone.iterator(); i.hasNext();) {
i.next();

// clean up the zone

// If allowed, at point to polygon

x++;
}

/*
* Other way of iterating
* for (int x = 0; x < zone.size(); x++) {
* 		// clean up the zone
*
* 		// If allowed, at point to polygon
*
* 		System.out.println("Point added: " + zone.get(x));
* }
*/
}

public static void main(String[] args) {
new PolyCheck();
}
}```  Reply With Quote

2. ## The Following User Says Thank You to Vinvar For This Useful Post:

ChristopherLowe (August 14th, 2014)

4. ## Re: Algorithym to remove unnecessary points

Ah terrific question! One of the best I've seen for a long time. This happens to be very close to me because I've recently be trying to optimise shape files for use on a tablet.

My solution was to calculate the distance between the point before and the point after then compare it to the sum of the distance between that point and the one after and the one before. If it's below a certain tolerance it can be removed.

Christ that sounds illiterate. Let me re-word it.

Take point B (1, 0). Calculate the distance between point A (0, 0) and point C (2, 0). The answer it 2. The distance between point A and point B is 1. The distance between point B and point C is 1. The sum of A->B and B->C is 2 and the distance between A->C is also 2. Therefore the angle of incidence between A->B and B->C is zero (it forms a straight line) which is below my threshold so B can be removed without effecting the geometry of the shape!

The tolerance, that is the vector difference between A->C and (A->B + B->C) can be increased to reduce geometry at the expense of geometrical accuracy. I should also add that you need to apply this algorithm linearly to every point before making changes to the data points or you could end up culling things that you were not supposed to. You can repeat this algorithm quadratically to remove consecutive useless points at the expense of a little processing time.

edit
If anyone can provide a better / more elegant / more efficient solution I will buy them a coffee.  Reply With Quote

5. ## Re: Algorithym to remove unnecessary points

@ChristopherLowe, re: your approach, how do you determine that point B is a candidate for removal when considering the two points A and C? Did you only do straight lines, or did you have to develop similar approaches for curves? What did you use for a threshold?  Reply With Quote

6. ## Re: Algorithym to remove unnecessary points

As far as I understood you just want to know if the line from A to B has the same angle as the line from B to C.
This should not be very hard, but for many points this can be quite a number of computations to do.  Reply With Quote

7. ## Re: Algorithym to remove unnecessary points Originally Posted by GregBrannon @ChristopherLowe, re: your approach, how do you determine that point B is a candidate for removal when considering the two points A and C? Did you only do straight lines, or did you have to develop similar approaches for curves? What did you use for a threshold?
My data set was entirely linear point geometry like OP's. The threshold I used was originally hard coded but after field testing we used the rendering time and number of culled points to adjust the threshold. Taking too long to render? Bump up the threshold. Removing too much geometry? Bump it down and make the user wait. It's not perfect and it takes a bit of hand holding to get the right balance but it's a massive step forwards in handling the ridiculous nature of the data our app is expected to handle.

If the data was for curved geometry it would require some calculus. I've never really thought about this but my approach would be to calculate the turning point (where the second derivative of the curve equals zero) of that same A->C .. (A->B + B->C) relationship and use this as a culling threshold. IE. Not much change in curvature, it can be removed. Originally Posted by Cornix As far as I understood you just want to know if the line from A to B has the same angle as the line from B to C.
This should not be very hard, but for many points this can be quite a number of computations to do.
Rendering this geometry is an order of magnitude more expensive than retrieving it from primary storage, which itself is an order of magnitude more expensive than a few silly nested loops and trigonomic operations.

Think of it this way. If you are making a game rendering occurs every single frame. In my case (a mapping application) rendering a polygon sits on top of a massively complex map service of which I have no control over. This pre-rendering simplification of the geometry occurs once at load time.  Reply With Quote

8. ## Re: Algorithym to remove unnecessary points

More than one way to skin a cat. Here's a more mathematical way to look at it: be it a straight line or a curve, the line/curve between two points can be specified by a math function (for a line this can be thought of as the typical equation of a line y=mx +b, more complex curves by more complex functions such as a quadratic bezier):

y = f(x)

To test a point in 2D, plug in its 'x' value into the function, and test the 'y' for equality against the result (note one can round the result if using int precision, or for floating point one can specify a precision value)  Reply With Quote

9. ## Re: Algorithym to remove unnecessary points

Thank you all for your quick reply. ChristopherLowe, thanks for the compliment about my question. Unfortunately, I am afraid the next questions will be noobish ones...

The assumption was right: it will be straight lines, not curved ones. I am calculating the distance between the points, as you suggested. I do get the first UNnecessary point to be removed. However, the following errors occur:
• The program adds point 0. Based on the code, it should be marked as redundant because of point 6.
• The program does not add point 6, which should be added (or called redundant if the program adds point 0).
• The program adds point 3, which is redundant.

Can anyone tell me what I am doing wrong, please?

Off course with workable demo:
```import java.awt.Point;
import java.awt.Polygon;
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class PolyCheck {

List<Point> zone;

PolyCheck() {
Point p0 = new Point(0, 0);// Point 0
Point p1 = new Point(1, 0);// Point 1 -> UNnecessary
Point p2 = new Point(2, 0);// Point 2
Point p3 = new Point(2, 1);// Point 3 -> UNnecessary
Point p4 = new Point(2, 2);// Point 4
Point p5 = new Point(0, 2);// Point 5
Point p6 = new Point(0, 0);// Point 6 -> UNnecessary

zone = new ArrayList<Point>();

Polygon poly = new Polygon();

// just a counter because I cannot use i (since items can be removed)
int counter = 0;

for (ListIterator<Point> i = zone.listIterator(); i.hasNext();) {
// clean up the zone
try {

// The program think these values could not be initialized.
// Therefore, set it to ridiculous values.
Point tempAC = new Point(9, 9);
Point tempAB = new Point(10, 10);

// Check if the first point and the last point are the same
if (i.nextIndex() == 0) {
System.out.printf("Point %s: %s \n", counter,
zone.get(i.nextIndex()));
tempAC = new Point(zone.get(i.nextIndex() + 1));
tempAC.distance(zone.get(zone.size() - 1));
System.out.println("     AC: " + tempAC);
tempAB = new Point(zone.get(i.nextIndex()));
tempAB.distance(zone.get(zone.size() - 1));
System.out.println("     AB: " + tempAB);
Point tempBC = new Point(zone.get(i.nextIndex()));
tempBC.distance(zone.get(i.nextIndex() + 1));
System.out.println("     BC: " + tempBC);

tempAB.translate(tempBC.x, tempBC.y);
System.out.println("AB + BC: " + tempAB);
}
// Check all other points
else {
System.out.printf("Point %s: %s \n", counter,
zone.get(i.nextIndex()));
tempAC = new Point(zone.get(i.nextIndex() + 1));
tempAC.distance(zone.get(i.previousIndex()));
System.out.println("     AC: " + tempAC);
tempAB = new Point(zone.get(i.nextIndex()));
tempAB.distance(zone.get(i.previousIndex()));
System.out.println("     AB: " + tempAB);
Point tempBC = new Point(zone.get(i.nextIndex()));
tempBC.distance(zone.get(i.nextIndex() + 1));
System.out.println("     BC: " + tempBC);

tempAB.translate(tempBC.x, tempBC.y);
System.out.println("AB + BC: " + tempAB);
}

if (tempAC.equals(tempAB)) {
System.out.println("  B is redundant");
i.remove();
} else {
zone.get(i.nextIndex()).y);
}

} catch (Exception e) {
}
i.next();
counter++;
}
}

public static void main(String[] args) {
new PolyCheck();
}
}```  Reply With Quote

10. ## Re: Algorithym to remove unnecessary points

Uhm, maybe I'm way off here. Why not construct a Line2D and use the contains method? I have not thought this through, but that's what I thought about first.  Reply With Quote

11. ## Re: Algorithym to remove unnecessary points

Looking at your code in Post 7, the problem seems different that you've described. In Post #7, there is a List of 7 points, and the task is to find which are redundant, adding only those that are not redundant to a new List of Points. Redundant points are those not needed to define the outline of the polygon within some threshold.

For that, I would think the first task would be to define the outline of the polygon and identify the points that define it. The example points chosen for Post #7 may be too simple, but it's okay to start with the simple case. In this simple case, the polygon boundary contains only horizontal and vertical lines, so simple logic can be used to identify the corners of the polygon:

the coordinate with the

1. least x and least y: (0, 0)
2. least x and greatest y: (0, 2)
3. greatest x and least y: (2, 0)
4. greatest x and greatest y: (2, 2)

Once the boundary or outline of the polygon is (roughly) determined, the remaining points can be evaluated for redundancy. I add 'roughly' defined, because as the simple case is expanded to include the more complex, there will be points not chosen by steps 1 - 4 above that may be required to define the polygon. For example, adding a tiny bit of complexity, consider the additional points (1, 1.5) or (2.5, 1).

I'm sure that CL has worked through all this, so his comments will likely be more useful.

Another thought: And how does one know if the 4 steps above are sufficient for a shape that has 5, 6, 8, or 10 sides? I suspect there may be other considerations as the shape's complexity increases.  Reply With Quote

12. ## Re: Algorithym to remove unnecessary points Originally Posted by PhHein Uhm, maybe I'm way off here. Why not construct a Line2D and use the contains method? I have not thought this through, but that's what I thought about first.
Unfortunately not feasible. From the API for Line2D.contains:

Tests if a given Point2D is inside the boundary of this Line2D. This method is required to implement the Shape interface, but in the case of Line2D objects it always returns false since a line contains no area.  Reply With Quote

13. ## The Following User Says Thank You to copeg For This Useful Post:

PhHein (August 18th, 2014)

14. ## Re: Algorithym to remove unnecessary points

@Vinvar - Some of your assumptions are incorrect. The first and last points should *never* be culled. They are critical in defining the geometry and removing Point 6 in your example turns it from a closed polygon to an open polyline. Secondly, a point with the same (x, y) as another point cannot be safely culled. Imaging a bowtie shaped twisted polygon. There could easily exist two points (at the intersection) that happen to be at the same (x, y) but will drastically alter the geometry if removed. Finally, you cannot alter the geometry while iterating over the points. It's just plain messy and you need to rinse and repeat the entire process

Now the theoretical stuff is out of the way how about something practical. Start by creating a way of measuring the distance between two points.

`double distanceBetweenPoint(Point p1, Point p2)`

I'll leave the implementation up to you. It's elementary school mathematics. Just make sure it's well tested.

```List<Points> pointsToRemove = new ArrayList<Points>();
double threshold = 0.1;  // TODO: magic number

for (int n = 1; n < points.size(); n++) {

Point previous = points.get(n - 1);
Point next = points.get(n + 1);
Point current = points.get(n);

double nextToPrevious = distanceBetweenPoints(previous, next);
double ordinal = distanceBetweenPoints(previous, current) + distanceBetweenPoints(current, next);

if ( Math.abs( nextToPrevious - ordinal ) < threshold ) {
pointsToRemove( points.get(n) );
}

}

points.removeAll( pointsToRemove );```

--- Update --- Originally Posted by GregBrannon Looking at your code in Post 7, the problem seems different that you've described. In Post #7, there is a List of 7 points, and the task is to find which are redundant, adding only those that are not redundant to a new List of Points. Redundant points are those not needed to define the outline of the polygon within some threshold.

For that, I would think the first task would be to define the outline of the polygon and identify the points that define it. The example points chosen for Post #7 may be too simple, but it's okay to start with the simple case. In this simple case, the polygon boundary contains only horizontal and vertical lines, so simple logic can be used to identify the corners of the polygon:

the coordinate with the

1. least x and least y: (0, 0)
2. least x and greatest y: (0, 2)
3. greatest x and least y: (2, 0)
4. greatest x and greatest y: (2, 2)

Once the boundary or outline of the polygon is (roughly) determined, the remaining points can be evaluated for redundancy. I add 'roughly' defined, because as the simple case is expanded to include the more complex, there will be points not chosen by steps 1 - 4 above that may be required to define the polygon. For example, adding a tiny bit of complexity, consider the additional points (1, 1.5) or (2.5, 1).

I'm sure that CL has worked through all this, so his comments will likely be more useful.

Another thought: And how does one know if the 4 steps above are sufficient for a shape that has 5, 6, 8, or 10 sides? I suspect there may be other considerations as the shape's complexity increases.
I think this is the wrong approach for a given piece of straight line geometry. You are only really concerned if a given point adds geometrical significance with respect to the point that comes before and the one that comes after. If a point does nothing but reinforce a straight line it can be removed and the shape remains visibly identical. The extents of the shape and even the shape itself have no relevance in this.  Reply With Quote

15. ## The Following User Says Thank You to ChristopherLowe For This Useful Post:

Vinvar (August 15th, 2014)

16. ## Re: Algorithym to remove unnecessary points

CL, thank you very much. Once again I solved it, see the solution below. Much better then the 50+ LoC I came up with (twice)!
I do need to mention that in my case only the x OR y value can change. This because I am not allowing diagonal lines. Also, I know for certain X and Y are integers. based on earlier calculations/transformations.
Therefore the double 'threshold' and method 'distanceBetweenPoints' are fairly easy. You could argue I do not even have to calculate it as a double.

```import java.awt.Point;
import java.awt.Polygon;
import java.util.ArrayList;
import java.util.List;

public class PolyCheck {

List<Point> zone;
List<Point> pointsToRemove;

Polygon poly;

PolyCheck() {
Point p0 = new Point(0, 0);// Point 0
Point p1 = new Point(1, 0);// Point 1 -> UNnecessary
Point p2 = new Point(2, 0);// Point 2
Point p3 = new Point(2, 1);// Point 3 -> UNnecessary
Point p4 = new Point(2, 2);// Point 4
Point p5 = new Point(0, 2);// Point 5
Point p6 = new Point(0, 0);// Point 6

zone = new ArrayList<Point>();

pointsToRemove = new ArrayList<Point>();

poly = new Polygon();

// As I only have changing X OR Y values, this can be anything below 0.9
// If you would have changing X AND Y values, you need to calculate this
// double every time (or change the distanceBetweenPoints method).
double threshold = 0.1;

for (int n = 1; n < zone.size() - 1; n++) {

Point previous = zone.get(n - 1);
Point next = zone.get(n + 1);
Point current = zone.get(n);

double nextToPrevious = distanceBetweenPoints(previous, next);
double ordinal = distanceBetweenPoints(previous, current)
+ distanceBetweenPoints(current, next);

if (Math.abs(nextToPrevious - ordinal) < threshold) {
}
}
System.out.println("Removed points: " + pointsToRemove.size());

zone.removeAll(pointsToRemove);

for (int n = 0; n < zone.size(); n++) {
System.out.println("Zone point: " + zone.get(n));
}
}

private double distanceBetweenPoints(Point p1, Point p2) {
return p1.distance(p2);
}

public static void main(String[] args) {
new PolyCheck();
}
}```

Thanks everybody for helping and solving!  Reply With Quote

17. ## Re: Algorithym to remove unnecessary points Originally Posted by ChristopherLowe If the data was for curved geometry it would require some calculus....
I can't imagine anyone would find this interesting but myself, however something came across my desk the other day that was sort of relevant to this. We needed to simplify closed, non-linear geometry without too much impact on the overall shape. My solution was to calculate the area of the polygon, remove a point and compare the new area. It's a similar idea to my previous answer (about comparing angular changes and using a threshold for culling) however it works for both linear and non-linear shapes.  Reply With Quote

18. ## Re: Algorithym to remove unnecessary points

Sorry for being late to this topic
One question anyway ... what is largest polygon size you have tested your algorithm ?  Reply With Quote 