[PATCH][RFC] Search for missing power line support features

[gaben]

Problem

The power lines are sometimes drawn from low quality satellite imagery, and support features can be easily missed.

Proposed solution

Add a java validator test to sort these issues out. It works as following:

• an average node distance calculated for the whole way (line or minor_line)
• using mean and individual segment lengths, the standard deviation calculated
• if exceeds a threshold, a warning message created where both nodes highlighted to make manual checks faster

Way requirements to lower false positives:

• the way has to have at least 5 nodes
• segment length must be higher than a specific value, calculated as follows:

default threshold

• power=line -> 1.6
• power=minor_line -> 1.4

if (mean / stdDev) < 4 (high inconsistency) an extra 0.2 threshold value added.

If any segment length exceeds mean * threshold, the warning fired. In my testing, they give good results.

Usage

Run the validator as usual, an extra warning appears if the issue detected.

[gaben]

And the best part it's already done :)

[gaben]

float is enough

[GerdP]

I see no use in the cast to float.
I think I've seen power lines in Japan where the distance between towers isn't very regular. Did you test this in areas with steep hills and water between?

[gaben]

Hmm, there is another minor issue found outside the patch context.

If there is a long line with a missing tower in the middle and the towers are referred with a number, the whole needs renumbered. I saw the references are just added without an actual survey but still, it's a bit dangerous to automatically fix the numbering.

Replying to GerdP:

I see no use in the cast to float.

I thought float is more than enough and saves memory.

I think I've seen power lines in Japan where the distance between towers isn't very regular. Did you test this in areas with steep hills and water between?

Yes, although only in my country which is mostly flat.

Preparing the next version of the patch, the tag collection is a bit outdated.

[stoecker]

I thought float is more than enough and saves memory.

If you don't store it somewhere (with multiple copies) then a downsizing conversion will have no real gain. Variable sizes only count when you have many or large objects :-)

[gaben]

I'm more familiar with the microcontroller C/C++ world where every bit counts 😄

Currently testing the 3rd version of the patch around the world. With a variable threshold, there are minimal false positives. The line has 1.6, while minor_line has 1.8 multiplier.

[gaben]

Current state:

• power tagset updated, contained deprecated tags like sub_station
• added line segment checker with variable threshold, depending on line type (line or minor_line), needs testing
• fixed some existing false positive warnings inside substations, where power=line and power=line + line=busbar|bay connects

Maybe the ref checker could be added as well.

I looked at the MapCSS if I can use it to be more portable (Osmose) but these checks need more advanced techniques.

[gaben]

@Klumbumbus, what do you think about a ref continuity checker on a power line? Is it worth it?

[gaben]

How can I detect crossing power=line|minor_line and water features like a river in MapCSS?

[GerdP]

So far this is not possible.

[gaben]

Alright, Java patch is ready, threshold parameters under testing.

[gaben]

v5 adds

• reference number continuity test
• line type checking (power=line/minor_line)
• improved missing support node checker

I also optimised for performance because the crossing finder is a CPU heavy task, probably responsible 90% per cent of the test running time.

What do you think? :)

[GerdP]

reg. crossing ways: can't you use CrossingWays for that?

[gaben]

Yeah, I tried, but it just didn't find anything don't know why :/ Side note: the 'cell' meaning which used in that class isn't clear for me.

I'm happy with that if you can modify it to use the CrossingWays test.

[GerdP]

Sorry, have no time. Maybe look how it is used in MultipolygonTest.

[gaben]

I used the implementation from MultipolygonTest for reference, but it still didn't work. Maybe that is tuned for MPs, while this also has to work with ways (tagged as some water body).

[gaben]

(fixed javadoc <ul/> -> </ul>)

[gaben]

added some comments, minor code improvements

[GerdP]

I'll have a closer look during the next days.

[gaben]

Thank you! :) I'm here if you suggest changes.

[GerdP]

First feedback:

• new javadoc is missing lines for parametes / return values
• checkstyle complains about some issues
• sonarling complains about some methods which could be static and obsolete blocks
• Maybe change Missing line support node within power line to Possibly missing line support node within power line? Or maybe better Possibly missing power=pole node / Possibly missing power=tower node depending on the expected support?
• The message Missing power line support tag from node is hard to read. Old text is Missing power tower/pole within power line. What's wrong with that? Maybe this can go into the group "missing tag" with a text like "node without power=*"?

[gaben]

Thank you, answers:

• [javadoc] it was intentional
  • the current version also missing some javadoc here and there
  • they are private methods, I don't expect usage outside this test

but easy to fix, so I did that

• [checkstyle] fixed
• [sonar]
  • What do Sonar "obsolete blocks" mean? I don't have Sonar set up with JOSM preferences.
  • static methods fixed
• [wording 1]

The problem is, sometimes they mix the poles with towers (or other way around) in a single power line in real life, so I saw this approach error-prone. In other words, the generic message is better as we can't guess confidently what's missing.

• [wording 2]

It is a bit misleading because it can be tower, pole plus portal and maybe catenary_mast as well.

Grouping under "missing tag" is the best idea so far!

[GerdP]

reg. sonarlint: In Eclipse you need the plugin and then you can "Bind to server". Server is josm.openstreetmap.de and the project is josm. I think that's all I did. There is no commandline version for this and I don't know if/how it works with other IDEs.

[gaben]

Thanks, I'm using IntelliJ IDEA it largely works the same as Eclipse in this regard.

Currently, I'm thinking about adding some tests as well. Maybe later :)

[gaben]

suggestions applied, minor code style improvements

[GerdP]

The new patch doesn't contain the changes in Way.java for getSegmentLengths().

[gaben]

Aaaarg, sorry about that. I was working on multiple patches (typos, other small things in over 10 files) and missed the Way.java part.

[gaben]

added missing Way.java part

[GerdP]

• What's the reason for the !way.isDisabled() check? This ignores ways which are hidden by filters, very unusual for validator. Did you mean way.isUsable()?
• you collect several water objects in datasetWaterways but not natural=coastline. Inteneded? I can imagine power lines crossing the ocean above the surface, but maybe they are not relevant?
• the test reg. Missing line support node within power line should probably ignore areas which are not downloaded as they may be covered by water?

[gaben]

They are good questions, thanks! :D

• I wrote that part 3 months ago, so I'm just guessing: I referenced one of the utilsplugin2 methods and there is this line

if (anyway.isDisabled()) continue which probably became !way.isDisabled() in the adaptation.

I remember checking both way.isDisabled() and way.isUsable(), but now I have no idea why ended up this way. As you wrote way.isUsable() probably makes more sense for validation.

• More or less intended. Near the coastline, they use underwater cables I guess, but never mapped or saw this kind of infrastructure. If anyone thinks it's useful, please give examples, and I'll look into it.
• Good catch, I opted for including. Imagine the following:
  1. you download specific data with overpass, in our case power data
  2. start validating and fixing issues
  3. notice a bigger issue, download the full data from the main server
  4. fix the discovered one in 3.
  5. revalidate the dataset to check the fix
  6. you lost one of the validator features because step 3. restricts the test to a small area

[GerdP]

reg. coastline: try full download with this small area: 60.2191844,20.0121117,60.2241931,20.0282156

reg. overpass and full download: I would download the full data to a new layer in step 3, but we have this issue with many other tests. The more items a test is analysing the larger the probem with incomplete data gets.

[GerdP]

Shouldn't this data produce warning Mixed reference numbering?

[GerdP]

This data marks the wrong node as Mixed reference numbering. I think it should mark the 2nd node in the way. Or it should mark the 3rd with "duplicate ref" or something similar.

[GerdP]

reg. code:

• I think directions.stream().findAny().get(); and similar should be replaced by directions.iterator().next(); whenever it is clear that the set contains only one object.
• way.referrers(Relation.class) returns a stream. I think these lines are obsolete:

                                          .collect(Collectors.toSet())
                                          // no parallel stream here, just makes the iteration slower
                                          .stream()
  

[gaben]

• coastlines works well with existing parameters, no need for extra handling in my short testing
• reference numbering: both your examples show the same problem, the checking is directional (and "stops" at the first issue). Should be fixed but will have different results based on the way direction.

Probably I need a different approach. What about searching for the longest continued ref numbering(s?) and comparing this sequence to the rest? It was my initial idea before coding, but dropped because it means "nothing". I've seen power lines where the majority of the nodes were misreferenced.

• code suggestions applied, thanks!

[GerdP]

reg. coastlines: I don't think so. Maybe the bounds in comment:28 were misleading. Download way 963238369. It produces several Missing line support node within power line warnings, some seem plausible but some segments are clearly between coastlines.
reg. refs: I also think that the longest sequence should be treated as "correct". Or maybe simplify the check to mark only the way if anything with the refs is suspicious.

[gaben]

It wasn't misleading, I tested on this specific way :D If you download map features along the way (Alt+Shift+D) and run the validator, there is only one warning across the water, but also is a missing tower around 60.215939, 20.0755674, near the coastline.

Alright, I will rewrite the ref checker and issue a warning for the whole way. This is the safest bet.

[GerdP]

It also claims that a tower is missing between node 8910059873 and node 8910059872 and another between node 8910059869
and node 8910059870. I think these are false positives which could be avoided by checking natural=coastline.

[gaben]

I added coastline to waterways locally (no patch yet). I was thinking about if the existing distance parameters work well with coastlines, as wrote in comment:30. Sorry about that. I don't want to spam the issue with patches. I will upload the new version when the ref checker is ready.

[gaben]

patch v8:

• added natural=coastline to collected water objects
• added configurable hilly compensation and threshold (can changed without restart)
• replaced !way.isDisabled with way.isUsable()
• restricted "Missing node..." warning to downloaded area (overpass compatible)
• rewritten the ref checker
• improved performance by ~10x (by eliminating parallelStream in findCrossings())

[GerdP]

• patch contains some good, but unrelated changes. Intended?
• test about wrong refs seems to work much better now.
• I'd evaluate the preferences once in startTest(). See e.g. minDist in test UnconnectedWays.
• The test reg. "Possibly missing line support node within power line" seems to be missing some issues? Why doesn't it complain about the line between nodes 7781362852 and 7781362851? I see three missing towers in Maxar Premium imagary.
• I would only collect usable ways in datasetWaterways and use a method for the collecting of water objects, something like this

      @Override
      public void startTest(ProgressMonitor progressMonitor) {
          super.startTest(progressMonitor);
          // the test run can take a bit of time, show detailed progress
          setShowElements(true);
  
          // collect all waterways
          getLayerManager()
                  .getActiveDataSet()
                  .getWays()
                  .parallelStream()
                  .filter(way -> way.isUsable() && (concernsWaterArea(way)
                          || way.referrers(Relation.class).anyMatch(PowerLines::concernsWaterArea)))
                  .forEach(datasetWaterways::add);
      }
  
      /**
       * Check if primitive has a tag that marks it as a water area or boundary of a water area.
       * @param p the primitive
       * @return true if primitive has a tag that marks it as a water area or boundary of a water area
       */
      private static boolean concernsWaterArea(OsmPrimitive p) {
          return p.hasTag("water", "river", "lake") || p.hasKey("waterway") || p.hasTag("natural", "coastline");
      }
  

[gaben]

• Comments fixes? Yes. Maybe should I put them in a separate patch? I always find spelling and other issues but don't bother with patches because it involves too much manual effort. For me it looks as follows: start the virtual machine, open IDE inside VM, create the patch, paste into gedit, copy, paste into the guest system (Windows), change back the line ending, save, search the file, upload to Trac. For every single patch.

So I'm putting them together with possibly unrelated changes :(

• "missing" warning: The code reflects my usage pattern, which involves running the validator regularly for visual guidance (error highlight).

You may know, on ways, the segment highlight isn't stable. As long you are adding nodes, the highlight can move or even disappear. It's unrelated to this ticket, it's how JOSM works currently. As a result, the fastest way to detect issues is running the validator regularly.

Regarding the example; the check can be only as accurate as the data. When you start adding nodes and rerun the validator, the warning will appear between n7781362852 and n7781362851.

• preference and water object collection suggestions applied, thank you! Much better this way :)

I found some false positive "Possibly wrong power line type used" warnings where towers used on short lengths on minor_lines over a water area. I'm thinking on a solution.

[GerdP]

I typically just use svn command line tool to create patches.

svn diff src test ... > xyz.patch

[gaben]

v9 complementary patch: add average and stdDev info to extended info panel

[gaben]

patch v9:

• added workaround for false positive "wrong line type..." warnings
• restricted "wrong line type..." check to downloaded area (overpass compatible)
• fixed segment alignment check
• code suggestions applied
• small refactor

[GerdP]

I don't understand this loop in visit():

for (int i = 1; i < w.getRealNodesCount(); i++) {

Why is the 1st node ignored, but not the last?

[gaben]

The intention was to create a segment check, which needs two consecutive nodes. So the first node saved before the loop (prevNode) but later I added the other checks and forgot the first node is ignored.

But it turns out, this skip is unnecessary. Just change it to 0, no more modification needed.

[GerdP]

OK

[gaben]

What's the plan with the patch?

[GerdP]

The logic in the patch itself is good enough after (with comment:41 applied). I am just not sure if the Validator dialog is the right place to add this kind of AI which somehow guesses that there must be more objects and blames an existing object. My understanding is that the blamed power line is correct unless a missing power=tower node changes the geometry (adds an angle).
It's an edge case. A similar problem is #17188.

[gaben]

If I translate it into a plugin, it doesn't make a difference - the messages still would show up in the validator dialog.

It uses not angles but distances, otherwise correct.

Btw the patch contains more than that:

1. revised the power tags (they were out of date)
2. refined the checks inside power stations
3. added ref continuity checker
4. added this "AI" (:D) missing node check
5. added extra info about way in extended info panel

[GerdP]

What I am thinking about is either a new window or at least a new category inside the validator window. But both will require a lot more work, so I'll probably commit the patch as is.

[gaben]

Yeah, I also often feel the validator window lacks functionality, levels and configuration possibility. In the current state it is rudimentary.

[GerdP]

v9 with some minor changes

[GerdP]

There are a few sonarlint issues, esp. with the Way.getSegmentLengths(). The code assumes that the way has nodes, this is not guaranteed. It is also not guaranteed that all nodes exist (isIncomplete() returns true). I'm not sure what to return for those cases. Maybe it would be better to move that code into PowerLines?

Would be nice to have some unit tests for the new methods in Utils, too.

[gaben]

Hmm, interesting. When I run remote SonarQube in IntelliJ it doesn't find any issues. Here is my setup

Probably it needs configured "local analysis script" option. You said in Eclipse it's simple, so I don't know why is it needed here :/

I will add the unit tests and probably move the problematic code inside PowerLines as lacking a better idea.

[GerdP]

reg. sonar: I have no local script. I have a laptop where I cannot simply configure josm.openstreetmap.de as server. It asks for a login. Not sure what I used (maybe the same as with trac), my PC installation never asks me for it.

[skyper]

power=connection needs to be added, see #21566 and #17034.

[gaben]

Replying to skyper:

power=connection needs to be added, see #21566 and #17034.

Ok, I will look into the validator part in the next days.

[Don-vip]

Milestone renamed

[gaben]

Hmm, how would you handle power=connection in reference numbering context? I mean, if there is a way numbering like this: ----X+++ where

• - a continuous ref segment (this is the longer, making it the reference for numbering)
• X is a power=connection
• + should be treated as a continuation of - or not?

I think the best would be code wise if it was treated like two separate ways.

[gaben]

added basic power=connection handling, minor code improvements

[stoecker]

Milestone renamed

[stoecker]

Milestone renamed

[gaben]

I'm thinking about putting the patch on GitHub and link it back here because we lost changes between patches, and it's already on the 11th iteration.

[stoecker]

Issue is I have little time for JOSM (and Vincent as well it seems). I can review the code, but not the functionality.

@Klumbumbus, skyper: If you're ok with the logic then I'll check the code and apply the patch. I don't see a big impact, when something is sub-optimal.

[stoecker]

P.S. Sorry gaben for the (probably nearly unacceptable) delay, but you know, that's still a free-time project.

[Don-vip]

Yes sorry. I'm still around for breaking/emergency/hyper urgent things but I can't find any time for routine stuff with work and personal things. I hope to come back to active development in August or September.

[gaben]

Ah, thank you guys for responding, no problem. As I found my first ever job, I became busy as well and since then have ever less time for open source :( I feel you.

I'm doing the libphonenumber plugin for 2 years now (see #15250).

Anyway, please find the patch ​on GitHub, among other pull requests. If you suggest something, I'll continue the development there.

[taylor.smock]

@gaben: If you have any patches you feel are languishing, feel free to ping me. I've been trying to go through the patch backlog, but I've prioritized recent tickets over older tickets. Partly because I know they are more likely to apply cleanly and have a responsive patch author, if something needs to be changed and/or clarified.

Anyway, I'm looking at your patch right now, and I'll be playing with it a bit (keep in mind I don't typically map power lines), but GerdP indicated that the logic was good.

[taylor.smock]

Quick comment on the validator: PowerLines#findCrossings is exceedingly expensive. As in, it takes up ~75% of the CPU time and ~79% of the memory allocations for a validator run (just looking at the Way checks) for Mesa County, Colorado (1).

Most of the CPU cost is in Way#isUsable (73% of method). I want to say I saw something somewhere about caching the result from that call. Which would help immensely. It is also responsible for ~17% of the memory allocations. Mostly from the stream in Way#hasIncompleteNodes.

About 25% of the allocations are from INode#getEastNorth -- the actual EastNorth object is not cached in Node. It looks those are for Geometry.getSegmentSegmentIntersection, which we may want to add an overload for (Geometry.getSegmentSegmentIntersection(ILatLon, ILatLon, ILatLon, ILatLon)). I'll attach a patch​ for that, if you want to try it. If it works out, a bit of cleanup will be necessary for sonarlint (null -> empty arrays, specifically).

(1)

[out:xml][timeout:90];
{{geocodeArea:Mesa County, Colorado}}->.searchArea;
(
  nwr/*nwr*/(area.searchArea);
);
(._;>;);
out meta;

EDIT: Additional place for memory allocation optimization: Way#getNodePairs creates a list which could be sized to Way#getNodesCount() - 1 (this would reduce the memory allocation and CPU cost by ~33% for getNodePairs). This means it would save an additional 5% or so of memory allocations for PowerLines#findCrossings. I'll apply a patch for that separately.

[taylor.smock]

Add Geometry#getSegmentSegmentIntersection(ILatLon, ILatLon, ILatLon, ILatLon), crossingPositions are now LatLon objects

[taylor.smock]

In 18470/josm:

Reduce memory allocations and CPU calls in Way#getNodePairs

This reduces memory allocations and CPU calls by ~33% for the method call
by setting the size of the list at construction time.

See #20716 comment:68.

[taylor.smock]

Decrease memory usage by ~83%, CPU samples by ~78%, deduplicate some code in Way for segment lengths,

[taylor.smock]

Like in comment:68, most of the remaining CPU samples (75%) are in Way#isUsable (specifically in hasIncompleteNodes). Almost all remaining memory allocations are from Way#getNodePairs.

After r18470, Way#isUsable used ~91% of the CPU samples, and attachment:20716.1.patch​ reduced it back to 75%.

[taylor.smock]

Significantly reduce cpu/memory allocations by using the same logic as CrossingWays (note: this logic should probably be extracted to a common class)

[taylor.smock]

OK. I'm happy with the performance hit of attachment:20716.2.patch​. I'll give the patch author (gaben) and the other maintainers a few weeks to take a look at it.

@gaben/@skyper: I've checked the changes against the provided unit test, attachment:20716-refs-mixed.osm​​, and attachment:20716-refs-mixed2.osm​​. Do we have any other samples to sanity check against? I've also sanity checked the changes by modifying attachment:20716-refs-mixed.osm​​, and it appears to work with 99% less cpu samples and 99% fewer memory allocations as compared to the original code.

Side note for gaben: thank you for the original patch. While I know I've spent quite a bit of time optimizing the code so it doesn't significantly slow down the validation process, you provided the original code, and many of the optimizations have occurred outside of your code (so thank you for providing something that showed some of the more inefficient code paths in JOSM core). About the only optimization in your code that had a significant impact was reusing the same logic as CrossingWays, which we don't have a "good" way to reuse currently (so I get why you didn't even think about using it). I should spend some time refactoring that code so it is easier to reuse.

[gaben]

@taylor.smock thank you the kind words, really appreciated :)

As for the patch, I plan to have a look at the weekend. Did you base the changes on the latest patch (PR on GitHub) version?

[taylor.smock]

I think so, but its been a bit since I pulled it down.

[gaben]

I checked in the weekend, looks good, but I have two minor comments:

• the "unneeded" null check in the maintain() function was intentionally left there to preserve consistency (sonar might warn about this)
• what do es1 variables mean?

[taylor.smock]

Replying to gaben:

I checked in the weekend, looks good, but I have two minor comments:

• the "unneeded" null check in the maintain() function was intentionally left there to preserve consistency (sonar might warn about this)

Odd. It wasn't warning me. And it shouldn't be warning you. It will always be true once it is hit, based off of the previous branch (previousRef != null && ref == null).
The code isn't multi-threaded (and probably cannot be multi-threaded), so there isn't even a race condition where previousRef could be null and ref could be null, thus skipping the first branch, but then (before the next branch executes) previousRef becomes not null, but ref is still null, thus skipping that branch, and coming to the last branch were the ref != null gets hit. But the code isn't multi-threaded, so that should never happen.
So the only way for ref to be null at that point is if someone is messing with the JVM, at which point we have bigger problems. Like someone messing with the JVM. :)

if (previousRef == null && ref != null) {
} else if (previousRef != null && ref == null /* This is the null check */) {
} else if (previousRef != null && ref != null /* Always `true` once this branch is hit absent race conditions/JVM hacking */) {
}

• what do es1 variables mean?

Good question. I think I was using es1 due to code in CrossingWays I was looking at using es1. We can change it, but I was mostly just reusing code from CrossingWays. Specifically,

for (int i = 0; i < way.getNodesCount() - 1; i++) {
    WaySegment es1 = new WaySegment(way, i);
    // do stuff with es1
}

Like I mentioned in comment:73,

About the only optimization in your code that had a significant impact was reusing the same logic as CrossingWays, which we don't have a "good" way to reuse currently (so I get why you didn't even think about using it). I should spend some time refactoring that code so it is easier to reuse.

[taylor.smock]

@gaben: do you have any further comments? Did I answer your comments from comment:76?

[taylor.smock]

In 18553/josm:

Fix #20716: Search for missing power line support features (patch by gaben, modified)

Way:

• Avoid Arrays.stream in hasIncompleteNodes. This decreases CPU cost by 90%+ and makes it free from a memory allocation standpoint.
• Add method to get segment lengths (meters)

CrossingWays:

• Avoid Node#getEastNorth calls
• Add a getSegments call that takes ILatLon

PowerLines:

• Check for inconsistent support node reference numbering
• Check for ways with unusually long segments without node supports
• Check for ways where line types might be misused

ValUtil:

• Avoid unnecessary calls to Node#getEastNorth
• Add getSegmentCells for ILatLon

InspectPrimitiveDataText:

• Add average segment length statistic

Geometry:

• Add getSegmentSegmentIntersection for ILatLon to avoid new EastNorth objects

Utils:

• Add getStandardDeviation methods

[taylor.smock]

In 18555/josm:

Update tests for new UI information

See #20716: Search for missing power line support features.

This also improves test failure feedback in TestUtils.assertEqualsNewline.
This is done by creating arrays and comparing those, which will help narrow
down where the actual problem was.

[aceman]

Good idea, thanks!

[gaben]

Replying to taylor.smock:

@gaben: do you have any further comments? Did I answer your comments from comment:76?

Ooopsie, sorry for the late response I'm quite busy these days.

I have no further questions. There was some misunderstanding of what I meant by consistency, but there is no code logic difference between the proposed and committed solution.

Thank you for taking care of the ticket! Users hopefully can soon give some feedback on the new feature ;)

Help/Preferences/Validator updated.

[taylor.smock]

Replying to gaben:

Ooopsie, sorry for the late response I'm quite busy these days.

Everyone else is busy as well, don't worry about it.

Thank you for taking care of the ticket! Users hopefully can soon give some feedback on the new feature ;)

Hopefully users like it. Thank you for the patch. I don't map power poles personally, but I can see it being useful for those that do.

Help/Preferences/Validator updated.

Thanks for updating the wiki page. :)