boost::geometry::intersection algorithm creates spike

[vschoech]

My tc::geo::polygon<int> type is actually a multi-polygon, using a polygon type that is based on int, oriented counter-clockwise and open (not closed). I am using boost 1.79.0.

Please consider the following example as it occurred in our code:

tc::geo::polygon<int> polygonA;
boost::geometry::read_wkt("MULTIPOLYGON(((1169 177,2004 177,2004 1977,1262 1977,1169 177)))", polygonA);
tc::geo::polygon<int> polygonB;
boost::geometry::read_wkt("MULTIPOLYGON(((1179 371,1175 287,1179 287,1179 371)))", polygonB);
tc::geo::polygon<int> polygonC;
boost::geometry::intersection(polygonA, polygonB, polygonC);
tc::geo::polygon<int> polygonD = polygonC;
boost::geometry::remove_spikes(polygonD);
// polygonC=polygon(MULTIPOLYGON(((1179 370,1179 365,1175 287,1179 287,1179 370))))
// polygonD=polygon(MULTIPOLYGON(((1179 365,1175 287,1179 287,1179 365))))

It was my expectation that when the input does not contain spikes, neither does the output from boost::geometry::intersection. Please clarify whether my assumption is wrong or there is a bug in boost::geometry::intersection.

See also:

• remove_spikes does not remove spike #603
• boost::geometry::intersection algorithm creates spike #1022

[barendgehrels]

Hi Volker!

Thanks for the report and the clear reproduction scenario. I looked in the issue. I can reproduce it. It seems that the cause is that open is not taken into account correctly, somewhere in the intersection procedure.

My extra code:

    std::cout << std::boolalpha;
    std::cout << "a: " << boost::geometry::is_valid(polygonA) << " " << boost::geometry::area(polygonA) << " " << boost::geometry::wkt(polygonA) << std::endl;
    std::cout << "b: " << boost::geometry::is_valid(polygonB) << " " << boost::geometry::area(polygonB) << " " << boost::geometry::wkt(polygonB) << std::endl;
    std::cout << "c: " << boost::geometry::is_valid(polygonC) << " " << boost::geometry::area(polygonC) << " " << boost::geometry::wkt(polygonC) << std::endl;
    std::cout << "d: " << boost::geometry::is_valid(polygonD) << " " << boost::geometry::area(polygonD) << " " << boost::geometry::wkt(polygonD) << std::endl;

Delivering (coordinates you also listed):

a: true 1.4193e+06 MULTIPOLYGON(((1169 177,2004 177,2004 1977,1262 1977,1169 177)))
b: true 168 MULTIPOLYGON(((1179 371,1175 287,1179 287,1179 371)))
c: false 156 MULTIPOLYGON(((1179 370,1179 365,1175 287,1179 287,1179 370)))
d: true 156 MULTIPOLYGON(((1179 365,1175 287,1179 287,1179 365)))

If I make it closed, it works as expected:

a: true 1.4193e+06 MULTIPOLYGON(((1169 177,2004 177,2004 1977,1262 1977,1169 177)))
b: true 168 MULTIPOLYGON(((1179 371,1175 287,1179 287,1179 371)))
c: true 156 MULTIPOLYGON(((1179 287,1179 365,1175 287,1179 287)))
d: true 156 MULTIPOLYGON(((1179 287,1179 365,1175 287,1179 287)))

I don't think it is related to the issues you mention (though they are also about spikes, thanks for the links and the heads up there).

To be complete, a figure (zoomed in), where

• green = A
• blue = B
• green/red dotted = C
  

And zoomed in more, where extra

• orange = D

and the spike in polygonC is indeed visible.

Side note: the output is here not optimal for integer. Using double, the intersection will follow polygonB. But cause of intersection segment logic and rounding to integer coordinates, these points get the same value and a spike is caused.

Picture for double:

and debug info:

a: true 1.4193e+06 MULTIPOLYGON(((1169 177,2004 177,2004 1977,1262 1977,1169 177)))
b: true 168 MULTIPOLYGON(((1179 371,1175 287,1179 287,1179 371)))
c: true 167.938 MULTIPOLYGON(((1179 370.548,1178.73 365.235,1175 287,1179 287,1179 370.548)))
d: true 167.938 MULTIPOLYGON(((1179 370.548,1178.73 365.235,1175 287,1179 287,1179 370.548)))

where the area matches better as well. But this is not really related to removing the spike.

[vschoech]

Thank you for the quick and thorough reply! I've seen it in 1.79, but I assume you reproduced in 1.83?

[barendgehrels]

Yes, it's reproduced in 1.83

[barendgehrels]

I've a concept fix, will create a PR later today (if the concept is fine)

[vschoech]

@barendgehrels Thank you! :)