Trapezoidal map search structure

@zStupan

Part 1 of 2:

It’s been a while since I’ve considered this subject (maybe 15 years most recently). I’m aware that the DCEL (doubly connected edge list) data structure is commonly used for computational geometry, like that of the trapezoidal map, which includes the notion of “half edges”, but I’m not seeing that in your structure, so you’re using something a bit different (likely valid, I’m not well versed). Yet, your question is about C++, efficiency and what boils down to a tree data structure, with which I’m quite familiar.

I note there’s a C++ library (student experiment, not worth much investigation and declared so in the comments) which uses inheritance for differentiating a node as in your second case. I hesitate to say that is best, but I’ll say it is likely better than three different pointer types in Node, two of which will always be nullptr depending on ‘type’. To that member, too, I submit that ‘type’, a NodeType, should probably be the return of a virtual “GetType()” member, so there’s no accidental misalignment of that value in the base.

That said, there is some reason to at least consider std::any, though there may be as many reasons not to prefer it. The virtual object approach in your second snippet is the classic representation of polymorphism, with acknowledgment that virtual functions impose a minor performance penalty. They do offer a great many design benefits for you use case.

To that end, too, you may not require a pointer for the member of XNode, YNode and LeafNode. Why not just make them members and avoid the allocation/deallocation? Is there something about your intention for Point, Segment and Trapezoid which implies they must be stored by pointer? Do you require, for example, that a Point or Trapezoid can be extracted from a Node and put in another Node (I think not). If not, then don’t. The pointer is an indirection, which is to say that the processor must access a new memory location to use the pointer to get the object itself, and that is a performance hit (due even more to a cache miss than for the two step process implied).

If you do need to ‘new’ the object, consider std::unique_ptr so as to automatically delete the object (less for you to concern yourself with). If you use unique_ptr, you’ll use ‘make_unique’ instead of ‘new’. One might consider the alternative std::scoped_ptr. This puts a burder on the Node, however, because neither pointers can be copied. In this regard std::scoped_ptr is more limited. A std::unique_ptr can be moved, but not copied or ‘shared’ (in the sense that std::shared_ptr shares ownership). For modern C++ it is suggested that std::unique_ptr is the presumed default, while std::shared_ptr has other benefits but is slower in performance. If your object uses std::unique_ptr (or the more restrictive std::scoped_ptr), you must consider your copy constructor and assignment operator situation carefully, as in perhaps Node should not be a copyable class (default assignment and copy are deleted/prohibited). If Node’s must be copyable, you must decide if you’re going to create a copy of the Point, Segment or Trapezoid, or if you want shared ownership of one common such object when a Node is copied. If the latter applied, you’d use std::shared_ptr. All of these issues must come to mind even with naked pointers, but it is more work with naked pointers.

If some resemblance to standard container design is considered (which is to say you plan create an iterator class), you’ll need to consider how the iterator deals with the notion of the ‘current’ entry. In some cases a copy of the element is used, and others might prefer a pointer to that element. If you’re using a pointer, you have to contend with that as an issue if you use std::unique_ptr. You’ll be motivated to consder std::unique_ptr.get(), and thus hold a raw pointer in the iterator. If you choose to use std::shared_ptr, you have no such issue. They are easier, which is why they’re overused. We say overused because they are a performance concern, and are often chosen for this convenience over performance priorities.

Last edited on

Part 2 of 2:

Those issues are quite separate for what to do about ‘parent’, ‘left’ and ‘right. These are in support of the tree structure you’re building. Of these, we have good reason to declare that ‘parent’ is a pointer that does NOT own anything. It is merely a way to refer to the parent Node (and is only required if you’re not using recursive algorithms to traverse or operate the tree, or otherwise believe ‘parent’ is important for performance). In most tree structures, ‘parent’ is avoided, because the recursive algorithm naturally ‘tracks’ the parent from the return of a recursive call. C++ developers consider the wisdom of this kind of naked pointer, because while the intent is merely to refer to the parent, the potential exists that code might, by accident, write to it, or worse delete it. We hope to express intent in code, and there’s very little intent described by this naked pointer. Make it private and control it for read only purposes (consider const where appropriate).

