detecting arc and circle shapes in vector array
in
Programming Questions
•
7 months ago
have an array of 2d vertices and I want to detect if there are any arch or circle shapes in a array. Sometimes the values are not that precise and I need a small range. This is how far I came:
- //POLYGON((187559.337 428176.811,187527.509 428183.553,187523.497 428165.367,187551.576 428159.43,187556.304 428166.129,187557.089 428165.963,187559.337 428176.811))
- String building = "-0.014847994,-13.268441,0.0, -0.017455578,-4.8451867,0.0, 0.0,0.0,0.0, -9.536743E-7,14.13996,0.0, -12.110065,14.070896,0.0, -12.099585,10.644216,0.0, -12.230479,10.648428,0.0, -12.324993,10.638414,0.0, -12.44753,10.6125145,0.0, -12.563799,10.564032,0.0, -12.6779785,10.508021,0.0, -12.757869,10.445311,0.0, -12.831491,10.360016,0.0, -12.905113,10.274723,0.0, -12.972468,10.166845,0.0, -13.037734,10.051438,0.0, -13.040686,9.945219,0.0, -13.073751,9.830641,0.0, -13.072525,9.709364,0.0, -13.041186,9.596445,0.0, -13.009849,9.483524,0.0, -12.978511,9.370605,0.0, -12.919151,9.27357,0.0, -12.829678,9.184893,0.0, -12.772408,9.095386,0.0, -12.6570015,9.030121,0.0, -12.573796,8.964026,0.0, -12.466747,8.928872,0.0, -12.329586,8.902075,0.0, -12.228804,8.889506,0.0, -12.1,8.89282,0.0, -12.107458,5.64764,0.0, -12.20615,5.6526823,0.0, -12.332867,5.6418395,0.0, -12.455402,5.61594,0.0, -12.571672,5.567457,0.0, -12.655741,5.519803,0.0, -12.765741,5.448736,0.0, -12.841454,5.37097,0.0, -12.912987,5.2781477,0.0, -12.980341,5.17027,0.0, -13.017584,5.070749,0.0, -13.050648,4.956172,0.0, -13.051512,4.842423,0.0, -13.052376,4.728675,0.0, -13.051149,4.607398,0.0, -13.019812,4.494478,0.0, -12.988473,4.3815594,0.0, -12.929113,4.284524,0.0, -12.83964,4.1958456,0.0, -12.752257,4.1146955,0.0, -12.666964,4.0410733,0.0, -12.555736,3.9908638,0.0, -12.446597,3.948182,0.0, -12.341637,3.9205565,0.0, -12.210744,3.9163435,0.0, -12.112051,3.911302,0.0, -12.098757,0.0070438385,0.0, -12.089501,-3.2983603,0.0, -12.220395,-3.2941473,0.0, -12.34711,-3.3049905,0.0, -12.439535,-3.3225327,0.0, -12.557894,-3.3634877,0.0, -12.669984,-3.4270265,0.0, -12.749874,-3.4897366,0.0, -12.855698,-3.5758595,0.0, -12.929319,-3.6611536,0.0, -12.966563,-3.760675,0.0, -13.033917,-3.8685527,0.0, -13.066981,-3.98313,0.0, -13.067844,-4.0968785,0.0, -13.068708,-4.210627,0.0, -13.067483,-4.3319035,0.0, -13.036145,-4.4448233,0.0, -12.976784,-4.5418577,0.0, -12.949624,-4.639722,0.0, -12.862242,-4.720872,0.0, -12.807059,-4.8028507,0.0, -12.723854,-4.868945,0.0, -12.610538,-4.9266825,0.0, -12.5336,-4.970193,0.0, -12.426551,-5.0053463,0.0, -12.32368,-5.025444,0.0, -12.2228985,-5.038014,0.0, -12.098272,-5.019643,0.0, -12.099463,-8.287407,0.0, -12.230357,-8.283194,0.0, -12.326961,-8.285681,0.0, -12.449497,-8.311579,0.0, -12.567856,-8.352534,0.0, -12.679947,-8.416073,0.0, -12.759836,-8.478784,0.0, -12.86566,-8.564906,0.0, -12.937192,-8.657728,0.0, -12.976525,-8.749722,0.0, -13.041791,-8.865128,0.0, -13.074855,-8.979705,0.0, -13.075718,-9.093452,0.0, -13.0744915,-9.214729,0.0, -13.073266,-9.336006,0.0, -13.041928,-9.448925,0.0, -12.980478,-9.553489,0.0, -12.921119,-9.650523,0.0, -12.861757,-9.747559,0.0, -12.774375,-9.828709,0.0, -12.658969,-9.893974,0.0, -12.575763,-9.960069,0.0, -12.468715,-9.995222,0.0, -12.3315525,-10.022018,0.0, -12.230771,-10.034589,0.0, -12.104056,-10.023746,0.0, -12.102295,-13.185289,0.0, -0.014847994,-13.268441,0.0";
- String b2 = "0.0,23.383022,0.0, -2.9107447,23.34843,0.0, -2.910431,23.526754,0.0, -2.9237957,23.712631,0.0, -2.9591064,23.874931,0.0, -3.0080957,24.044785,0.0, -3.0639238,24.218414,0.0, -3.141698,24.368465,0.0, -3.2263107,24.522295,0.0, -3.3397102,24.656322,0.0, -3.44627,24.786572,0.0, -3.5665083,24.924377,0.0, -3.7018547,25.034826,0.0, -3.8372002,25.145277,0.0, -3.9944925,25.23215,0.0, -4.160055,25.287886,0.0, -4.3105087,25.37098,0.0, -4.4911785,25.399364,0.0, -4.6650095,25.423971,0.0, -4.8388405,25.448578,0.0, -5.0058327,25.469406,0.0, -17.687822,25.40509,0.0, -32.194794,25.34911,0.0, -32.188892,24.810364,0.0, -32.176155,24.267841,0.0, -32.149742,23.717762,0.0, -32.101376,23.191261,0.0, -32.032497,22.65343,0.0, -31.95678,22.111824,0.0, -31.874224,21.566437,0.0, -31.762882,21.040854,0.0, -31.6447,20.511494,0.0, -31.512842,19.974579,0.0, -31.359035,19.461243,0.0, -31.191555,18.940351,0.0, -31.002123,18.443039,0.0, -30.805857,17.941952,0.0, -30.595911,17.433306,0.0, -30.379124,16.920887,0.0, -30.140392,16.432045,0.0, -29.879713,15.966781,0.0, -29.612196,15.497741,0.0, -29.33784,15.024922,0.0, -29.041534,14.575684,0.0, -28.738394,14.122666,0.0, -28.428413,13.665873,0.0, -28.081379,13.260013,0.0, -27.74261,12.823021,0.0, -27.388737,12.4133835,0.0, -27.012915,12.027325,0.0, -26.652203,11.613911,0.0, -26.254433,11.2514305,0.0, -25.849825,10.885172,0.0, -25.445219,10.518914,0.0, -25.025503,10.180013,0.0, -24.59895,9.837334,0.0, -24.157288,9.522009,0.0, -23.700518,9.234039,0.0, -23.252016,8.914939,0.0, -22.780138,8.654325,0.0, -22.301422,8.389935,0.0, -21.829544,8.129321,0.0, -21.335718,7.892286,0.0, -20.848732,7.6590276,0.0, -20.346638,7.4531245,0.0, -19.844543,7.247221,0.0, -19.327341,7.068673,0.0, -18.816978,6.893903,0.0, -18.291506,6.7464867,0.0, -17.772873,6.6028485,0.0, -17.239134,6.4865656,0.0, -16.71223,6.3740587,0.0, -16.170221,6.2889075,0.0, -15.635051,6.207534,0.0, -15.09161,6.1572914,0.0, -14.54817,6.10705,0.0, -14.003299,6.0917177,0.0, -13.458429,6.0763845,0.0, -12.920398,6.0648293,0.0, -12.90176,4.983558,0.0, -12.9055605,4.37877,0.0, -12.9065,3.8437996,0.0, -12.856937,0.10370207,0.0, -12.639213,0.12625217,0.0, -6.3840165,0.027300596,0.0, -0.12738986,-0.036741648,0.0, 0.0,0.0,0.0, 0.0,23.383022,0.0";
- String b3 = "187559.337 428176.811,187527.509 428183.553,187523.497 428165.367,187551.576 428159.43,187556.304 428166.129,187557.089 428165.963,187559.337 428176.811";
- boolean sw = true;
- PVector[] c = new PVector[0];
- void setup() {
- size(1800, 1000);
- String[] b = split(building, ", ");
- for (int x=0; x< b.length-1; x++) {
- String[] s = split(b[x], ",");
- String[] s2 = split(b[x+1], ",");
- // println(s);
- float scaleFactor = 3;
- PVector vec = new PVector(float(s[0])*scaleFactor, float(s[1])*scaleFactor);
- PVector vec2 = new PVector(float(s2[0])*scaleFactor, float(s2[1])*scaleFactor);
- float at = PVector.angleBetween(vec, vec2);
- //if (vec.dist(vec2) < .150*scaleFactor){
- c = (PVector[])append(c, vec);
- // }
- }
- }
- void draw() {
- background(255);
- translate(width/2,0);
- strokeWeight(.5);
- scale(8);
- String[] l = new String[0];
- strokeWeight(.2);
- noFill();
- stroke(0);
- getcircles circle = new getcircles(c);
- circle.getCircleFromPoints();
- circle.sortList();
- circle.drawCircles();
- strokeWeight(.2);
- noFill();
- stroke(255, 0, 0);
- circle.showConcentration();
- stroke(0, 125);
- strokeWeight(.2);
- if (sw ) beginShape();
- for (int x=0;x<c.length;x++) {
- point( c[x].x, c[x].y);
- }
- if (sw)endShape();
- stop();
- }
- class getcircles {
- circleData[] vectors;
- ArrayList<circleData> circlesFromBuildings = new ArrayList<circleData>();
- PVector[] cArray;
- PVector maxSize;
- PVector minSize;
- //___-----------------------------------------------------------
- getcircles(PVector[] _c) {
- cArray = _c;
- maxSize = getMax(c);
- minSize = getMin(c);
- println("max size");
- println(maxSize);
- println(minSize);
- println("-----");
- }
- //___-----------------------------------------------------------
- void getCircleFromPoints() {
- vectors = new circleData[c.length * (c.length-3)];
- int index = 0;
- for (int y=0; y< cArray.length;y++)
- for (int x=0; x< cArray.length-3;x++)
- {
- // PVector[] p = new PVector[3];
- PVector[] p2 = {
- cArray[x], cArray[y], cArray[x+2]
- };
- circleData cD = circleFromPoints(p2);
- float at = PVector.angleBetween(cArray[x], cArray[y]);
- // println(at);
- if ( ((cD.point.x < maxSize.x) && (cD.point.x > minSize.x)) && ((cD.point.y < maxSize.y) && (cD.point.y > minSize.y)) && ((at < 2) &&(at > -2))) {
- // vectors[index] = cD;
- circlesFromBuildings.add(cD);
- }
- index++;
- }
- closePoints();
- }
- int size() {
- return circlesFromBuildings.size();
- }
- //___-----------------------------------------------------------
- void closePoints() {
- int[] circlePointCount = new int[size()];
- for (int y=0; y< size();y++)
- for (int x=0; x< size();x++) {
- if ((round(circlesFromBuildings.get(x).point.x)== round(circlesFromBuildings.get(y).point.x)) && (round(circlesFromBuildings.get(x).point.y)== round(circlesFromBuildings.get(y).point.y))) {
- // circlesFromBuildings.get(x).countPoints++;
- circlesFromBuildings.get(x).countPoints++;
- }
- }
- sortList() ;
- }
- //___-----------------------------------------------------------
- void sortList()
- {
- Collections.sort(circlesFromBuildings, new Comparator<circleData>() {
- public int compare(circleData lhs, circleData rhs) {
- return (lhs.countPoints.compareTo(rhs.countPoints));
- }
- }
- );
- }
- //___-----------------------------------------------------------
- ArrayList<circleData> ellipses = new ArrayList<circleData>();
- void showConcentration() {
- for (int x=0; x<circlesFromBuildings.size()-1;x++) {
- if ( circlesFromBuildings.get(x).countPoints > cArray.length*2.2) {
- for (int y=0; y<cArray.length-1; y++) {
- float d = PVector.dist(circlesFromBuildings.get(x).point, cArray[y]);
- float d2 = PVector.dist(circlesFromBuildings.get(x+1).point, cArray[y+1]);
- if ( d == circlesFromBuildings.get(x).r ) {
- stroke(255, 0, 0);
- // point(circlesFromBuildings.get(x).point.x, circlesFromBuildings.get(x).point.y);
- ellipse(circlesFromBuildings.get(x).point.x, circlesFromBuildings.get(x).point.y, circlesFromBuildings.get(x).r*2, circlesFromBuildings.get(x).r*2);
- ellipses.add(circlesFromBuildings.get(x));
- // als dist binnen elllipse valt, dan is het een cirkel
- // detecteer een begin en een eind binnen ellipse
- line(circlesFromBuildings.get(x).point.x, circlesFromBuildings.get(x).point.y, cArray[y].x, cArray[y].y);
- // }
- }
- //}
- }
- }
- }
- // compareEllipses();
- }
- void compareEllipses(){
- stroke(255,0,0);
- strokeWeight(.2);
- for(int x=0; x<ellipses.size(); x++){
- PVector[] ePoints = ellipsePoints(ellipses.get(x).point,ellipses.get(x).r, 100);
- point(ellipses.get(x).point.x,ellipses.get(x).point.y);
- for(int z=0; z<ePoints.length; z++)
- for(int y=0; y<cArray.length; y++){
- point(ePoints[z].x,ePoints[z].y);
- if ( cArray[y] == ePoints[z]){
- point(cArray[y].x,cArray[y].y);
- }
- }
- }
- }
- PVector[] ellipsePoints(PVector center, float r, int num_segments) {
- float theta = 2 * 3.1415926 / float(num_segments);
- float c = cos(theta);//precalculate the sine and cosine
- float s = sin(theta);
- float t;
- float x = r;//we start at angle = 0
- float y = 0;
- PVector[] temp = new PVector[num_segments];
- for (int ii = 0; ii < num_segments; ii++)
- {
- PVector vec = new PVector(x + center.x, y + center.y);//output vertex
- temp[ii] = vec;
- //apply the rotation matrix
- t = x;
- x = c * x - s * y;
- y = s * t + c * y;
- }
- return temp;
- }
- //___-----------------------------------------------------------
- void drawCircles() {
- for (int x=0; x< circlesFromBuildings.size();x++) {
- point( circlesFromBuildings.get(x).point.x, circlesFromBuildings.get(x).point.y);
- }
- }
- //___-----------------------------------------------------------
- void getDistancesFromCircle(circleData d) {
- }
- //___-----------------------------------------------------------
- PVector centroid(PVector[] points) {
- PVector centroid = new PVector( 0, 0 );
- for (int i = 0; i < points.length; i++) {
- centroid.x += points[i].x;
- centroid.y += points[i].y;
- }
- int totalPoints = points.length;
- centroid.x = centroid.x / totalPoints;
- centroid.y = centroid.y / totalPoints;
- return centroid;
- }
- //___-----------------------------------------------------------
- circleData circleFromPoints( PVector[] p)
- {
- final double offset = Math.pow(p[1].x, 2) + Math.pow(p[1].y, 2);
- final double bc = ( Math.pow(p[0].x, 2) + Math.pow(p[0].y, 2) - offset )/2.0;
- final double cd = (offset - Math.pow(p[2].x, 2) - Math.pow(p[2].y, 2))/2.0;
- final double det = (p[0].x - p[1].x) * (p[1].y - p[2].y) - (p[1].x - p[2].x)* (p[0].y - p[1].y);
- final double idet = 1/det;
- final double centerx = (bc * (p[1].y - p[2].y) - cd * (p[0].y - p[1].y)) * idet;
- final double centery = (cd * (p[0].x - p[1].x) - bc * (p[1].x - p[2].x)) * idet;
- final double radius = Math.sqrt( Math.pow(p[1].x - centerx, 2) + Math.pow(p[1].y-centery, 2));
- circleData d = new circleData();
- d.point.x = (float)centerx;
- d.point.y = (float)centery;
- d.usedPoints = p;
- d.r = (float)radius;
- return d;
- ///return new Circle(new PVector(centerx,centery),radius);
- }
- PVector getMax(PVector[] dataArray)
- {
- PVector max = dataArray[0];
- for (int i = 0; i < dataArray.length; i++) {
- if (dataArray[i].x > max.x)
- max.x = dataArray[i].x;
- if (dataArray[i].y > max.y)
- max.y = dataArray[i].y;
- }
- // println(max);
- return max;
- }
- PVector getMin(PVector[] dataArray)
- {
- PVector min = new PVector( 888, 888);
- for (int i = 0; i < dataArray.length; i++) {
- if (dataArray[i].x < min.x)
- min.x = dataArray[i].x;
- if (dataArray[i].y < min.y)
- min.y = dataArray[i].y;
- }
- // println(min);
- return min;
- }
- }
- class circleData {
- PVector point;
- PVector[] usedPoints;
- float r;
- Integer countPoints;
- circleData() {
- point = new PVector();
- usedPoints = new PVector[3];
- countPoints = 0;
- }
- }
My code is a bit messy and doesn't work that well. After the detection I want to recreate the verticle without the points.
Could somebody help me a bit with this code to get it working better? And to get out a biezier vertex?
1