[mkgmap-dev] patch to write polygons in decreasing order

Tue Nov 8 09:41:02 GMT 2016

Hi Gerd

Thinking about simple rectangle clipping, PolygonClipper.java and
ShapeSplitter.java, quite a lot of the cost must be converting the
points representation to Path2D and back (preserving coords) and
handling the multiple output shapes. Given the pseudocode for
Sutherland-Hodgman, I might have a stab at doing it directly.

I'll fix the comments/debug and try and explain better - sorry.

The Area.split change has the same behaviour as before if
resolutionShift = 0, and, without order-by-decreasing-area, this is
what is passed to it; making the whole system behaviour unchanged.
With order-by-decreasing-area, the caller passes an appropriate shift
to force the split to be on a line exactly represent-able at the
subDivision level/resolution, because this will be the clipping for
shape splitting into the subDivisions.

Ticker

PS: I'm still working on aspects from your response on 05Nov16 01:13

On Mon, 2016-11-07 at 23:48 -0700, Gerd Petermann wrote:
> Hi Ticker,
> 
> okay, I will try on my own later. Please review the patch:
> 1) log messages esp. those with log.warn. I think most are debug
> messages ? 
> This one looks wrong to me:  ""Area single pixel shifted so can't
> split at
> "....
> What does it mean?
> 2) Comments / javadoc : Please remove commented code and add javadoc
> without
> jokes like
> @return An area containing xsplit*ysplit areas (hopefully).
> Instead try to explain in what case the result will be null. 
> BTW: It seems that this change in the code no longer depends on the
> new
> option. 
> Is that intended?
> 
> Gerd
> 
> 
> 
> Ticker Berkin wrote
> > Hi Gerd
> > 
> > I've been looking at ShapeSplitter and clipping to a rectangle
> > algorithms generally. I don't feel I know enough about how to use
> > the
> > java.awt.geom package to implement this effectively, and so I'd
> > rather
> > keep to using Java2DConverter and .intersect(), even though it is
> > most
> > likely much less efficient.
> > 
> > Ticker
> > 
> > On Sat, 2016-11-05 at 23:33 -0700, Gerd Petermann wrote:
> > > Hi Ticker,
> > > 
> > > Gerd Petermann wrote
> > > > Alternative would be to implement a clipper which doesn't need
> > > > area.intersect(). I've once coded the "Sutherland-Hodgman
> > > > algorithm" but
> > > > ways or concave shapes producing spikes, but I still think this
> > > > would be a
> > > > great improvement. See attached (out-aged) patch and the wiki
> > > > https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algori
> > > > thm
> > > > for further details.
> > > 
> > > I just noticed that the algo is already used in
> > > ShapeSplitter.clipSinglePathWithSutherlandHodgman(),
> > > the comment says
> > > "Clip a single path with a given rectangle using the Sutherland
> > > -Hodgman
> > > algorithm. This is much faster compared to the area.intersect
> > > method,
> > > but
> > > may create dangling edges." 
> > > I think these danling edges are now removed in the
> > > RemoveObsoletePointsFilter, so maybe it is worth 
> > > trying. 
> > > 
> > > Gerd
> > > 
> > > 
> > > 
> > > 
> > > --
> > > View this message in context: 
> > > http://gis.19327.n8.nabble.com/patch-to
> > > -write-polygons-in-decreasing-order-tp5884038p5885439.html
> > > Sent from the Mkgmap Development mailing list archive at
> > > Nabble.com.
> > > _______________________________________________
> > > mkgmap-dev mailing list
> > > 
> 
> > mkgmap-dev at .org
> 
> > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> > _______________________________________________
> > mkgmap-dev mailing list
> 
> > mkgmap-dev at .org
> 
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> 
> 
> 
> 
> 
> --
> View this message in context: http://gis.19327.n8.nabble.com/patch-to
> -write-polygons-in-decreasing-order-tp5884038p5885541.html
> Sent from the Mkgmap Development mailing list archive at Nabble.com.
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev