Asked  7 Months ago    Answers:  5   Viewed   62 times

I am trying to write a C++ program that takes the following inputs from the user to construct rectangles (between 2 and 5): height, width, x-pos, y-pos. All of these rectangles will exist parallel to the x and the y axis, that is all of their edges will have slopes of 0 or infinity.

I've tried to implement what is mentioned in this question but I am not having very much luck.

My current implementation does the following:

// Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
// point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
// Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2

// rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
// point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2]; 
pnt_y = arrRect1[3];
// test point, a from rect 2
int tst_x, tst_y;
tst_x = arrRect2[0];
tst_y = arrRect2[1];

int value;
value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y));
cout << "Value: " << value;  

However I'm not quite sure if (a) I've implemented the algorithm I linked to correctly, or if I did exactly how to interpret this?

Any suggestions?

 Answers

10
if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
     RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top ) 

or, using Cartesian coordinates

(With X1 being left coord, X2 being right coord, increasing from left to right and Y1 being Top coord, and Y2 being Bottom coord, increasing from bottom to top -- if this is not how your coordinate system [e.g. most computers have the Y direction reversed], swap the comparisons below) ...

if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
    RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1) 

Say you have Rect A, and Rect B. Proof is by contradiction. Any one of four conditions guarantees that no overlap can exist:

  • Cond1. If A's left edge is to the right of the B's right edge, - then A is Totally to right Of B
  • Cond2. If A's right edge is to the left of the B's left edge, - then A is Totally to left Of B
  • Cond3. If A's top edge is below B's bottom edge, - then A is Totally below B
  • Cond4. If A's bottom edge is above B's top edge, - then A is Totally above B

So condition for Non-Overlap is

NON-Overlap => Cond1 Or Cond2 Or Cond3 Or Cond4

Therefore, a sufficient condition for Overlap is the opposite.

Overlap => NOT (Cond1 Or Cond2 Or Cond3 Or Cond4)

De Morgan's law says
Not (A or B or C or D) is the same as Not A And Not B And Not C And Not D
so using De Morgan, we have

Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4

This is equivalent to:

  • A's Left Edge to left of B's right edge, [RectA.Left < RectB.Right], and
  • A's right edge to right of B's left edge, [RectA.Right > RectB.Left], and
  • A's top above B's bottom, [RectA.Top > RectB.Bottom], and
  • A's bottom below B's Top [RectA.Bottom < RectB.Top]

Note 1: It is fairly obvious this same principle can be extended to any number of dimensions.
Note 2: It should also be fairly obvious to count overlaps of just one pixel, change the < and/or the > on that boundary to a <= or a >=.
Note 3: This answer, when utilizing Cartesian coordinates (X, Y) is based on standard algebraic Cartesian coordinates (x increases left to right, and Y increases bottom to top). Obviously, where a computer system might mechanize screen coordinates differently, (e.g., increasing Y from top to bottom, or X From right to left), the syntax will need to be adjusted accordingly/

Tuesday, June 1, 2021
 
anjan
answered 7 Months ago
14

This will find if the rectangle is overlapping another rectangle:

public boolean overlaps (Rectangle r) {
    return x < r.x + r.width && x + width > r.x && y < r.y + r.height && y + height > r.y;
}
Sunday, June 13, 2021
 
rojo
answered 6 Months ago
95

Edited to better wording, as suggested :

Basic observations :

  • I assume the radius is one, since it doesn't change anything.
  • given any two points, there exists at most two unit circles on which they lie.
  • given a solution circle to your problem, you can move it until it contains two points of your set while keeping the same number of points of your set inside it.

The algorithm is then:

  • For each pair of points, if their distance is < 2, compute the two unit circles C1 and C2 that pass through them.
  • Compute the number of points of your set inside C1 and C2
  • Take the max.
Sunday, August 8, 2021
 
Eddy
answered 4 Months ago
49

Using the link @Muckle_ewe gave me, I was able to code the following algorithm: Outside the main()

class Vector3d {  // this is a pretty standard vector class
public:
    double x, y, z;
    ...
}

void subdivide(const Vector3d &v1, const Vector3d &v2, const Vector3d &v3, vector<Vector3d> &sphere_points, const unsigned int depth) {
    if(depth == 0) {
        sphere_points.push_back(v1);
        sphere_points.push_back(v2);
        sphere_points.push_back(v3);
        return;
    }
    const Vector3d v12 = (v1 + v2).norm();
    const Vector3d v23 = (v2 + v3).norm();
    const Vector3d v31 = (v3 + v1).norm();
    subdivide(v1, v12, v31, sphere_points, depth - 1);
    subdivide(v2, v23, v12, sphere_points, depth - 1);
    subdivide(v3, v31, v23, sphere_points, depth - 1);
    subdivide(v12, v23, v31, sphere_points, depth - 1);
}

void initialize_sphere(vector<Vector3d> &sphere_points, const unsigned int depth) {
    const double X = 0.525731112119133606;
    const double Z = 0.850650808352039932;
    const Vector3d vdata[12] = {
        {-X, 0.0, Z}, { X, 0.0, Z }, { -X, 0.0, -Z }, { X, 0.0, -Z },
        { 0.0, Z, X }, { 0.0, Z, -X }, { 0.0, -Z, X }, { 0.0, -Z, -X },
        { Z, X, 0.0 }, { -Z, X, 0.0 }, { Z, -X, 0.0 }, { -Z, -X, 0.0 }
    };
    int tindices[20][3] = {
        {0, 4, 1}, { 0, 9, 4 }, { 9, 5, 4 }, { 4, 5, 8 }, { 4, 8, 1 },
        { 8, 10, 1 }, { 8, 3, 10 }, { 5, 3, 8 }, { 5, 2, 3 }, { 2, 7, 3 },
        { 7, 10, 3 }, { 7, 6, 10 }, { 7, 11, 6 }, { 11, 0, 6 }, { 0, 1, 6 },
        { 6, 1, 10 }, { 9, 0, 11 }, { 9, 11, 2 }, { 9, 2, 5 }, { 7, 2, 11 }
    };
    for(int i = 0; i < 20; i++)
        subdivide(vdata[tindices[i][0]], vdata[tindices[i][1]], vdata[tindices[i][2]], sphere_points, depth);
}

Then in the main():

vector<Vector3d> sphere_points;
initialize_sphere(sphere_points, DEPTH);  // where DEPTH should be the subdivision depth
for(const Vector3d &point : sphere_points)
    const Vector3d point_tmp = point * RADIUS + CENTER;  // Then for the sphere I want to draw, I  iterate over all the precomputed sphere points and with a linear function translate the sphere to its CENTER and chose the proper RADIUS

You actually only need to use initialize_sphere() once and use the result for every sphere you want to draw.

Monday, September 13, 2021
 
user3263192
answered 3 Months ago
65

Introduction

Quite now your matching conditions may be too broad. However, you can use levenshtein distance to check your words. It may be not too easy to fulfill all desired goals with it, like sound similarity. Thus, I'm suggesting to split your issue into some other issues.

For example, you can create some custom checker which will use passed callable input which takes two strings and then answering question about are they same (for levenshtein that will be distance lesser than some value, for similar_text - some percent of similarity e t.c. - it's up to you to define rules).


Similarity, based on words

Well, all of built-in functions will fail if we are talking about case when you're looking for partial match - especially if it's about non-ordered match. Thus, you'll need to create more complex comparison tool. You have:

  • Data string (that will be in DB, for example). It looks like D = D0 D1 D2 ... Dn
  • Search string (that will be user input). It looks like S = S0 S1 ... Sm

Here space symbols means just any space (I assume that space symbols will not affect similarity). Also n > m. With this definition your issue is about - to find set of m words in D which will be similar to S. By set I mean any unordered sequence. Hence, if we'll found any such sequence in D, then S is similar to D.

Obviously, if n < m then input contains more words than data string. In this case you may either think that they are not similar or act like above, but switch data and input (that, however, looks a little bit odd, but is applicable in some sense)


Implementation

To do the stuff, you'll need to be able to create set of string which are parts from m words from D. Based on my this question you can do this with:

protected function nextAssoc($assoc)
{
   if(false !== ($pos = strrpos($assoc, '01')))
   {
      $assoc[$pos]   = '1';
      $assoc[$pos+1] = '0';
      return substr($assoc, 0, $pos+2).
             str_repeat('0', substr_count(substr($assoc, $pos+2), '0')).
             str_repeat('1', substr_count(substr($assoc, $pos+2), '1'));
   }
   return false;
}

protected function getAssoc(array $data, $count=2)
{
   if(count($data)<$count)
   {
      return null;
   }
   $assoc   = str_repeat('0', count($data)-$count).str_repeat('1', $count);
   $result = [];
   do
   {
      $result[]=array_intersect_key($data, array_filter(str_split($assoc)));
   }
   while($assoc=$this->nextAssoc($assoc));
   return $result;
}

-so for any array, getAssoc() will return array of unordered selections consisting from m items each.

Next step is about order in produced selection. We should search both Niels Andersen and Andersen Niels in our D string. Therefore, you'll need to be able to create permutations for array. It's very common issue, but I'll put my version here too:

protected function getPermutations(array $input)
{
   if(count($input)==1)
   {
      return [$input];
   }
   $result = [];
   foreach($input as $key=>$element)
   {
      foreach($this->getPermutations(array_diff_key($input, [$key=>0])) as $subarray)
      {
         $result[] = array_merge([$element], $subarray);
      }
   }
   return $result;
}

After this you'll be able to create selections of m words and then, permutating each of them, get all variants for compare with search string S. That comparison each time will be done via some callback, such as levenshtein. Here's sample:

public function checkMatch($search, callable $checker=null, array $args=[], $return=false)
{
   $data   = preg_split('/s+/', strtolower($this->data), -1, PREG_SPLIT_NO_EMPTY);
   $search = trim(preg_replace('/s+/', ' ', strtolower($search)));
   foreach($this->getAssoc($data, substr_count($search, ' ')+1) as $assoc)
   {
       foreach($this->getPermutations($assoc) as $ordered)
       {
           $ordered = join(' ', $ordered);
           $result  = call_user_func_array($checker, array_merge([$ordered, $search], $args));
           if($result<=$this->distance)
           {
               return $return?$ordered:true;
           }
       }
   }
   
   return $return?null:false;
}

This will check on similarity, based on user callback, which must accept at least two parameters (i.e. compared strings). Also you may wish to return string which triggered callback positive return. Please, note, that this code will not differ upper and lower case - but may be you do not want such behavior (then just replace strtolower()).

Sample of full code is available in this listing (I didn't used sandbox since I'm not sure about how long code listing will be available there). With this sample of usage:

$data   = 'Niels Faurskov Andersen';
$search = [
    'Niels Andersen',
    'Niels Faurskov',
    'Niels Faurskov Andersen',
    'Nils Faurskov Andersen',
    'Nils Andersen',
    'niels faurskov',
    'niels Faurskov',
    'niffddels Faurskovffre'//I've added this crap
];

$checker = new Similarity($data, 2);

echo(sprintf('Testing "%s"'.PHP_EOL.PHP_EOL, $data));
foreach($search as $name)
{
   echo(sprintf(
      'Name "%s" has %s'.PHP_EOL, 
      $name, 
      ($result=$checker->checkMatch($name, 'levenshtein', [], 1))
         ?sprintf('matched with "%s"', $result)
         :'mismatched'
      )
   );

}

you'll get result like:

Testing "Niels Faurskov Andersen"

Name "Niels Andersen" has matched with "niels andersen"
Name "Niels Faurskov" has matched with "niels faurskov"
Name "Niels Faurskov Andersen" has matched with "niels faurskov andersen"
Name "Nils Faurskov Andersen" has matched with "niels faurskov andersen"
Name "Nils Andersen" has matched with "niels andersen"
Name "niels faurskov" has matched with "niels faurskov"
Name "niels Faurskov" has matched with "niels faurskov"
Name "niffddels Faurskovffre" has mismatched

-here is demo for this code, just in case.


Complexity

Since you're caring about not just any methods, but also about - how good is it, you may notice, that such code will produce quite excessive operations. I mean, at least, generation of string parts. Complexity here consists of two parts:

  • Strings parts generation part. If you want to generate all string parts - you'll have to do this like I've described above. Possible point to improve - generation of unordered string sets (that comes before permutation). But still I doubt it can be done because method in provided code will generate them not with "brute-force", but as they are mathematically calculated (with cardinality of enter image description here)
  • Similarity checking part. Here your complexity depends of given similarity checker. For example, similar_text() has O(N3) complexity, thus with large comparison sets it will be extremely slow.

But you still may improve current solution with checking on the fly. Now this code will first generate all string sub-sequences and then start checking them one by one. In common case you don't need to do that, so you may want to replace that with behavior, when after generating next sequence it will be checked immediately. Then you'll increase performance for strings which have positive answer (but not for those which have no match).

Sunday, November 21, 2021
 
ajjumma
answered 2 Weeks ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :
 
Share