Thread: 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();
 
		// Add points to polygon
		int x = 0;
		for (Iterator<Point> i = zone.iterator(); i.hasNext();) {
			i.next();
 
			// clean up the zone
 
			// If allowed, at point to polygon
			poly.addPoint(zone.get(x).x, zone.get(x).y);
 
			System.out.println("Point added: " + zone.get(x));
			x++;
		}
 
		/*
		 * Other way of iterating
		 * for (int x = 0; x < zone.size(); x++) {
		 * 		// clean up the zone
		 * 
		 * 		// If allowed, at point to polygon
		 * 		poly.addPoint(zone.get(x).x, zone.get(x).y);
		 * 
		 * 		System.out.println("Point added: " + zone.get(x));
		 * }
		 */
	}
 
	public static void main(String[] args) {
		new PolyCheck();
	}
}

@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?

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.

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>();
		zone.add(p0);
		zone.add(p1);
		zone.add(p2);
		zone.add(p3);
		zone.add(p4);
		zone.add(p5);
		zone.add(p6);
 
		Polygon poly = new Polygon();
 
		// just a counter because I cannot use i (since items can be removed)
		int counter = 0;
 
		// Add points to polygon
		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 {
					poly.addPoint(zone.get(i.nextIndex()).x,
							zone.get(i.nextIndex()).y);
					System.out.printf("      Point %s added.\n", counter);
				}
 
			} catch (Exception e) {
			}
			i.next();
			counter++;
		}
	}
 
	public static void main(String[] args) {
		new PolyCheck();
	}
}

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.

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>();
		zone.add(p0);
		zone.add(p1);
		zone.add(p2);
		zone.add(p3);
		zone.add(p4);
		zone.add(p5);
		zone.add(p6);
 
		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) {
				pointsToRemove.add(zone.get(n));
			}
		}
		System.out.println("Removed points: " + pointsToRemove.size());
 
		zone.removeAll(pointsToRemove);
 
		for (int n = 0; n < zone.size(); n++) {
			poly.addPoint(zone.get(n).x, zone.get(n).y);
			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!

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