Basic issues

[ghost]

I have some basic issues when I run your code the code fails in two tests.

In "test2" why can I not split the polygon into more than four (4) areas?

Say I have a 10,000 x 10,000 square I might want to create a mesh with lots of areas.

In "test3" why can I not split a triangle (this is a polygon) ?

It seems like any sort of polygon splitter should be able to handle a triangle.

Looking forward to some answers/explanations - I don't really see any mistakes on my part. Note I am using Java8 and the latest GIT along with the latest JTS

package de.incentergy.geometry;

import java.util.List;
import com.vividsolutions.jts.geom.Polygon;
import com.vividsolutions.jts.io.WKTReader;
import de.incentergy.geometry.PolygonSplitter;
import de.incentergy.geometry.impl.GreedyPolygonSplitter;

public class Qtest2 {

    private static final PolygonSplitter polygonSplitter = new GreedyPolygonSplitter();

    public static void test1() {
    	System.err.println ("==================================================");
    	System.err.println ("BEG: running test method "+new Exception().getStackTrace()[0].getMethodName());
    	try {
			WKTReader wktReader = new WKTReader();
			Polygon polygon = (Polygon) wktReader.read("POLYGON ((0 0, 100 0, 100 100, 50 50, 0 0))");
			List<Polygon> parts = polygonSplitter.split(polygon, 4);
			System.err.println("SUCCESS: "+0+" split into " + parts.size());
    	} catch (Exception e) {
    		e.printStackTrace();
    		System.err.println("FAILED");
    	}
    }

    public static void test2() {
    	// like test1 but trys for five (5) area - why does this fail ?
    	System.err.println ("==================================================");
    	System.err.println ("BEG: running test method "+new Exception().getStackTrace()[0].getMethodName());
    	try {
			WKTReader wktReader = new WKTReader();
			Polygon polygon = (Polygon) wktReader.read("POLYGON ((0 0, 100 0, 100 100, 50 50, 0 0))");
			List<Polygon> parts = polygonSplitter.split(polygon, 5);
			System.err.println("SUCCESS: "+0+" split into " + parts.size());
    	} catch (Exception e) {
    		e.printStackTrace();
    		System.err.println("FAILED");
    	}
    }

    public static void test3() {
    	// this is a triangle - why does it fail ? 
    	System.err.println ("==================================================");
    	System.err.println ("BEG: running test method "+new Exception().getStackTrace()[0].getMethodName());
    	try {
			WKTReader wktReader = new WKTReader();
			Polygon polygon = (Polygon) wktReader.read("POLYGON ((0 0, 100 0, 100 100, 0 0))");
			List<Polygon> parts = polygonSplitter.split(polygon, 2);
			System.err.println("SUCCESS: "+0+" split into " + parts.size());
    	} catch (Exception e) {
    		e.printStackTrace();
    		System.err.println("FAILED");
    	}
    }

    public static void main(String [] args) {
    		test1();
    		test2(); // fails
    		test3(); // fails
    }
}

The output when run ....

==================================================
BEG: running test method test1
SUCCESS: 0 split into 4
==================================================
BEG: running test method test2
java.util.NoSuchElementException: No value present
	at java.util.Optional.get(Unknown Source)
	at de.incentergy.geometry.impl.GreedyPolygonSplitter.split(GreedyPolygonSplitter.java:82)
	at de.incentergy.geometry.impl.GreedyPolygonSplitter.split(GreedyPolygonSplitter.java:38)
	at de.incentergy.geometry.Qtest2.test2(Qtest2.java:38)
	at de.incentergy.geometry.Qtest2.main(Qtest2.java:64)
FAILED
==================================================
BEG: running test method test3
java.util.NoSuchElementException: No value present
	at java.util.Optional.get(Unknown Source)
	at de.incentergy.geometry.impl.GreedyPolygonSplitter.split(GreedyPolygonSplitter.java:82)
	at de.incentergy.geometry.impl.GreedyPolygonSplitter.split(GreedyPolygonSplitter.java:38)
	at de.incentergy.geometry.Qtest2.test3(Qtest2.java:53)
	at de.incentergy.geometry.Qtest2.main(Qtest2.java:65)
FAILED

[grimsa]

First of all, thank you for reporting the issue.

This is a project I did a while ago for a company called Incentergy. As you see, it was never truly finalized, but I'll reach out to them to see if they have improved the code further and if they could share it.
I'm not planning to do major development because I am not using this library myself. But you are welcome to contribute, and I could help you as well if you can pinpoint the problem and it is not too difficult to fix.

Now if we look at the issue, it could be a problem with the algorithm itself not supporting some edge case. You could try to verify this by running the algorithm on paper or using alternate implementations (C++ or JS, linked in the original article's comments).

If there is no issue there, then it's just a problem with this implementation. If you could provide a unit test for it (some input and expected precise output), it would help. If you could debug the code and pinpoint the issue, that would be even better.