本文介绍了我可以使用Postgres函数来查找固定大小的旋转矩形内的点吗?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧! 问题描述 29岁程序员,3月因学历无情被辞! 我使用的是Postgres 9.5,而我刚刚为某些扩展功能安装了PostGIS。我有一个带有(x,y)点的表格,我想找到适合最大点数的矩形。约束条件是矩形边长是固定的。到目前为止,我在计算没有旋转的框中有多少个点。我的观点以原点为中心,(0,0)。 SELECT Sum(CASE 当x> -5 和x 和y> -10 和y 其他0 结束)作为inside_points,计数(1)AS total_points FROM track_t; 这个查询给出了原点(0,0) 和lenghts x = 10 和 y = 20 。 从这里我创建一个帮手旋转的矩形角点(角度,x1,y1,x2,y2)的表格,然后交叉连接到我的数据,并计算每个角度的点数,而GROUP BY角度。然后,我可以选择哪个角度给予矩形内的最多点。 但是,这看起来有些过时,也许是非高性能。此外,计算旋转矩形内的点不是平凡计算。 是否有更高效和优雅的方式,可能使用Postgres 几何数据类型或PostGIS Box2D ,旋转一个带有固定边长的矩形,然后计算里面的点数?几何函数看起来不错,但它们似乎提供了最小边界框,而不是其他方式。 除了Postgresql之外,我还使用了一个Python框架,可以在SQL无法使用的情况下使用它。 更新:我尝试的一件事是使用几何类型,特别是BOX SELECT deg,Box(点(-5,-10),点(5 ,10))* Point(1,Radians(deg)) FROM Generate_series(0,360,90)AS deg 不幸的是,旋转功能 by a Point 不适用于Polygons 。解决方案最后,我通过生成矩形顶点,旋转这些顶点,然后比较矩形区域(常量)和包含测试点的4个三角形的面积。 / p> 这项技术基于简洁的回答:矩形由 A 左下(-x / 2,-y / 2) (+ x / 2,+ y / 2) 然后检查点(qx,qy)是否在宽度 x = 10 和高度 y = 20 ,它围绕原点(0,0)以范围0到180的角度旋转10度。 以下是代码。需要花费9分钟来检查750k点,所以有一定的改进空间。此外,一旦我将t升级到9.6时,它可以并行化(选择x为10 * 0.5,20 * 0.5为y,17.0为qx,-3.0为qy) 选择 z.angle - ABC区域 - ,abs(0.5 *(z.ax *(z.by-z.cy)+ z.bx *(z.cy-z.ay)+ z.cx *(z.ay-z.by))) - CDA区域 - ,abs(0.5 *(z.cx *(z.dy-z.ay)+ z.dx *(z.ay-z.cy)+ z.ax *(z.cy -z.dy))) - ABCD区域,abs(0.5 *(z.ax *(z.by-z.cy)+ z.bx *(z。 cy.z.ay)+ z.cx *(z.ay-z.by)))+ abs(0.5 *(z.cx *(z.dy-z.ay)+ z.dx *(z.ay -z.cy)+ z.ax *(z.cy-z.dy)))as abcd_area - ABQ area - ,abs(0.5 *(z.ax *(z.by-z.qx)+ z.bx *(z.qy-z.ay)+ z.qx *(z.ay-z.by))) - BCQ区域 - ,abs(0.5 *(z.bx *(z.cy-z.qx)+ z.cx *(z.qy-z.by)+ z.qx *(z.by -z.cy))) - CDQ区域 - ,abs(0.5 *(z.cx *(z.dy-z.qx)+ z.dx *( z.qy-z.cy)+ z.qx *(z.cy-z.dy))) - DAQ区域 - ,abs(0.5 *(z。 dx *(z.ay-z.qx)+ z.ax *(z.qy-z.dy)+ z.qx *(z.dy-z.ay))) - - 总面积t (ABQ + BCQ + CDQ + DAQ),abs(0.5 *(z.ax *(z.by-z.qx)+ z.bx *(z.qy-z.ay) + z.qx *(z.ay-z.by))) + abs(0.5 *(z.bx *(z.cy-z.qx)+ z.cx *(z.qy-z .by)+ z.qx *(z.by-z.cy))) + abs(0.5 *(z.cx *(z.dy-z.qx)+ z.dx * qy-z.cy)+ z.qx *(z.cy-z.dy))) + abs(0.5 *(z.dx *(z.ay-z.qx)+ z.ax * (z.qy-z.dy)+ z.qx *(z.dy-z.ay)))as point_area from ( SELECT a.id作为角度 - 左下角(A),( - tx)* cos(弧度(a.id)) - (--ty)* sin(弧度(a.id)) (a),( - tx)* sin(弧度(a.id))+(-ty)* cos(弧度(a.id))as ay - top left(B)$ (弧度(a.id))为bx $ b $,( - tx)* cos(弧度(a.id)) - (ty)* sin(弧度(a.id))。 (b)右(C),(tx)* cos(弧度(a.id)) - (())+(ty)* cos(弧度(a.id) (弧度(a.id))为cx ,(tx)* sin(弧度(a.id))+(ty)* cos(弧度(a.id))为cy --bottom right(D),(tx)* cos(弧度s(a.id)) - (--ty)* sin(radians(a.id))as dx ,(tx)* sin(radians(a.id))+(--ty)* cos弧度(a.id))为dy - 指向检查(Q),t.qx为qx ,t.qy为qy FROM generate_series(0,180,10)AS a(id),t )z ; 结果是 angle; abcd_area; point_area 0; 200; 340 10; 200; 360.6646055963 20; 200; 373.409049054212 30; 200; 377.846096908265 40; 200; 373.84093170467 50; 200; 361.515248361426 60; 200; 341.243556529821 70; 200; 313.641801308188 80; 200; 279.548648061772 90; 200 ; 240 * 100; 200; 200 * * 110; 200; 200 * * 120; 200; 200 * * 130; 200; 200 * * 140; 200; 200 * 150; 200; 237.846096908265 160; 200; 277.643408923024 170; 200; 312.04311584956 180; 200; 340 * ) I'm using Postgres 9.5 and I've just installed PostGIS for some extended functions. I have a table with (x,y) points and I want to find the rectangle that fits the maximum number of points. The constraint is that the rectangle side lenghts are fixed. So far I'm counting how many points are in the box without rotation. My points are centered around the origin, (0,0).SELECT Sum(CASE WHEN x > -5 AND x < 5 AND y > -10 AND y < 10 THEN 1 ELSE 0 END) AS inside_points, Count(1) AS total_pointsFROM track_t;This query gives me the count of points inside a rectangle with origin (0,0) and lenghts x = 10 and y = 20.From here I would create a helper table of rotated rectangle corner points (angle, x1, y1, x2, y2), then cross join to my data, and count over the points per angle, while GROUP BY angle. Then I can select which angle gives me the most points inside the rectangle.But this seems a little old fashioned, and perhaps non-performant. Additionally, counting points inside a rotated rectangle is not a trivial calculation.Are there more efficient and elegant ways, perhaps using Postgres Geometric Datatypes or PostGIS Box2D, to rotate a rectangle with fixed side lenghts, and then to count the number of points inside? The geometric functions look good, but they seem to provide minimum bounding boxes and not the other way around.In addition to Postgresql, I'm using a Python framework that could be used in case SQL can't make this work.Update: One thing I tried is to use Geometric Types, specifically BOX SELECT deg, Box(Point(-5, -10), Point(5, 10)) * Point(1, Radians(deg)) FROM Generate_series(0, 360, 90) AS degUnforunately, the Rotate function by a Point doesn't work for Polygons. 解决方案 I ended up by generating rectangle vertices, rotating those vertices, and then comparing the area of the rectangle (constant) with the area of the 4 triangles that are made by including the test point.This technique is based on the parsimonious answer:The rectangles are defined byA bottom left (-x/2,-y/2)B top left (-x/2,+y/2)C top right (+x/2,+y/2)D bottom right (+x/2,-y/2)This code then checks if point (qx,qy) is inside a rectangle of width x=10 and height y=20, which is rotated around the origin (0,0) by an angle with range of 0 to 180, by 10 degrees.Here's the code. It's taking 9 minutes to check 750k points, so there is definite room for improvement. Additionally, It can be parallelized once I upgrade to 9.6with t as (select 10*0.5 as x, 20*0.5 as y, 17.0 as qx, -3.0 as qy)select z.angle -- ABC area --,abs(0.5*(z.ax*(z.by-z.cy)+z.bx*(z.cy-z.ay)+z.cx*(z.ay-z.by))) -- CDA area --,abs(0.5*(z.cx*(z.dy-z.ay)+z.dx*(z.ay-z.cy)+z.ax*(z.cy-z.dy))) -- ABCD area ,abs(0.5*(z.ax*(z.by-z.cy)+z.bx*(z.cy-z.ay)+z.cx*(z.ay-z.by))) + abs(0.5*(z.cx*(z.dy-z.ay)+z.dx*(z.ay-z.cy)+z.ax*(z.cy-z.dy))) as abcd_area -- ABQ area --,abs(0.5*(z.ax*(z.by-z.qx)+z.bx*(z.qy-z.ay)+z.qx*(z.ay-z.by))) -- BCQ area --,abs(0.5*(z.bx*(z.cy-z.qx)+z.cx*(z.qy-z.by)+z.qx*(z.by-z.cy))) -- CDQ area --,abs(0.5*(z.cx*(z.dy-z.qx)+z.dx*(z.qy-z.cy)+z.qx*(z.cy-z.dy))) -- DAQ area --,abs(0.5*(z.dx*(z.ay-z.qx)+z.ax*(z.qy-z.dy)+z.qx*(z.dy-z.ay))) -- total area of triangles with question point (ABQ + BCQ + CDQ + DAQ) ,abs(0.5*(z.ax*(z.by-z.qx)+z.bx*(z.qy-z.ay)+z.qx*(z.ay-z.by))) + abs(0.5*(z.bx*(z.cy-z.qx)+z.cx*(z.qy-z.by)+z.qx*(z.by-z.cy))) + abs(0.5*(z.cx*(z.dy-z.qx)+z.dx*(z.qy-z.cy)+z.qx*(z.cy-z.dy))) + abs(0.5*(z.dx*(z.ay-z.qx)+z.ax*(z.qy-z.dy)+z.qx*(z.dy-z.ay))) as point_areafrom(SELECT a.id as angle -- bottom left (A) ,(-t.x) * cos(radians(a.id)) - (-t.y) * sin(radians(a.id)) as ax ,(-t.x) * sin(radians(a.id)) + (-t.y) * cos(radians(a.id)) as ay --top left (B) ,(-t.x) * cos(radians(a.id)) - (t.y) * sin(radians(a.id)) as bx ,(-t.x) * sin(radians(a.id)) + (t.y) * cos(radians(a.id)) as by --top right (C) ,(t.x) * cos(radians(a.id)) - (t.y) * sin(radians(a.id)) as cx ,(t.x) * sin(radians(a.id)) + (t.y) * cos(radians(a.id)) as cy --bottom right (D) ,(t.x) * cos(radians(a.id)) - (-t.y) * sin(radians(a.id)) as dx ,(t.x) * sin(radians(a.id)) + (-t.y) * cos(radians(a.id)) as dy -- point to check (Q) ,t.qx as qx ,t.qy as qyFROM generate_series(0,180,10) AS a(id), t) z;the results then areangle;abcd_area;point_area0;200;34010;200;360.664605596320;200;373.40904905421230;200;377.84609690826540;200;373.8409317046750;200;361.51524836142660;200;341.24355652982170;200;313.64180130818880;200;279.54864806177290;200;240*100;200;200**110;200;200**120;200;200**130;200;200**140;200;200*150;200;237.846096908265160;200;277.643408923024170;200;312.04311584956180;200;340Where the rotations of angles 100, 110, 120, 130 and 140 degrees then includes the test-point (indicated with *) 这篇关于我可以使用Postgres函数来查找固定大小的旋转矩形内的点吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持! 上岸,阿里云!
08-04 12:14
查看更多