Rounding issues under Python

[GoogleCodeExporter]

What steps will reproduce the problem?

>>> from p2t import CDT, Point
>>> contour = 
[(453521.56421354739,5767884.7591257878),(453513.83972662123,5767843.0712512629)
,(453446.3724479521,5767807.8537950916),(453369.60432990646,5767717.0111599602),
(453370.19001821574,5767706.9852263089),(453324.26838960598,5767684.8794395626),
(453316.15682864317,5767682.2142445147),(453310.33114277112,5767686.4557612957),
(453308.08654497867,5767680.5475153625),(453301.09728229989,5767680.8364430135)]
>>> pts = [Point(x, y) for x, y in contour]
>>> cdt = CDT(pts)
>>> triangles = cdt.triangulate()
>>> for t in triangles:
...     print t.a.x, t.a.y, t.b.x, t.b.y, t.c.x, t.c.y
...
453521.5625 5767885.0 453301.09375 5767681.0 453446.375 5767808.0
453301.09375 5767681.0 453310.34375 5767686.5 453446.375 5767808.0
453446.375 5767808.0 453310.34375 5767686.5 453369.59375 5767717.0
453324.28125 5767685.0 453369.59375 5767717.0 453310.34375 5767686.5
...

What is the expected output? What do you see instead?

I'd expect to find the input coordinates as triangulation nodes exactly as 
defined. Instead they appear rounded (or even truncated) to a decimal place 
ending with either 5 or 0.

What version of the product are you using? On what operating system?

poly2tri 0.3.3 from pypi.org on Windows
p2t compiled under mingw using cython 0.15

Please provide any additional information below.

I'm working with real world coordinates featuring a lot of (possible 
meaningless albeit existing) decimal places. When triangulating with poly2tri, 
I'm having a problem with the output as the input coordinates are rounded at 
some certain time during the process. Result is that my triangulation does not 
overlap with the original data - not by a lot, but its annoying nonetheless. I 
somehow suspect this to be a compilation issue but haven't been able to 
pinpoint the problem. Has something like that occurred to you as well?

Original issue reported on code.google.com by reinhold...@googlemail.com on 5 Oct 2011 at 9:49

Attachments:

• orig_vs_triangulation.png

[GoogleCodeExporter]

I'm the maintainer of the java version so can't help you with anything python 
related.

I just want you to test one thing, that is to recenter your data set around 0 
and normalize it to the range 0-1.

So find the maxX,minX,maxY,minY values of your pointset and do something like 
this:
newx = (x - 0.5*(minX+maxX))/(maxX-minX)
newy = (y - 0.5*(minY+maxY))/(maxY-minY)

triangulate and then do the inverse transform to get your original coordinates 
back. Does this give you better precision?

Original comment by thahlen@gmail.com on 5 Oct 2011 at 6:49

[GoogleCodeExporter]

Hej,
thanks for the comment. Here's what I did following your suggestion:

>>> from operator import itemgetter
## calculating maxima and minima
>>> minx = min(map(itemgetter(0), contour))
>>> maxx = max(map(itemgetter(0), contour))
>>> miny = min(map(itemgetter(1), contour))
>>> maxy = max(map(itemgetter(1), contour))
>>> minx, maxx
(453301.09728229989, 453521.56421354739)
>>> miny, maxy
(5767680.5475153625, 5767884.7591257878)
## transforming x and y coordinates
>>> trf_x = [((x - 0.5*(minx + maxx))/(maxx - minx)) for x in 
map(itemgetter(0), contour)]
>>> trf_y = [((y - 0.5*(miny + maxy))/(maxy - miny)) for y in 
map(itemgetter(1), contour)]
>>> trf_contour = zip(trf_x, trf_y)
>>> trf_contour
[(0.5, 0.5), (0.46496305871155169, 0.29585943013700072), (0.15894311146884177, 
0.12340373039519884), (-0.18926384007374694, -0.32144186355641047), 
(-0.18660725885331514, -0.37053766976632635), (-0.39489985107982267, 
-0.47878708173821799), (-0.43169249348158473, -0.49183822531573157), 
(-0.45811680046990128, -0.47106802144629084), (-0.46829790917291558, -0.5), 
(-0.5, -0.49858515561182454)]
## triangulating
>>> trf_pts = [Point(x, y) for x, y in trf_contour]
>>> trf_cdt = CDT(trf_pts)
>>> trf_triangles = trf_cdt.triangulate()
>>> for t in trf_triangles:
...     print t.a.x, t.a.y, t.b.x, t.b.y, t.c.x, t.c.y
0.5 0.5 -0.5 -0.498585164547 0.158943116665 0.123403728008
-0.5 -0.498585164547 -0.458116799593 -0.471068024635 0.158943116665 
0.123403728008
0.158943116665 0.123403728008 -0.458116799593 -0.471068024635 -0.189263835549 
-0.321441859007
-0.394899845123 -0.478787094355 -0.189263835549 -0.321441859007 -0.458116799593 
-0.471068024635
-0.458116799593 -0.471068024635 -0.431692481041 -0.491838216782 -0.394899845123 
-0.478787094355
...
## the above looks good so far since these are exactly the input coordinates
## now performing the inverse transformation
>>>for t in trf_triangles:
...     for corner in [t.a, t.b, t.c]:
...             corner.x = corner.x * (maxx - minx) + 0.5*(minx + maxx)
...             corner.y = corner.y * (maxy - miny) + 0.5*(miny + maxy)
## now printing inverse transformed coordinates
>>> for t in trf_triangles:
...     for corner in [t.a, t.b, t.c]:
...             print corner.x, corner.y
...     print
...
453521.5625 5767885.0
453301.09375 5767681.0
453446.375 5767808.0

453301.09375 5767681.0
453310.34375 5767686.5
453446.375 5767808.0
...
## unfortunately no better precision
## there's obviously a problem with these high values in my p2t implementation..

Original comment by reinhold...@googlemail.com on 6 Oct 2011 at 12:33

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

If you compare the input and output decimal values they are only equal upto 7 
decimals. Seems like somewhere they are being converted from double to float 
precision?

The values should not be modified inside the traingulation lib so the problem 
should be when setting or getting the value from the point class. Wierd.

Original comment by thahlen@gmail.com on 6 Oct 2011 at 7:41

[GoogleCodeExporter]

If your using Decimal then maybe there is some issue when converting Decimal to 
cmath double?

Original comment by thahlen@gmail.com on 6 Oct 2011 at 7:45

[GoogleCodeExporter]

Did you find any solution to this problem?

Original comment by thahlen@gmail.com on 12 Oct 2011 at 7:35

[GoogleCodeExporter]

Closing this until someone else can confirm this is a poly2tri lib issue.

Original comment by thahlen@gmail.com on 26 Oct 2011 at 3:45

• Changed state: WontFix

[GoogleCodeExporter]

Hej,
your suggestions were very welcome. You were right about the problem already 
occurring when constructing the p2t.Point object:
>>> pt = Point(453521.56421354739, 5767884.7591257878)
>>> pt.x
453521.5625
>>> pt.y
5767885.0
Is there a reference implementation of the Python package available? It 
shouldn't be hard to build one - considering I was able to this as well, albeit 
obviously with errors.
Or would it be possible to deduct the cause of the problem from the build log? 
In this case I'd post it here?

Thanks again and sorry for not replying sooner.

Original comment by reinhold...@googlemail.com on 26 Oct 2011 at 8:58

[GoogleCodeExporter]

Hej again,
after getting back to it after quite some time, I think I have found the reason 
for this issue.
As already suspected in comment #4, the problem is created by an improper 
double to float conversion in src/p2t.cpp.
After changing every occurrence of *float* into *double* and a recompilation, I 
am now able to create instances of p2t.Point with coordinates of double 
precision, e.g.:

>>> x = 12345678.87654321
>>> y = 87654321.12345678
>>> p = p2t.Point(x, y)
>>> p.x
12345678.87654321
>>> p.y
87654321.12345678

As src/p2t.cpp originates from Cython's conversion from Python to C++, I'm 
suspecting this is a Cython issue. However, since I have experienced it in 
connection with poly2tri, I'm hoping this post will help others with similar 
problems.
Regards,
Markus

NB: For solving another problem occurring when trying to compile the poly2tri 
Python extension, you may refer to issue 47.

Original comment by reinhold...@googlemail.com on 13 Mar 2012 at 11:01