Code Monkey home page Code Monkey logo

Comments (4)

jillesvangurp avatar jillesvangurp commented on September 25, 2024

Interesting, it's been a while since I did anything on this code base. The problem with the example above (for the algorithm) is that in this case all of the points lie outside each other's polygon. So it fails to find an overlap.

A fix could be to check for line intersection for each segment as well. If any of the lines intersect, the polygons overlap. It should be possible to reuse the linesCross method for this. This will make things a bit slower of course but not massively. There may be some more efficient algorithms out there for this.

Feel free to provide a PR. If not, I might look at this at some point but very low priority for me. In any case, thanks for reporting this.

from geogeometry.

sashadu avatar sashadu commented on September 25, 2024

Yes. These are existing test polygons:
test1
Polygons p, p2 and p4 centers are very close and lie inside each other, so it is simple.
Consider this example:
test2
(p3 overlaps with p5).

Or even this:
test3
(p3 does not overlap with p6).

Here is my version of shouldOverlap test which fails (p5overlapP3 is yellow polygon on the image above, p6aroundP3 is magenta) :

`
public void shouldOverlap() {
double[][] polygon = new double[][] {
{50, 15},
{53, 15},
{53, 11},
{50, 11}
};

	double[][] p2overlapping = new double[][] {
			{51, 16},
			{52, 16},
			{52, 10},
			{51, 10}
	};
	double[][] p3outside = new double[][] {
			{60, 15},
			{63, 15},
			{63, 11},
			{60, 11}
	};
	double[][] p4inside = new double[][] {
			{51, 14},
			{52, 14},
			{52, 12},
			{51, 12}
	};
	// polygon which overlaps with p3 but does not have center or any vertexes inside the p3
	double[][] p5overlapP3 = new double[][] {
			{60.3, 10},
			{60.3, 22},
			{61, 22},
			{61, 10}
	};
	// polygon which lays around the p3 without overlapping
	// polygon 6 is concave with its center lying outside of p6 but inside the p3
	double[][] p6aroundP3 = new double[][] {
		{	63.39152174400882 , 16.3916015625 },
		{	63.38167869302983 , 17.2705078125 },
		{	64.30182213914463 , 17.02880859375 },
		{	64.24459476798195 , 8.349609375 },
		{	58.790978406215565, 8.349609375 },
		{	58.83649009392136 , 16.040039062499996  },
		{	59.40036514079251 , 16.171875 },
		{	59.377988012638895, 9.3603515625 },
		{	63.763065186029074, 9.3603515625 },
		{	63.918058296491104, 16.34765625 }
	};

	Assert.assertTrue(GeoGeometry.overlap(polygon,polygon));

	Assert.assertTrue(GeoGeometry.overlap(polygon, p2overlapping));
	Assert.assertTrue(GeoGeometry.overlap(p2overlapping,polygon));

	Assert.assertFalse(GeoGeometry.overlap(p3outside,polygon));
	
	Assert.assertTrue(GeoGeometry.overlap(polygon,p4inside));
	Assert.assertTrue(GeoGeometry.overlap(p4inside,polygon));

	// with overlap logic which check only center and vertexes this test fails
	// edge intersections should be checked as well
	Assert.assertTrue(GeoGeometry.overlap(p3outside,p5overlapP3));
	Assert.assertTrue(GeoGeometry.overlap(p5overlapP3, p3outside));

	// this test also fails because of the center logic.
	// polygon 6 is concave with its center lying outside of p6 but inside the p3
	// they do not overlap
	Assert.assertFalse(GeoGeometry.overlap(p3outside,p6aroundP3));
	Assert.assertFalse(GeoGeometry.overlap(p6aroundP3, p3outside));
}

`

from geogeometry.

jillesvangurp avatar jillesvangurp commented on September 25, 2024

Thanks for clarifying, I'll spend some time on improving this when I have a free moment.

from geogeometry.

jillesvangurp avatar jillesvangurp commented on September 25, 2024

I finally looked into this. The algorithm does not support concave polygons currently. p6 is concave. I added a clarification on this. Wikipedia hints at an algorithm that we might use but that would be a bit more work. https://en.wikipedia.org/wiki/Point_in_polygon

from geogeometry.

Related Issues (20)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.