HomeWildfire Games

Implement a ConvexPolygonPlacer that returns all points in the convex hull of…

Description

Implement a ConvexPolygonPlacer that returns all points in the convex hull of some given points.
Implements the Gift-Wrapping algorithm to compute the convex hull.

Replace the latter half of the pathplacer with this new placer, refs #892.
Improves the performance a bit, refs #5011.

Use the new placer on Kerala and Hyrcanian Shores to replace the workaround from rP20933, refs #4855
(the area is not supposed to be parallel to the meandering river).

Event Timeline

smiley added a subscriber: smiley.May 10 2019, 7:29 PM

Mind elaborating what the expected result should be for points on a straight line? (Not what the code does, what it should do?)
I am just interested in the reasoning.

Returns all points on the tilegrid within the convex hull of the given positions.
Returns a sorted subset of the given points that are the vertices of the convex polygon containing all given points.

According to the definition expressed in the title and code comments, it should return a convex hull of the given points, and the convex hull encompasses all given points, therefore it should return the tiles on the given line segment parallel to an axis (and not empty area in case it does that).

[{x:265, y:26}, {x:266, y:26}] for [{x:269, y:26}, {x:268, y:26}, {x:266, y:26}, {x:265, y:26}] is what the code does. Which vertices would constitute a convex hull. The term convex hull is being bent here. A Convex Hull implies a polygon. Co-linear points cannot form a polygon regardless of how they are connected.

Co-linear points cannot form a polygon regardless of how they are connected.

Depending on the definition of polygon.
It might also be described as a degenerate polygon https://en.wikipedia.org/wiki/Degeneracy_(mathematics)#Convex_polygon

A Convex Hull implies a polygon.

If finite amounts of points, and three of them are not colinear, then the convex hull is a polygon.
If infinite amount of points were given, it could also have a different shape.

https://en.wikipedia.org/wiki/Convex_hull defines the convex hull more generally as the "smallest convex set that contains X", so the convex hull doesn't have to be a polygon.
If a finite amount of colinear points are given, then the convex hull is the line segment and a non-polygon or degenerated polygon.

[{x:265, y:26}, {x:266, y:26}] for [{x:269, y:26}, {x:268, y:26}, {x:266, y:26}, {x:265, y:26}] is what the code does.

I think the gift wrapping algorithm was implemented based on this description: https://en.wikipedia.org/wiki/Gift_wrapping_algorithm#Algorithm

the description below assumes that the points are in general position, i.e., no three points are collinear.
The algorithm may be easily modified to deal with collinearity, including the choice whether it should report only extreme points (vertices of the convex hull) or all points that lie on the convex hull

(and where does that second L in collinear come from)

smiley added a comment.EditedMay 10 2019, 9:26 PM

I think the gift wrapping algorithm was implemented based on this description: https://en.wikipedia.org/wiki/Gift_wrapping_algorithm#Algorithm

Indeed it is. I found this while investigating a mapgen mismatch following an algorithm change, and found it interesting.
Btw, this does imply this is technically wrong since a placer called for points on a line should at least include all the points of the input. Someone raise a concern or something?
This does get called with such points quite often.

should at least include all the points of the input

And it must be convex, so the points between the given points may not be omitted either.

  • Returns all points on the tilegrid within the convex hull of the given positions.

A use case of raising concerns is to have a TODO list for someone (for example the committer, reviewer, or unrelated interested person).
I won't raise a concern since it's technically impossible for the one committing to do so.
At least the cited comment is lacking the exception for colinear points, so the legitimacy of raising a concern would be hard to contest.
A better handling for the degenerate case would be an improvement, but likely not applicable to many cases (though I'm not sure how you got to testing the degenerate case, so maybe there is some use case).

(I considered renaming ConvexPolygonPlacer to ConvexHullPlacer, but the former name might be more descriptive as towards the only use case of the placer, and it's not wrong if degenerate polygons are considered polygons, and since ConvexHull doesn't inform the reader explicitly that he will always receive a convex polygon if not passing colinear points, whereas ConvexPolygon placer informs of that in every definition of a placer, i.e. in all mapscripts uses as well.)

I only considered two things, the result is wrong, and this gets called with such points quite often. Since it got resolved with the rewrite, I either had to reintroduce the bug for mapgen hash matching or leave it alone.
I won’t raise a concern. I will leave it up to you to decide whether the current results are acceptable.

Is it private wip crap?

Is it private wip crap?

Irrelevant. I found a defect and I am just pointing it out. With arguments and opinion for why I think it needs to be fixed.
Does it make much of a difference anyway?

Is it private wip crap?

Is this conduct you condone?

If the people/person who cares about the thing can see it, I am content.
Making things public did not really helped much in the past, which probably played a part in that view.

So you condone the way the question is phrased?

I guess I focused on the wrong keyword there. (given your stance on both, I wasn't sure)
All that matters to me is the intention. Not the phrasing.

This does get called with such points quite often.

Except for the PathPlacer the passed values seem obviously non-degenerate polygons, I read the occurrences again:

elephantine.js
fortress.js
hyrcanian_shores.js
jebel_barkal.js
kerala.js
rmgen/painter/CityPainter.js
rmgen/placer/noncentered/ConvexPolygonPlacer.js
rmgen/placer/noncentered/EntitiesObstructionPlacer.js
rmgen/placer/noncentered/PathPlacer.js

The PathPlacer is complex.
I do recall extensively checking the before/after results for different parameters, mapsizes often for most if not all affected maps and all commits.
I don't recall if I ruled out or forgot to check for colinearity without looking more closely at the diff, and I don't want to speculate on it.

it got resolved with the rewrite

If that is a good one but you don't upload it because noone reviews it, then why don't you convince me to argue for your commit access if you are willing to do the hard work on your own?

I researched it, wrote it, tested it, benchmarked it and compared it with old code on my own. It was definetly not easy work.
To answer the question, past me would have come up with something better than "idk man, i am not sure if thats even something i want at this point". Honestly, from what I can tell, it sounds horrible.

To say something with actual meaning, you might have ignored a bunch of things thinking the performance impact is negligible. And to be fair, it would have been if the call count was a little lower. But do reconsider everything that seemed like micro optimization at the time. Making this thing faster reduced JB loading time by nearly half.