dlegland/javageom

Geometry library for Java

javageom's Issues

Polygon contain point returns false when inside, true when outside

I wanted to add this issue for others to lookup because it was so confounding -- our code was working fine and then we did some refactoring and changed our coordinate system a little. Then SimplePolygon2D.contains stopped working.

I was about to file a bug to see if we were crazy and found this which I think resolves it:

https://sourceforge.net/p/geom-java/discussion/618722/thread/6372ebe7/

Here's the background -- We graphed the polygon here:

https://www.desmos.com/calculator/fqfjo4mas0

Point: Point2D(500.0, 492.0)
Polygon:
  Point2D(1004.8166973359963, 657.5808589179162)
  Point2D(1048.4349833808149, 677.6169544086146)
  Point2D(1073.480102744188, 623.0940968525913)
  Point2D(1029.8618166993692, 603.0580013618929)
  Point2D(1017.1841976564538, 544.4126436990506)
  Point2D(995.3750546340445, 534.3945959537014)
  Point2D(915.8070777146482, 563.8723341463516)
  Point2D(895.7709822239499, 607.4906201911701)
  Point2D(925.2487204166001, 687.0585971105664)
  Point2D(968.8670064614187, 707.0946926012648)

Dumped it when contains() was True

public boolean contains(Point2D point) {
		for (SimplePolygon2D poly : polygons()) {
			if (poly.contains(point)) {
				System.out.print("Point: ");
				System.out.print(point);
				System.out.print("\n");
				System.out.print("Polygon:\n");
				for (Point2D pt : poly.vertices()) {
					System.out.print("  ");
					System.out.print(pt);
					System.out.print("\n");
				}
				return true;
			}
		}
		return false;
	}

Turns out our polygon is now defined CW due to some other changes we made.

In the above link, David says:

Hi,

this is because your polygon is oriented Clockwise (CW). The convention in the library is to consider point within polygon by taking into account polygon orientation. This allows working with polygon with holes.

You can solve your problem by several ways:

• check both contains and getSignedArea method. The point is isinside the enclosing area if the condition is met:
  boolean z = p.contains(136.0,124.0) ^ p.getSignedArea()<0;
• use the complement of the polygon (method p.complement())

regards,
David

And the original poster fixed it by doing:

The problem is solved when I make sure the polygon is oriented counter-clockwise:

if (p.getSignedArea()<0)
p = p.complement();

Publish to maven central

Can you please publish 0.11.3 to maven central?

RuntimeException for a undefined StraightLine

Hello,

we found something but we are not sure if this is intended or a bug. We think it shouldn't be possible to create a StraightLine with two (nearly) identical points, because it leads to a RuntimeException.

@Test
public void javaGeomCircleStraightLine2DIntersection2() {
    // if center and point are equals, intersections method throw an exception
    Point2D center = new Point2D(174980.60, 66497.20);
    Point2D point = new Point2D(174980.60, 66497.20);
    StraightLine2D straightLine2D = new StraightLine2D(center, point);
    Circle2D circle = new Circle2D(center, 274.10);
    Collection<Point2D> circleIntersections = circle.intersections(straightLine2D);
    Assert.assertTrue(circleIntersections.isEmpty());
 }

@Test
public void javaGeomCircleStraightLine2DIntersection2() {
    // if center and point are equals, intersections method throw an exception
    Point2D center = new Point2D(174980.6000001, 66497.20);
    Point2D point = new Point2D(174980.60, 66497.20);
    StraightLine2D straightLine2D = new StraightLine2D(center, point);
    Circle2D circle = new Circle2D(center, 274.10);
    Collection<Point2D> circleIntersections = circle.intersections(straightLine2D);
    Assert.assertTrue(circleIntersections.isEmpty());
 }

Performance: Add sqDistance function

Hello,

assume you have million of points and you would like to find the point closest to line, polygon ...
It would be a lot faster if you could just calculate the square distance. And find smallest square distance value. With this it is possible to save for each distance calculation at least one Math.hypot().

kind regards
Christian

LineSegment distance doesn't work if LineSegment2D is based on identical points

Hello,

the following test fails, because the LineSegment2D has been created with two identical points.
In my opionen it is fine to create a line segment with two identical points in contrast to a straight line. If so the distance should still be possible.

@Test
public void javaGeomLineSegment2DDistanceTest() {
    final LineSegment2D lineA = new LineSegment2D(244059.964, 151370.04000000003, 244059.964, 151370.04000000003);
    lineA.distance(new Point2D(246599.964, 151370.03000000003));
}

sincerely
christian

math package problems in Scala

It's very common for scala developers to use the scala.math package without the scala prefix as it's imported by default. Naming your package math conflicts with this such that simply JavaGeom as a dependency will break the build - it can't find math.max, math.round etc. Maybe you should have prefixed it with your own package to avoid these conflicts? Could the library use some package e.g. dlegland.javageom.math or just javageom.math so it can be also used in Scala?

LinearRing.isInside SimplePolgon2d.contains : incorrect for anti-clockwise case

The isInside and contains methods have the following test

if (area > 0) {
    	return winding == 1;
} else {
    	return winding == 0;
}

I believe the code should be

if (area > 0) {
   return winding == 1;
 } else {
  return winding == -1;
}

