Changeset View
Standalone View
binaries/data/mods/public/maps/random/rmgen/placer/noncentered/ConvexPolygonPlacer.js
| Context not available. | |||||
| this.failFraction = failFraction; | this.failFraction = failFraction; | ||||
| }; | }; | ||||
| /** | |||||
| * Returns orientation magniture and sign. | |||||
| */ | |||||
| ConvexPolygonPlacer.prototype.orient = function(line_p1, line_p2, point) | |||||
| { | |||||
| // (line_p1 - point).cross(line_p2 - point) | |||||
| return line_p1.cross(line_p2) - point.cross(line_p2) - line_p1.cross(point); | |||||
| } | |||||
elexis: Missing semicolon, this is an assigment `x = y;`.
Would be better in Vector2D, possibly as a… | |||||
| /** | |||||
| * Source: https://fgiesen.wordpress.com/2013/02/10/optimizing-the-basic-rasterizer/ | |||||
| * License: CC-0 (https://creativecommons.org/share-your-work/public-domain/cc0/) | |||||
elexisUnsubmitted Not Done Inline ActionsThe imported code is CC-0 licensed. Afaik CC-0 grants anything, so it also grants release under GPL v2+. However if we say this function is CC0 licensed, then this function is not GPL v2+ licensed, because CC-0 also grants everything that GPL v2+ forbids (such as distribution of the application without the source). In particular if we add our own contributions to this function, they will be licensed under CC-0 instead of GPL v2+ according to that line. It seems more simple to state that this is a derived work licensed as GPL v2+ where the original work is licensed as CC-0. elexis: The imported code is CC-0 licensed. Afaik CC-0 grants anything, so it also grants release under… | |||||
| */ | |||||
| ConvexPolygonPlacer.prototype.place = function(constraint) | ConvexPolygonPlacer.prototype.place = function(constraint) | ||||
| { | { | ||||
| let points = []; | let points = []; | ||||
| Context not available. | |||||
| let count = 0; | let count = 0; | ||||
| let failed = 0; | let failed = 0; | ||||
| for (let point of getPointsInBoundingBox(getBoundingBox(this.polygonVertices))) | if (!this.polygonVertices.length) | ||||
| return undefined; | |||||
| // v0 will always have the x-left most position of all vertices | |||||
| const v0 = this.polygonVertices[0]; | |||||
| const minx = Math.max(v0.x, 0); | |||||
| // fills triangles all sharing the same v0 vertex | |||||
| for (let i = 1; i < this.polygonVertices.length - 1; i++) | |||||
elexisUnsubmitted Not Done Inline ActionsWe use ++i unless i++ is necessary http://trac.wildfiregames.com/wiki/Coding_Conventions elexis: We use `++i` unless `i++` is necessary http://trac.wildfiregames.com/wiki/Coding_Conventions | |||||
| { | { | ||||
| if (this.polygonVertices.some((vertex, i) => | // triangle filling procedure algorithm | ||||
| distanceOfPointFromLine(this.polygonVertices[i], this.polygonVertices[(i + 1) % this.polygonVertices.length], point) > 0)) | const v1 = this.polygonVertices[i]; | ||||
| continue; | const v2 = this.polygonVertices[i + 1]; | ||||
| ++count; | // bounding box | ||||
| const miny = Math.max(Math.min(v0.y, v1.y, v2.y), 0); | |||||
| const maxx = Math.min(Math.max(v1.x, v2.x), g_Map.size - 1); | |||||
| const maxy = Math.min(Math.max(v0.y, v1.y, v2.y), g_Map.size - 1); | |||||
| if (g_Map.inMapBounds(point) && constraint.allows(point)) | const A01 = v0.y - v1.y; | ||||
| points.push(point); | const B01 = v1.x - v0.x; | ||||
| else | const A12 = v1.y - v2.y; | ||||
| ++failed; | const B12 = v2.x - v1.x; | ||||
| const A20 = v2.y - v0.y; | |||||
| const B20 = v0.x - v2.x; | |||||
| const p = new Vector2D(minx, miny); | |||||
| let w0_row = this.orient(v2, p, v1); | |||||
| let w1_row = this.orient(v0, p, v2); | |||||
| let w2_row = this.orient(v1, p, v0); | |||||
| for (p.y = miny; p.y <= maxy; p.y++) | |||||
| { | |||||
| let w0 = w0_row; | |||||
| let w1 = w1_row; | |||||
| let w2 = w2_row; | |||||
| for (p.x = minx; p.x <= maxx; p.x++) | |||||
| { | |||||
| if ((w0 | w1 | w2) >= 0) | |||||
elexisUnsubmitted Not Done Inline ActionsBitwise-or? I didn't really examine it, but isn't it equivalent to w0 >= 0 || w1 >= 0 || w2 >= 0, or (w0 || w1 || w2) >= 0? it faster or slower than that (If so, by how much?) elexis: Bitwise-or? I didn't really examine it, but isn't it equivalent to `w0 >= 0 || w1 >= 0 || w2 >=… | |||||
lyvUnsubmitted Not Done Inline ActionsThat but with && I think. I suspect it would be pretty much the same or just slightly slower. Bit-wise operations in JS is pretty slow compared to c/c++. lyv: That but with `&&` I think. I suspect it would be pretty much the same or just slightly slower. | |||||
| { | |||||
| ++count; | |||||
| if (constraint.allows(p)) | |||||
| points.push(p.clone()); | |||||
| else | |||||
| ++failed; | |||||
| } | |||||
| w0 += A12 | |||||
| w1 += A20 | |||||
| w2 += A01 | |||||
| } | |||||
| w0_row += B12 | |||||
| w1_row += B20 | |||||
| w2_row += B01 | |||||
| } | |||||
| } | } | ||||
| return failed <= this.failFraction * count ? points : undefined; | return failed <= this.failFraction * count ? points : undefined; | ||||
| Context not available. | |||||
| }; | }; | ||||
| /** | /** | ||||
| * Applies the gift-wrapping algorithm. | * Filters inner points quickly that we can assure won't be part of the convex hull. | ||||
| * Returns a sorted subset of the given points that are the vertices of the convex polygon containing all given points. | * Algorithm: http://mindthenerd.blogspot.com/2012/05/fastest-convex-hull-algorithm-ever.html | ||||
| */ | */ | ||||
| ConvexPolygonPlacer.prototype.pruning = function(points) | |||||
| { | |||||
| if (points.length < 15) | |||||
| return points.slice(); | |||||
| let plist = []; | |||||
| let A = points[0]; | |||||
| let B = points[0]; | |||||
| let C = points[0]; | |||||
| let D = points[0]; | |||||
| points.forEach(function(p) | |||||
| { | |||||
| if (A.x - A.y <= p.x - p.y) A = p; | |||||
| if (B.x + B.y <= p.x + p.y) B = p; | |||||
| if (C.x - C.y >= p.x - p.y) C = p; | |||||
| if (D.x + D.y >= p.x + p.y) D = p; | |||||
| }) | |||||
elexisUnsubmitted Not Done Inline ActionsWhat is happening here? elexis: What is happening here? | |||||
FeXoRUnsubmitted Not Done Inline ActionsThis spans a quadrangle with: A rectangle (with an angle of Pi/4 between it's side and the axis) with these pints on it's sides will contain all given points. FeXoR: This spans a quadrangle with:
A the bottom right most point
B the top right most point
C the… | |||||
elexisUnsubmitted Not Done Inline ActionsHow is it written in vector algebra? The unequation A.x - A.y <= p.x - p.y is unintuitive, because subtracting the X coordinate from the Y coordinate makes no sense. After some transformations I suppose it will be more transparent (I won't solve it). elexis: How is it written in vector algebra? The unequation `A.x - A.y <= p.x - p.y` is unintuitive… | |||||
StanUnsubmitted Not Done Inline ActionsCould be replaced by an arrow function as well. Stan: Could be replaced by an arrow function as well. | |||||
lyvUnsubmitted Not Done Inline ActionsIt’s trying to find the bottom right corner I guess. i.e the point where x-y is the largest. Hence, the largest x with the smallest y. Same for the other inequalities. lyv: It’s trying to find the bottom right corner I guess. i.e the point where x-y is the largest. | |||||
FeXoRUnsubmitted Not Done Inline ActionsOh, replace Pi/4 by Pi/8 in my last comment ^^ A.x - A.y <= p.x - p.y can be read as : If (P.x|P.y) is more bottom right from the straight line between x- and y-axis than (A.x|A.y) One could rotate all position vectors by Pi/8 and check for the point with the maximum x value (right most) and set A to it. Still the next part is about intervals on x/y axis. FeXoR: Oh, replace Pi/4 by Pi/8 in my last comment ^^
```
A.x - A.y <= p.x - p.y
```
can be read as… | |||||
FeXoRUnsubmitted Not Done Inline ActionsOo, Pi/4 was correct ofc and Pi/8 isn't x) FeXoR: Oo, Pi/4 was correct ofc and Pi/8 isn't x) | |||||
| const x1 = Math.max(C.x, D.x); | |||||
| const x2 = Math.min(A.x, B.x); | |||||
| const y1 = Math.max(A.y, D.y); | |||||
| const y2 = Math.min(B.y, C.y); | |||||
| points.forEach(function(p) | |||||
| { | |||||
| if (!(p.x > x1 && p.x < x2 && p.y > y1 && p.y < y2)) | |||||
| plist.push(p) | |||||
| }) | |||||
| return plist; | |||||
| } | |||||
| /** | |||||
| * Source: https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain#JavaScript | |||||
| * License: CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0/) | |||||
| */ | |||||
| ConvexPolygonPlacer.prototype.getConvexHull = function(points) | ConvexPolygonPlacer.prototype.getConvexHull = function(points) | ||||
| { | { | ||||
| let uniquePoints = []; | let sortedPoints = points.length < 10 ? points : this.pruning(points); | ||||
| for (let point of points) | let lower = []; | ||||
| if (uniquePoints.every(p => p.x != point.x || p.y != point.y)) | let upper = []; | ||||
| uniquePoints.push(point); | |||||
| // Start with the leftmost point | sortedPoints.sort((a, b) => a.x == b.x ? a.y - b.y : a.x - b.x); | ||||
| let result = [uniquePoints.reduce((leftMost, point) => point.x < leftMost.x ? point : leftMost, uniquePoints[0])]; | |||||
| // Add the vector most left of the most recently added point until a cycle is reached | if (sortedPoints.length < 4) | ||||
| while (result.length < uniquePoints.length) | return sortedPoints; | ||||
| for (let i = 0; i < sortedPoints.length; i++) | |||||
StanUnsubmitted Not Done Inline Actions++i Stan: ++i | |||||
| { | { | ||||
| let nextLeftmostPoint; | while (lower.length >= 2 && this.orient(lower[lower.length - 2], lower[lower.length - 1], sortedPoints[i]) <= 0) | ||||
| { | |||||
| lower.pop(); | |||||
| } | |||||
| lower.push(sortedPoints[i]); | |||||
| } | |||||
| // Of all points, find the one that is leftmost | for (let i = sortedPoints.length - 1; i >= 0; i--) | ||||
StanUnsubmitted Not Done Inline Actions--i Stan: --i | |||||
| for (let point of uniquePoints) | { | ||||
| while (upper.length >= 2 && this.orient(upper[upper.length - 2], upper[upper.length - 1], sortedPoints[i]) <= 0) | |||||
| { | { | ||||
| if (point == result[result.length - 1]) | upper.pop(); | ||||
| continue; | |||||
| if (!nextLeftmostPoint || distanceOfPointFromLine(nextLeftmostPoint, result[result.length - 1], point) <= 0) | |||||
| nextLeftmostPoint = point; | |||||
| } | } | ||||
| upper.push(sortedPoints[i]); | |||||
| } | |||||
| // If it was a known one, then the remaining points are inside this hull | upper.pop(); | ||||
| if (result.indexOf(nextLeftmostPoint) != -1) | lower.pop(); | ||||
| break; | |||||
| result.push(nextLeftmostPoint); | return lower.concat(upper); | ||||
| } | }; | ||||
| No newline at end of file | |||||
| return result; | |||||
| }; | |||||
| Context not available. | |||||
Missing semicolon, this is an assigment x = y;.
Would be better in Vector2D, possibly as a "static" function?
Is this equation paresent in other places of the code too and could be reused there? (we can easily search for cross products, as we use Vector2D everywhere...)