This leaves ‘left’ and ‘right’. They may well express ownership of these two child Nodes. When they do, deleting the entire tree is simply a matter of deleting the root of the tree. The Node destructor would naturally see to the destruction of the ‘left’ and ‘right’ child, which in turn (being Nodes) establishes a recursive traversal of the tree causing deletion of all but nullptr nodes. This is typical and convenient. If, however, you can accept the minor restrictions associated with std::unique_ptr, you can use it for ‘left’ and ‘right’ so as to not have to even consider this destruction in the Node destructor. It would be ‘implied’ by the std::unique_ptr, and therefore automatic.

However, if std::unique_ptr is uncomfortable (it is moved, not copied), you might use std::shared_ptr. The default behavior of a copy constructor or assignment operator is (loosely) acceptable, but there’s a minor performance impact.

On that point, let me zoom out one moment to discuss efficiency. Your post places the question of efficiency in the context of the data structure, but there’s an “out layer” you’ll want to consider which is more imposing. You may be considering efficiency and performance as related, and they are, but efficiency may invoke the notion of space savings equally, or prioritize one over the other. There is a competing notion of convenience, which may negatively impact performance and space efficiency, but considering what you MIGHT be doing, you may end up preferring convenience over speed.

The implication of pointers in C++ (naked or smart) is that you intended to allocate with ‘new’ frequently (same notion in this context as make_unique, make_shared, etc). This couples performance with allocation from new (related to malloc), and therefore limits performance to that of the heap’s allocation speed. It is widely known that allocation performance is orders of magnitude faster when custom allocation schemes, typically (and most easily) implemented as “allocation from arrays”, are used. By array I intend to imply std::vector or more complex containers, not exclusively the primitive C style array, but that, too, may depend on your real underlying objectives. The point here is that this Node class may be instantiated many times, and where performance is concerned, both space and speed are enhanced by allocating out of memory taken from “malloc” (or some related heap allocation implied within a container like vector – which is safer) in bulk. It is the bulk allocation of this resource which saves much time. Every ‘new’ (or malloc) requires the heap to encode information in a header which usually exists before the memory address returned by malloc (implying ‘new’ and all others), occupying space for each and every allocation. When a bulk (let’s say 1024 Nodes at once) allocation strategy is used, you save that header information over many Nodes (or whatever objects are being ‘newed’). This does not mean you’re switching to a vector or array like storage strategy. You’re still using the notions of ‘parent’, ‘left’ and ‘right’ for node connections as before.

The heap is typically locked (with a mutex) during each allocation in threaded builds, because it is a common resource, which further impacts performance when allocating frequently.

This approach can simplify some of your memory allocationstrategy (because everything is stored in these vectors, memory can be released at cost and complexity savings). It can complicate one point, however – construction and destruction. For custom allocation you may chose to ignore the paradigm of construction and destruction and treat the Node as a C style struct, so there’s no action in a constructor or destructor. This is a typical approach in real time systems like physics engines where performance is critical. You loose RAII, but you gain performance when object count is high.

On the other hand, if you prefer or require RAII in Node, and you write constructor and destructor functions, you can employ “in place new” and “in place delete” as an alternative. This simply allows the constructor/destructor cycle to acknowledge that both new and delete on Node (or whatever class is involved) does not involve the heap directly, but assumes custom storage. This is used by std::make_shared and std::make_unique.

If the burden of complexity of these performance options are beyond your target intentions, stick with your preference between std::unique_ptr or std::shared_ptr for ‘left’ and ‘right’ members. Professional code with high performance priorities usually grapples with these issues as common practice, so old hands like me jump in without hesitation. That might not be what you want, but at least this exposes the kind of options we consider. Without custom allocators you may observe unique allocations in the region of 10 to 25 million per second in non-threaded builds in typical modern desktop hardware, which can (depending on many factors) drop to as low as the task switching speed (meaning 150 to 300 thousand per second) in threaded builds due to synchronization of heap access. Custom allocations can double the best case performance in some situations, or retain the 10 to 25 million per second allocation rate even in threaded builds.

While you did inquire about efficiency, perhaps your actual performance concerns aren’t as critical as you expect.

Holy cow, that’s a wall of text.

Remember, most of the questions here are by students who are learning this stuff for the first time. Even if they ask about “efficiency” (which depends entirely upon the system constraints), a good answer is “efficiency == only stuff you need”.

As Niccolo noted, a Trapeziodal Map is a highly specialized data structure, typically using DCEL. This is waaaay over the head of a one-off university assignment.
Now, if the professor was having students work on a special research project...

To answer the question about structure: either one of those will do. I will suggest using a union for your data.

It is OK to repeat information in your tree. It is OK to use plain pointers, but you will have to make sure to delete stuff properly.

You do not need a parent node.

struct Node
{
  NodeType type;
  Node*    left;
  Node*    right;
  union
  {
    Trapezoid t;
    Point     p;
    Segment   s;
  };

  Node(): type(XNODE), left(nullptr), right(nullptr) { }
  ...

  ~Node()
  {
    delete left;
    delete right;
  }
};

At some future point you can mess with things like data encapsulation (to guarantee the invariant that left and right are unique, dynamically-allocated objects), but for now, don’t worry about it. Just make sure that whenever you assign to one of them it looks like foo->left = new Node; or something similar (like foo->left = new Node( XNODE, x );).

There are plenty of other variations you can use. Before you become too sure about your structure (and spend a whole lot of time coding it), be sure to work your way through the two algorithms you need: build a TM and search a TM.

Take notes about what kind of data you actually need to keep track of while you work your way through the algorithms.

Hopefully you have already spent time looking at the stuff here: http://cglab.ca/~cdillaba/comp5008/mulmuley.html

Seriously, get out a pencil and paper and spend some time drawing stuff.

Hope this helps.

Thank you both for your replies. I actually enjoyed the wall of text :) Very informative. I've decided I'm sticking to C style pointers because I don't really get smart pointers, so I'll just make sure to delete them properly.

The DCEL could be used to represent the trapezoids themselves yes, although because of the special shape and structure of the subdivision a trapezoid is represented by the top and bottom segments and the two points through which the vertical exstentions are made, plus the pointers to it's neighbors (there are at most 4 neighbors). A trapezoid also contains a pointer to the leaf node it belongs to.

class Trapezoid {
private:
    Node* node;

    Segment top;
    Segment bottom;
    Point leftP;
    Point rightP;

    Trapezoid* upperLeft;
    Trapezoid* lowerLeft;
    Trapezoid* upperRight;
    Trapezoid* lowerRight;
public:
    Trapezoid();
    Trapezoid(Segment top, Segment bottom, Point leftP, Point rightP);
    ~Trapezoid(); //delete neighbor pointers
    //...
};

Maybe it should be a LeafNode*?

I used pointers in the derived node classes to avoid duplicating the data, but I guess it doesn't really make sense.

So now the search structure looks like this:

enum NodeType {
    XNODE,
    YNODE,
    LEAF
};

class Node {
protected:
    Node* leftChild{nullptr};
    Node* rightChild{nullptr};
public:
    Node() = default;
    virtual ~Node();

    virtual NodeType getType() const = 0;
    Node *getLeftChild() const;
    void setLeftChild(Node *leftChild);
    Node *getRightChild() const;
    void setRightChild(Node *rightChild);
};

class XNode : public Node {
    Point point;
public:
    XNode() = default;
    explicit XNode(Point p);
    ~XNode() override = default;

    NodeType getType() const override;
    Point getPoint() const;
    void setPoint(Point point);
};

class YNode : public Node {
    Segment segment;
public:
    YNode() = default;
    explicit YNode(Segment s);
    ~YNode() override = default;

    NodeType getType() const override;
    Segment getSegment() const;
    void setSegment(Segment segment);
};

class LeafNode : public Node {
    Trapezoid trapezoid;
public:
    LeafNode() = default;
    explicit LeafNode(Trapezoid t);
    ~LeafNode() override = default;

    NodeType getType() const override;
    Trapezoid getTrapezoid() const;
    void setTrapezoid(Trapezoid trapezoid);
};

But you're right @Niccolo, I would probably just be storing the derived classes as Node pointers, so maybe a union or std::any is a better solution. I'm still not sure.

EDIT: I guess if I go with the non polymorphic option std::variant would be better than union?

Last edited on

@zStupan,

I have, still, an unanswered question. You present the appearance of either a high end student, or a professional in need of expressing in code some ideas for a professional (or study) purpose. I’ve all but excluded the notion that you’re making a product.

Many engineers, scientists, researchers, and even graduate or PhD students in such situations choose Python. I personally loathe Python, but that’s a prejudice born from the fact I’ve been a C++/C developer for a long time. I have similar reactions to other languages.

The choice of C++ shouldn’t be taken lightly. If you’re studying C++, and that’s the underlying purpose, I have one avenue of response. If you’re a researcher (student or professional), I have another.

Bluntly, C++ is nasty. There are many ways of doing the same thing, and many should be avoided. There’s more to learn in order to use the language effectively, reliably and efficiently (both from the perspective of execution and development) when compared with other languages. I say this despite that I far prefer C++ to most any modern language, but then I've known it for decades.

I need to better understand why you intend write in C++. I can see, based on experience and the writings of many observing the same history, you are likely to end up chasing down bugs to a depressing end. That’s not to say you won’t succeed, but how I should advise you depends greatly on why you’ve chosen C++, and what you’re really doing in the larger context. I’ve asked earlier, but I still don’t understand that part sufficiently to be of REAL help here. It may be that my best advice is to suggest you switch to C# or Java if you’re not going to study smart pointers.

To that end, I cite this line from you:

"I don't really get smart pointers, so I'll just make sure to delete them properly."

This is, in part, what tells me to pause and ensure I know the environment in which you’re operating, and why you’ve chosen C++.

We know from research that pointers and allocation (they go together) is historically known to represent about 30% of all bugs in C (and C++ when used exclusively). One of the worst types of bugs related to issues with pointers is that the problem (or crash) happens well removed from the real source of the bug itself. It creates quite a debugging mystery. It has been known to soak up weeks and months. These kinds bugs have persisted in professional products for as long as years before they were found.

One of the single most important developments in C++ was the smart pointer. At first it wasn't even part of the language. I remember when it happened. I was a late 20's (almost 30) something engineer at the time. C++ was not yet in full vogue, but convincing. C was still more in use. C++ templates didn't exist, and so smart pointers in C++ didn't either. There were intrusive reference counted pointers, but those aren't what we now call smart pointers - one had to derive from a common base representing the reference count.

When templates were released (around 1990), one of the first things every interested programmer did with them was to fashion their own smart pointers (usually reference counted). The second was usually to fashion some containers (from lists to trees of some kind). It was after that when the STL was released, and shared_ptr was not in it. The shared_ptr came from Boost, then added to C++ much later.

An oversimplified but illustrative example of the smart pointer is this, which clarifies “what to get about it”.

using namespace std;

template< typename T> class SPtr
{
 private:

    SPtr *  thePointer;

 public:

   SPtr( Sptr * s ) : thePointer( s ) {}

 ~ SPtr() { if ( thePointer ) delete thePointer; }

   SPtr * operator ->() { return thePointer; }
};



void SomeFunc()
{
 SPtr< AType > p( new AType() );

 p->x = 1; // assuming AType has an integer x member
}

This naive version demonstrates the single most important aspect of them. They delete what they own in the destructor.

User code allocation with 'new' may take different forms (make_unique, make_shared), but no explicit delete is performed. Although SomeFunc includes the allocation of AType with 'new', it is deleted by the smart pointer when SomeFunc returns, even if an exception occurs (and that's key to their importance).

Using the pointer with the ‘->’ operator is the same as with raw pointers.

This naive example resembles (very loosely) std::scoped_ptr. You expect there’s no support for copying the pointer (which std::scoped_ptr will deny). Factually, this naive code would allow copies, but with disastrous implications (the memory pointed to would be deleted twice). The std::scoped_ptr denies copies (or moves), while the std::unique_ptr enforces moves (but prevents copies). The std:shared_ptr implements copies with reference counting, and thus eliminates all manual burden of defining ownership, or of deleting the allocated memory.

That’s a considerable benefit in the long run, because copying pointers around is one source of bugs even though that’s one of the reasons one likes and uses pointers. The contradictory nature of those two ideas is one of the many reasons smart pointers were created for C++, and why many advise the use of C#, Java or other languages (because they don’t have raw pointers - or at least they're behind a barrier - implementing a scheme closely resembling the behavior of std::shared_ptr, which C# calls references). Experienced C# programmers may object that C# CAN use pointers, but that is only in code declared by the 'unsafe' keyword, which I consider a derogatory judgment that happens to be true relative to C# code outside the 'unsafe' context.

The quote I show from you above hints you’re not familiar with RAII. The acronym is described by it’s author is poor (not a good marketing term). The naive smartpointer code I post shows what it is. Initialization (one of the I’s in the acronym) acquires (the A in the acronym) a resource, in this case allocated memory. Such resources could be anything that is opened which must subsequently be closed, or allocated and subsequently freed. The strong association between constructors and destructors is how C++ implements RAII. The destructor deals with closing or freeing the resource. This paradigm is key in C++. It isn’t in Java or C#, except in the hidden implementation of what they call references (the behavior I claim resembles std::shared_ptr).

This, in turn, suggests that C++ is very new to you. Implementing a target of such ambition as computational geometry may be ill advised, because you are (likely) diving too deep into the woods, and will end up spending considerable time with details you’ll find bothersome and delaying. Unless your purpose is to study C++, or for other reasons you require it, you may be better to switch to C# or Java. If not, you should consider a pause to study smart pointers before you continue.

I’m still not sure which. However, merely choosing raw pointers is not wise, and I have historical and empirical reasons for insisting on clarifying the issue. A modern C++ programmer without smart pointers is a fundamental contradiction unless there’s seriously well considered reasoning behind the choice.

Last edited on

@Niccolo
You have hit exactly on one of the main problems I have with C++ academia. (In another wall of text. Please consider using some formatting. :O)

C + + V S E D U C A T I O N A L R E A L I T Y

Modern C++ is more than capable, and has a number of very powerful idioms and structures to make code demonstrably correct and maintainable.

Unfortunately, a lot of old developers are still stuck on C or early C-like paradigms when programming C++. And university education is worse: introductory C++ courses are typically taught by people who are experts in some facet of CS other than C++ — meaning they aren’t capable (or interested) in teaching valuable C++.

Rather, they are interested in teaching students basic concepts, like arrays and control constructs, and they will use the most basic, learn-in-10-minutes C++ possible to do it.

C U R R I C U L A R G O A L S

I am guessing that zStupan is in a 200 or 300 level course, and the professor decided that Point Location With A Trapezoidal Map looked like an interesting, currently-useful programming exercise. If at a 300 level, then I would hope that the professor has already coded a solution himself. If at a 200 level I doubt he has.

The purpose of this exercise has nothing to do with actually being able to successfully perform point location (though doing it is obviously a requirement). It has to do with being able to effectively use somewhat more advanced data structures than before (ordered arrays, associative arrays, linked lists, and simple classes) to work on a more difficult goal than the ‘maintain a movie store database’ variety.

As Niccolo has observed, this assignment is a really bad choice for that goal.

Y O U R G O A L S

All is not lost. Your primary goal is to get an ‘A’. Nothing else. Not even learning C++. Learning how to code is your secondary goal. Messed up, isn’t it? You would think it is the other way around...

My advice, then, is do only what it takes to solve the homework. Even if the code is really, really bad, inefficient, leaks, tell dirty jokes, whatever... as long as it can construct a Trapezoidal Map and traverse it to identify what region a point lies, then you are golden.

See, your professor (or one of his TAs), will do the following:

  • verify that your code compiles

  • run it over a few test cases
    ...at least one of which will aim to test a corner case

  • glance through your code for a few things
    What those things are varies.
    At the minimum he will want to see a properly-shaped class or two and some
    basic organizational structure. He will likely have also mentioned some stuff
    in class that you should attend to.

D A T A S T R U C T U R E

Remember, a region will have at most four neighbors IFF you can guarantee that no two X values are the same. For your assignment, that may be a valid assumption. Either way, you are looking at, essentially, a linked list that bifurcates. For example:

        ┌───┐   ┌───┐
        │ B │···│ D │'·.┌───┐
┌───┐.·'└───┘   └───┘   │ G │ 
│ A │           ┌───┐.·'└───┘'·.┌───┐ 
└───┘'·.┌───┐.·'│ E │           │ H │
        │ C │   └───┘        .·'└───┘
        └───┘'·.┌───┐    .·'
                │ F │.·'
                └───┘

I drew this collection of neighboring regions after drawing a map (assuming no X coordinates share value). How can you represent this to best traverse regions?
Remember, finding adjacent regions is part of the algorithm!

Remember, you should spend time with a pencil and paper figuring it out. “Diving in”, as it were, is rarely a wise course of action. Figure out your needs first, then design your data structures. Then review:

  • Will it work as-is?
  • What changes do I need to make?
  • How difficult is it to find a neighbor? Split a segment? Etc.

Seriously, once you have a good grip on how to do it on paper, then code. Changes to the code will still happen, but you won’t have to spend time rewriting everything with each change.

Good luck!
Sorry for my own wall of text.

Thanks again guys, I should've better explained what I'm trying to do.

I am a student, as you've guessed. Currently in my last year (undergrad) and have picked Robot motion planing for my bachelor's thesis. More specifically, I want to implement the solution to the piano mover's problem which is presented in chapter 13 of this book: http://www.cs.uu.nl/geobook/. One step in this solution is constructing a trapezoidal map which is described in chapter 6 of the same book and summarized in @Duthomhas's link above. Also, at some point I want to visualize the whole planning procedure.

I've picked C++ because it's the language I'm most comfortable using and is the language I first learned at university. Although as you said @Duthomhas we were thought C basically for the most part. I remember I got scolded once for using the auto keyword and vectors instead of arrays. To be fair the professor was ancient. So smart pointers and other cool modern C++ features were never really explained to me and I've had to learn them myself and the language is huge so it'll take some time.

I've put some thought into using other languages. I share @Niccolo's opinion on Python, C# I didn't wanna pick because I'm running linux and I don't know how I would go about visualization. There is gtk# , which I am not familial with at all. Java I just don't really know that well.

In C++ I've worked with and know a lot of graphics libraries as well.

And I do need to spend some more time studying the algorithm.

Last edited on

Ouch!

"I remember I got scolded once for using the auto keyword and vectors instead of arrays."

Man, did @Duthomhas get that point right. (...and Dude, I type fast for an old man and I'm really surprised how short 8000 characters really is ;)

This might be the origin of those who profess that C++/Object Oriented Programming is bad, a waste or destructive.

It may create C# or Java programmers who think they know C++ but swear it's awful.

The problem with any argument is that, from certain perspectives (even my own), C++ can be awful, but in the same way English can be awful when used certain ways.

Suggestion: Use std::shared_ptr

In line with @Duthomhas' point about getting a grade (closely related to your thesis), and assuming you're going to continue with standard C++, I'm going back to underscore my suggestion of using std::shared_ptr.

Many embedded controllers use limited versions of C or C++, so you'd have to check for support. You may be able to use Boost's shared_ptr (and just that) if you must.

If your environment supports std::shared_ptr (or you can get Boost's), I'd suggest a quick (few hours at most) study of std::shared_ptr. Whatever objections one might have from a technical perspective, it would most closely resemble the ease and carefree implementation I would expect of C# or Java in your context.

The payback would be to shorten the overall project in front of you. With respect to myriad issues I predict if you use raw pointers, and ignoring any reason to consider unique_ptr (some performance benefit, for example), std::shared_ptr would be quite fast (faster than a C# build very likely), and you'd have all but zero issues related to ownership in your tree structure, or the many ways you might attach Trapezoids to Nodes, or what have you.

Suggestion: std::any ok, but the derived Trapezoid is classic

You'd need to experiment with std::any for an hour to see what weirdness it has (it is a notion C++ programmers find disorienting at first, slightly - a variable that changes type to what it was last assigned), but I wouldn't put a strong recommendation against using it. The hierarchy you posted where Trapezoids, Segments and Points are derived from a common base is classic and would probably serve well without std::any.

Suggestion: if you intend to continue with C++ in the future, a book list

A closing point, though, I'd like to underscore for you and any students in a similar position (emerging with knowledge of C++ damaged from such teachings):

If you want to know and use C++ well, you can completely correct the academic injury you've received on your own, with a reading of a few texts (and, of course, a bit of experiment). Nearly any of the recent offerings by Bjarne Stroustrup apply. Particularly "C++ Principles and Practice". Stroustrup's 1300 page reference is a bit dry, and can wait for later.

Herb Sutter's works are also highly recommended.

Josuttis' work "The C++ Standard Libary - A Tutorial and Reference" is particularly important for you.

"Effective Modern C++" by Meyers (there may be more than one in a series) is a good suggestion.

This site may be important: http://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines

Visit the Boost site and browse. Come back after you've advanced. You'll probably more interested the more you know about C++.

Consider examining Qt, but I'd recommend WxWidgets. Both are on par, generally, but WxWidgets is completely free.

As a summer "self help" plan, that would likely "complete your training" (at the risk of invoking Vader here).

Heh, I can use Java just fine. But I can’t stand it.

M E M O R Y M A N A G E M E N T

Another way to handle the dynamic memory is to keep a specialized pool, so your graph structures are never responsible for it. For example:

struct nodes_pool: public std::unordered_set <node*>
{
  ~nodes()
  {
    for (node* n : *this) delete n;
  }

  node* add()
  {
    node* n = new node;
    emplace_back( n );
    return n;
  }

  void remove( node* n )
  {
    delete n;
    erase( n );
  }
}
nodes;

Now, whenever you need a new node, just my_new_node = nodes.add(). When the nodes goes out of scope all the nodes will be deleted for you.

U S A G E

Keep in mind that the whole point of this thing is quick lookup in a predefined map. That is, the Trapezoidal Map is constructed before the end user sees anything.

This is so that the association between each trapezoidal region and a city (or whatever) is already done when you do the point location.

Take Google Maps for example. (Assuming it uses a Trapezoidal Map underneath. IDK if it does or doesn’t.)

Google will create the map first, so that it has it ready to use on its servers. Then it has a huge lookup table so that, once a region is identified, it can tell you what street/city/county you in.

Now when you are driving in your car you can ask “where am I?” Google does a point location lookup with your GPS coordinates to find the region in the TM, then looks that region up in its region→where you are database. Your cell phone happily draws a picture for you and tells you useful stuff about where you are.

To the point, the algorithm is optimized to find a region. It is not optimized to create a map. For this homework assignment, you do both, of course.

I M P L E M E N T A T I O N

You may have noticed, then, that creating the trapezoidal map is the tricky part. Here are a few hints:

(1) You can use the point lookup function while creating the map.

That is, for each new segment to add you have to identify the region(s) that the line segment crosses. And you have a convenient lookup function to locate the region(s) containing the endpoints of the segment. :O)

(2) Modify one region at a time.
Split your task up. You should start with the case that the line segment’s end points both lie in the same region. Then consider adjacent regions. Then consider three or more regions.

(3) Once you identify endpoint regions, there is a guaranteed path from the leftmost to the rightmost region, but it is not necessarily unique.

You can easily find the way from the left to the right with a simple recursive function to explore available paths.

Hope this helps.

[edit]
Added something to the suggested memory pool function to be more explicit

Last edited on

Thank you yet again.I've studied the github gist, read through some of the books, and smart pointers are pretty cool :D
I went with unique_ptr for the node class. I didn't go with the fancy "iteratively deleting the pointers to save on stack space" though, because my trees realistically won't be that deep.

I have one more question though. Can I still use raw pointers when it's just the case of pointing to another object or 'viewing' it? Like for example:

class Node {
protected:
    std::unique_ptr<Node> left, right;
public:
    Node() = default;
    virtual ~Node() = default;

    virtual NodeType getType() const = 0;
    Node* getLeft() const { return left.get(); }
    void setLeft(std::unique_ptr<Node> l) { this->left = std::move(l); }
    Node* getRight() const { return right.get(); }
    void setRight(std::unique_ptr<Node> r) { this->right = std::move(r); }
};

Here I return a raw pointer in the getters for the children so I can use them in the search structure like so:

class SearchStructure {
    std::unique_ptr<Node> root;
public:
    LeafNode* find(Point p) {
        Node* next = root.get();
        while(next != nullptr && next->getType() != LEAF) {
            if(condition) next = next->getLeft();
            else next = next->getRight();
        }
        return dynamic_cast<LeafNode*>(next);
    }
};

This is one case where I'd use raw pointers because there's no ownership, I'm just viewing the data. The nodes are still owned by root.

Another example, The trapezoid class. Trapezoids are owned by their coresponding leaf nodes liike so:

class Trapezoid {
private:
    // Ommited other members

    LeafNode* node;

    Trapezoid* upperLeft;
    Trapezoid* lowerLeft;
    Trapezoid* upperRight;
    Trapezoid* lowerRight;
};

class LeafNode : public Node {
Trapezoid t;
//...
};

The trapezoid has a pointer to its leaf node and it's neighbours, which I think should be raw pointers as well since they're already owned by their leaf nodes, and the leaf node is owned by its parent.

Mixing unique_ptr with raw pointer access is both freakishly painful and breaks the abstraction.

The problem that you face is that you may have multiple references to the same object — which is not what unique_ptr is designed for. (It is what shared_ptr is designed for.)

This is, in fact, why I suggested a memory pool. Let the pool maintain object ownership. All raw pointer references are therefore understood to be non-owning views; use them as you see fit. Then, at program termination the pool will delete all the objects.

If you wish to be more pedantic about preventing possible deletion of an object when other references to it still exist, use a shared_ptr. This replaces the memory pool easily and gives guaranteed RAII without the possibility of dangling pointers. Doing this may also wow your professor and get you bonus points.

tl;dr
Unique_ptr is not the droid you are looking for. Shared_ptr is.

Hope this helps.

Oh ok, It's not just ownership. I was thinking only from that aspect. Shared_ptr it is.

Thank you so much for taking the time out of your day to help me. You too @Niccolo. I really appretiate it.