This can be tested with the following simple example

		double[] xcoords0 = {0.0, 0.0, 10.0, 10.0, 0.0};
		double[] ycoords0 = {0.0, 10.0, 10.0, 0.0, 0.0};
		LinearRing2D ringCW = new LinearRing2D(xcoords0, ycoords0);

		// anti-clockwise 
		double[] xcoords1 = {0.0, 10.0, 10.0, 0.0, 0.0};
		double[] ycoords1 = {0.0, 0.0, 10.0, 10.0, 0.0};
		LinearRing2D ringACW = new LinearRing2D(xcoords1, ycoords1);

		System.out.println(ringCW.isInside(1.0, 1.0));
		System.out.println(ringCW.isInside(10.5, 10.5));
		
		System.out.println(ringACW.isInside(1.0, 1.0));
		System.out.println(ringACW.isInside(10.5, 10.5));

StraightLine intersection doesn't work properly.

Hello,

I found some cases where the StraightLine2D intersection doesn't work. I added a test case to reproduce this. I would expect that for all lines (1-4) an intersection occurs.

@Test
public void javaGeomIntersection() {

    StraightLine2D line2d = new StraightLine2D(110337.28297120638, 48934.88776858141, 1650.316028793619, 1052.3122314185894);

    StraightLine2D line1 = new StraightLine2D(110083.599, 47397.2, 3808.0, 0.0);
    StraightLine2D line2 = new StraightLine2D(113891.599, 47397.2, 0.0, 5180.0);
    StraightLine2D line3 = new StraightLine2D(113891.599, 52577.2, -3808.0, 0.0);
    StraightLine2D line4 = new StraightLine2D(110083.599, 52577.2, 0.0, -5180.0);

    assertNotNull(line2d.intersection(line1));
    assertNotNull(line2d.intersection(line2));
    assertNotNull(line2d.intersection(line3));
    assertNotNull(line2d.intersection(line4));
}

If you need any further information just let me know.

StraighLine intersection with a circle doesn't work

Hello,

A fellow found the following bug:

@Test
public void javaGeomCircleStraightLine2DIntersection() {
  Point2D center = new Point2D(44729.600000000006, 7264.400000000001);
  Point2D point = new Point2D(44501.100000000006, 7010.400000000001);       
  StraightLine2D curveAssemblyPointToCenter = new StraightLine2D(center, point);
  Circle2D circle = new Circle2D(center, 250);  
  Collection<Point2D> circleIntersections = circle.intersections(curveAssemblyPointToCenter);
  Assert.assertEquals(2, circleIntersections.size());
}

LineSegment2D contains doesn't work reliable for some input

Hello,

I stumbled over a problem regarding the contains method. Checking if a projection is part of a line (containsProjection) returns true, but calling contains with the projected point on the line returns false.

@Test
public void testLineContainsPoint() {
  LineSegment2D line = new LineSegment2D(-123707.89774439273, 157924.65808795238, -125829.21808795238, 155803.33774439275);
  Point2D point2d = new Point2D(-125034.27520951361, 157129.7152095136);
  Point2D projectedPoint = line.projectedPoint(point2d);
  assertEquals("Point need to be the same", new Point2D(-124768.55791617256, 156863.99791617255),  projectedPoint);
  assertTrue("Point is on line", line.containsProjection(point2d));
  assertTrue("Projected point has to be located on the line", line.contains(projectedPoint));
}

Polyline2D calculate distance doesn't work properly

When I calculating the distance using Polyline2D.distance().

ArrayList<Point2D> listPoint= new ArrayList<>();
listPoint.add(new Point2D(201093.16610711772, 1777477.3696508463)); // UTM Easting and Northing converted from lat,lng
listPoint.add(new Point2D(202667.84818503872, 1777673.8963489647));

Polyline2D polyline = Polyline2D.create(listPoint);
Point2D currentPoint = new Point2D(201926.0433899812, 1777926.9596233366);

double distance = polyline.distance(currentPoint);

Result is not correct.
But when I divided each coordinate by 1000, the result seem correct.
Is there any issue or I just missing somethings?

Function contains in class math.geom2d.polygon.SimplePolygon2D.

Hello,
I would appreciate your help understanding the contains function in simplePolygon2D.
The return statement check if the area is larger than zero (according to your explanation checking if the polygon is clockwise or counter-clockwise) and then re-check with the winding number of the polygon.
return area > 0.0D?winding == 1:winding==0;

1. If the winding number of a simple polygon is zero does it mean the point don’t contained in the polygon?
2. I get unexpected result with this input :

• Polygon:
  • (34.85738, 32.283905)
  • (34.85825, 32.294194999999995)
  • (34.88468, 32.29320499999999)
  • (34.88303, 32.283125)
  • (34.85738, 32.283905)
• Point :
  • (34.870909999999995, 32.289199999999994)
• Area :
  • -2.6633249990482E-4
• Winding numer :
  • -1

Thank you very much.

Line2D intersection bug

For some reason the implementation of Line2D.intersection(Line2D) is using a LineSegment2D here: https://github.com/dlegland/javaGeom/blob/master/src/main/java/math/geom2d/line/Line2D.java#L345

Then when the AbstractLine2D.instersect method takes over, it correctly finds the intersection, but then it checks LineSegment2D.contains(), and the intersection, though correct, may not be included in that segment... I don't know if this class was deprecated or what.

StraightLine2D seems to work correctly.